C++中的AVL樹 - Stack Overflow異常

Question

我正在用C++編寫AVL樹程序。我將它從我以前製作的BST Priority Queue程序中解脫出來。不幸的是，每次添加一個應該引起輪換的新節點時，都會引發堆棧溢出異常。

這裏是我的代碼迄今：

node.h

#ifndef NODE_H_ 
#define NODE_H_ 

#include "stdio.h" 
#include <iostream> 
using namespace std; 

class node 
{ 
    public:node(int inputValue) 
     { 
      value = inputValue; 
      Right = NULL; 
      Left = NULL; 
      Parent = NULL; 
     } 

     node* Right; 
     node* Left; 
     node* Parent; 
     int value; 
     int Priority; 

     int AvlValue; 
     void UpdateHeight(); 

    private:int Height(node* root); 
}; 

void node::UpdateHeight() 
{ 
    int Right = Height(this->Right); 
    int Left = Height(this->Left); 
    if (Right == -1) 
     Right = 0; 
    if (Left == -1) 
     Left = 0; 

    AvlValue = Left - Right; 
} 

int node::Height(node* root) 
{ 
    if (root == NULL) return -1; 
    return max(Height(root->Left), Height(root->Right)) + 1; 
} 
#endif 

AVL.h

#ifndef AVL_H_ 
#define AVL_H_ 

#include "node.h" 
#include <string> 
#include <iostream> 
using namespace std; 

class AVL 
{ 
    private: 
     int size; 
     node* head; 
    public: 
     AVL(void); 
     ~AVL(void); 

     void ADD(int nvalue, int nPriority); 
     int Peek(); 
     int RemoveAndDisplay(); 
     int Height(node* root); 
     int SearchFor(int Priority); 

     void MenuSelection(int indicator); 
     void Controller(); 
     int MainMenu(); 

     void PreOrder(node* root); 
     void inorder(node* root); 

     void Traverse(node* root); 
     node* First(); 
     void LevelOut(); 

     node* LRotation(node* current); 
     node* RRotation(node* current); 
     node* DoubleRotationLR(node* current); 
     node* DoubleRotationRL(node* current); 
}; 

AVL::AVL() 
{ 
    size = 0; 
    head = NULL; 
} 

AVL::~AVL() 
{ 
} 

void AVL::LevelOut() 
{ 
    Traverse(head); 

    node* sort; 
    node* current = head; 
    while(current->Left != NULL || current->Right != NULL) 
    { 
     if(current->AvlValue != 2 && current->AvlValue != -2) 
     { 
      if(current->Left != NULL) 
      { 
       current = current->Left; 
      } 
      else if(current->Right != NULL) 
      { 
       current = current->Right; 
      } 
     } 
     else 
     { 
      sort = current; 
      if (sort->AvlValue == 2) 
      { 
       if (sort->Left->AvlValue == 1) 
       { 
        RRotation(sort); 
        Traverse(head); 
       } 
       else if(sort->Left->AvlValue == -1) 
       { 
        DoubleRotationLR(sort); 
        Traverse(head); 
       } 
      } 
      else 
      { 
       if (sort->Right->AvlValue == -1) 
       { 
        LRotation(sort); 
        Traverse(head); 
       } 
       else if(sort->Right->AvlValue == 1) 
       { 
        DoubleRotationRL(sort); 
        Traverse(head); 
       } 
      } 
     } 
    } 
} 

node* AVL::LRotation(node* current) 
{ 
    node* RightChild = current->Right; 
    current->Parent = RightChild; 
    RightChild->Left = current; 

    return RightChild; 
} 

node* AVL::RRotation(node* current) 
{ 
    node* LeftChild = current->Left; 
    current->Parent = LeftChild; 
    LeftChild->Right = current; 

    return LeftChild; 
} 

node* AVL::DoubleRotationLR(node* current) 
{ 
    node* tmp = current; 
    tmp->Left = LRotation(tmp->Left); 
    tmp = RRotation(tmp); 
    return tmp; 
} 

node* AVL::DoubleRotationRL(node* current) 
{ 
    node* tmp = current; 
    tmp->Right = RRotation(tmp->Right); 
    tmp = LRotation(tmp); 
    return tmp; 
} 

int AVL::Peek() 
{ 
    node* current = head; 
    while(current->Left != NULL) 
    { 
     current = current->Left; 
    } 
    return current->value; 
} 

int AVL::RemoveAndDisplay() 
{ 
    int valueReturn = -1; 
    node* current = head; 
    node* deleterPointer; 

    if(current->Left != NULL) 
    { 
     while(current->Left != NULL) 
     { 
      current = current->Left; 
     } 
     valueReturn = current->value; 

     deleterPointer = current->Parent; 
     delete current; 
     deleterPointer->Left = NULL; 
    } 
    else 
    { 
     valueReturn = current->value; 
     current = current->Right; 
     delete head; 
     head = current; 
    } 
    size--; 
    LevelOut(); 
    return valueReturn; 
} 

