2

我已经用 C++ 中的旧二叉树构建了一个 AVL 树以供练习，但它无法正常工作。我认为它可能没有正确更新节点的高度，但我无法找出问题的根源（我 90% 确定它与辅助函数 getHeight、setHeight、getBalance 有关）。

一些示例测试运行..：

添加 6,3,4 会导致右旋转，它应该会导致 RL 旋转

类似地添加 20,30,25 会导致 LL 旋转，而它应该会导致 LR 旋转

添加 20,30,10,5,6 在应该导致 RL 旋转时会导致两个单独的右旋转

#include <string>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdlib>

using namespace std;

struct intNode {
   int data;
   intNode * Left;
   intNode * Right;
   int height;

   intNode(int input, intNode * iLeft= NULL, intNode * iRight = NULL) {
      data = input;
      Left = iLeft;
      Right = iRight;
      height = 0;
   }

};    

int getHeight(intNode* temp) {
   if (temp == NULL) 
       return 0;
   return temp->height;    
}

void setHeight(intNode * temp) 
{
    int hLeft = getHeight(temp->Left);
    int hRight = getHeight(temp->Right);          
    temp->height = 1 + max(hLeft, hRight); 
}

int getBalance(intNode * temp) {

   if (temp == NULL) {
      return 0;
   } else {
       return getHeight(temp->Left) - getHeight(temp->Right);
   }
}  


struct intTree {
    intNode * root;

    intTree();
    void addNode(int input);
    void addNode(int input, intNode *& root);
    void print();
    void print(intNode *input);

    intNode * balanceTree(intNode *& sub);
    intNode * rotateRight(intNode *& sub);
    intNode * rotateLeft(intNode *& sub);

}; 

 void intTree::print(intNode *input) {

    if (input != NULL) {
        print(input->Left);
        cout << input->data << endl;
        print(input->Right);
    }

}

void intTree::print() {
   print(root);
}

intNode * intTree::rotateRight(intNode *& subTree) {
   intNode * newRoot = subTree->Left;
   subTree->Left = newRoot->Right;   
   newRoot->Right = subTree;
   setHeight(subTree);    
   setHeight(newRoot);    

   return newRoot;
}

 intNode * intTree::rotateLeft(intNode *& subTree) {
   intNode * newRoot = subTree->Right;
   subTree->Right = newRoot->Left;   
   newRoot->Left = subTree;
   setHeight(subTree);    
   setHeight(newRoot);    

   return newRoot;
}

intNode* intTree::balanceTree(intNode *& subTree) {
   setHeight(subTree);

      if (getBalance(subTree) == 2 && getBalance(subTree->Right) < 0) {                     
         cout << "RL" << endl;
         subTree->Left = rotateLeft(subTree->Left);
         return rotateRight(subTree);

      } else if (getBalance(subTree) == 2) {                    // RR
        cout << "RR" << endl;
        return rotateRight(subTree);

      } else if (getBalance(subTree) == -2 && getBalance(subTree->Left) > 0) {  // LR
        cout << "LR" << endl;
        subTree->Right = rotateRight(subTree->Right);
        return rotateLeft(subTree);

      } else if (getBalance(subTree) == -2) {                   // LL
        cout << "LL" << endl;
        return rotateLeft(subTree);

      } else {
        return subTree;                                 // balanced
      }

}

intTree::intTree() {
   root = NULL;
}

void intTree::addNode(int input, intNode *& temp) {
   if (temp == NULL) {
       temp = new intNode(input);
   } else if (input < temp->data) {
       cout <<" added to the left" << endl;
       addNode(input,temp->Left);
   } else if (input > temp->data) {
       cout <<" added to the right" << endl;
       addNode(input, temp->Right);
   }

   temp = balanceTree(temp);

}

void intTree::addNode(int input) {
   addNode(input, root); 
}

void read() {
   string num;
   int balance, input;
   int i = 0;

   intTree * intBST = new intTree();       

   while (i != 10) {
      cout << "number?" << endl;
      cin >> input;


      intNode *tempInt= new intNode(input);
      intBST->addNode(input);

      i++; 
   }     

   cout << "Finished reading in files" << endl;

   while (true) {
      string userInput;
      cin >> userInput;    

      if (userInput == "Exit") {
         cout << "Goodbye!" << endl;
         return;
     }

     if (userInput == "Print") {
         intBST->print();
         return;
     }

  }
}


void main() {
  read();

  return 0;
}

我将不胜感激任何提示/帮助进一步解决这个问题。让我知道我是否可以提供更多信息来提供帮助。

谢谢你。

4

0 回答 0