int AVL::SearchFor(int sPriority) 
{ 
    node* current = head; 
    bool keepGoing = true; 
    int valueToReturn = -1; 

    while(keepGoing) 
    { 
     if(current->Priority == sPriority) 
     { 
      valueToReturn = current->value; 
      keepGoing = false; 
     } 
     else 
     { 
      if(current->Priority > sPriority && current->Left != NULL) 
      { 
       current = current->Left; 
       keepGoing = true; 
      } 
      else if(current->Priority < sPriority && current->Right != NULL) 
      { 
       current = current->Right; 
       keepGoing = true; 
      } 
      else 
      { 
       keepGoing = false; 
      } 
     } 
    } 
    return valueToReturn; 
} 

void AVL::ADD(int nvalue, int nPriority) 
{ 
    node* current = head; 
    bool nextLvL = true; 
    if (head == NULL) 
    { 
     head = new node(nvalue); 
     head->Priority = nPriority; 
    } 
    else 
    { 
     while(nextLvL) 
     { 
      if(current->Priority > nPriority) 
      { 
       if(current->Left != NULL) 
       { 
        current = current->Left; 
        nextLvL = true; 
       } 
       else 
       { 
        current->Left = new node(nvalue); 
        current->Left->Priority = nPriority; 
        current->Left->Parent = current; 
        nextLvL = false; 
       } 
      } 
      else 
      { 
       if (current->Right != NULL) 
       { 
        current = current->Right; 
        nextLvL = true; 
       } 
       else 
       { 
        current->Right = new node(nvalue); 
        current->Right->Priority = nPriority; 
        current->Right->Parent = current; 
        nextLvL = false; 
       } 
      } 
     } 
    } 
    size++; 
    LevelOut(); 
} 

int AVL::MainMenu() 
{ 
    int inputvalue = 0; 
    cout << "\t Main Menu " << endl; 
    cout << " 1. Add " << endl; 
    cout << " 2. Remove " << endl; 
    cout << " 3. Peek " << endl; 
    cout << " 4. SearchFor " << endl; 
    cout << " 5. Size " << endl; 
    cout << " 6. Inorder " << endl; 
    cout << " 7. PreOrder " << endl; 
    cout << " 8. Height " << endl; 
    cout << " 0. Quit " << endl; 

    cout << " Input: "; 
    cin>>inputvalue; 
    return inputvalue; 
} 

void AVL::MenuSelection(int indicator) 
{ 
    int userInput = -1; 
    int prior; 
    int SearchForValue = -1; 

    switch(indicator) 
    { 
    case 1: 
     cout << "Value to add: "; 
     cin>> userInput; 
     cout << "Priority for input: "; 
     cin>> prior; 
     ADD(userInput, prior); 
     break; 
    case 2: 
     cout << "Item Removed: " << RemoveAndDisplay() << endl; 
     break; 
    case 3: 
     cout << "The first item in the Queue has a value of: " << Peek() << endl; 
     break; 
    case 4: 
     cout << "Priority to Search for: "; 
     cin>> prior; 
     SearchForValue = SearchFor(prior); 
     break; 
    case 5: 
     cout << "Total items in the Queue is: " << size << endl; 
     break; 
    case 6: 
     cout << "First Value: " << First()->value << endl; 
     inorder(head); 
     printf("\n"); 
     break; 
    case 7: 
     PreOrder(head); 
     printf("\n"); 
     break; 
    case 8: 
     cout << Height(head) << endl; 
     break; 
    case 0: 
     cout << "\tGood Bye!" << endl; 
     break; 
    default: 
     break; 
    } 

} 

node* AVL::First() 
{ 
    node* current = head; 
    while(current->Left != NULL) 
     current = current->Left; 
    return current; 
} 

void AVL::Traverse(node* root) 
{ 
    if (root != NULL) 
    { 
     root->UpdateHeight(); 
     Traverse(root->Left); 
     Traverse(root->Right); 
    } 
} 

void AVL::PreOrder(node* root) 
{ 
    if(root != NULL){ 
     cout << root->value << ", "; 
     PreOrder(root->Left); 
     PreOrder(root->Right); 
    } 
} 

void AVL::inorder(node* root) 
{ 
    if(root != NULL){ 
     inorder(root->Left); 
     cout << root->value << ", "; 
     inorder(root->Right); 
    } 
} 

int AVL::Height(node* root) 
{ 
    if (root == NULL) return -1; 
    return max(Height(root->Left), Height(root->Right)) + 1; 
} 

void AVL::Controller() 
{ 
    int input = -1; 
    while(input != 0) 
    { 
     input = MainMenu(); 
     MenuSelection(input); 
    } 
} 

#endif 

AVL.cpp

#include "AVL.h" 


int main() 
{ 
    AVL avl; 
    avl.Controller(); 
    return 0; 
} 

Answer 1

似乎是一個邏輯錯誤 - 之後一些printf調試時，看起來有時候一個名爲root->Left的節點仍然有root作爲它的Right成員。因此致電Height(root->Left)將最終嘗試Height(root->Left->Right)並再次遇到root。

（另外，Height()應該因爲它不以任何方式使用this聲明爲靜態的。）

Answer 2

你真的想忽略的由LevelOut叫做旋轉函數的返回值？

例如，AVL::LevelOut電話： RRotation(sort)

宣告： node* AVL::RRotation(node* current)

:-)