我一直致力于实现一个普通的二叉搜索树以及一个 AVL 树。我已经大致弄清楚了，但是有一个问题我似乎无法解决。当我编译并运行驱动程序时，插入失败。运行或编译时没有错误；它根本不插入。我什至将 BST 插入中的代码粘贴到插入方法中，结果相同。我将把实现连同 BST 实现放在下面。任何帮助都是完美的！原谅我半凌乱的代码。还没好好清理
BST Definition
class BSTree {
BSTNode *root;
public:
//constructors
BSTree();
BSTree(int);
//public members
bool isEmpty(); //check if the bst is empty
void insert(int newValue); //inserts an int into the bst. Returns success
bool find(int findMe); //searches bst for int. True if int is in tree
void preorder(); //calls recursive transversal
void inorder(); //calls recursive traversal
void postorder(); //calls recursive transversal
int height(BSTNode *n); // given node only.
int height(); //returns height of whatever node is passed in.
int totalheight(); //returns tot height. height of empty tree = -1
int avgheight(); //returns avg height of tree
int totaldepth(); //returns tot depth. depth of empty tree = -1
int avgdepth(); //returns avg depth of tree
bool remove(int value); //deletes int. returns true if deleted
private:
int depth(BSTNode *n, int count); //depth of node. recursive.
int counter(BSTNode *n); //called by other functions for counting nodes
int totalheight(BSTNode *n); //called from public totalheight
int totaldepth(BSTNode *n, int depth);
int avgheight(BSTNode *n, int th);
bool findRecursive(struct BSTNode *root, int findMe); //called from public find
struct BSTNode* insertRecursive(struct BSTNode *n, int newValue);
void inorderRecursive(BSTNode *n); //traverses tree in inorder
void preorderRecursive(BSTNode *n); //traverses tree in preorder
void postorderRecursive(BSTNode *n); //traverses tree in preorder
};
//----------------------Constructor---------------------------
BSTree::BSTree(){
root = NULL;
} // BSTree
//root value given
BSTree::BSTree(int value){
root = new BSTNode(value);
} //BSTree(int)
//--------------------------insert-------------------------
void BSTree::insert(int newValue){
root = insertRecursive(root,newValue);
} //insert
struct BSTNode* BSTree::insertRecursive(struct BSTNode *n,int newValue){
//base case
if(n==NULL)
return new BSTNode(newValue);
else if (newValue < n->value) {
n->left = insertRecursive(n->left,newValue);
}
else if (newValue > n->value) {
n->right = insertRecursive(n->right,newValue);
}
else; //duplicate: do nothing
return n;
} //insertRecursive
//--------------------------Call in main-------------------------
BSTree *t = new BSTree();
t->insert(50);
请记住，这非常有效。
AVL
class AVLTree : public BSTree {
BSTNode *root;
public:
//constructors
AVLTree(); //given nothing
AVLTree(int value); //giving root value
//member methods
void insert(int newValue);
private:
struct BSTNode* insert(BSTNode *n, int newValue);
struct BSTNode* rotateLeft(BSTNode *n);
struct BSTNode* rotateRight(BSTNode *n);
struct BSTNode* doubleLeft(BSTNode *n);
struct BSTNode* doubleRight(BSTNode *n);
};
//--------------------------constructors-----------------------
AVLTree::AVLTree(){
root = NULL;
} // AVLTree
//root value given
AVLTree::AVLTree(int value){
root = new BSTNode(value);
} //AVLTree(int)
我不会展示旋转方法，因为即使没有它们和正常的 BST 代码，它仍然不起作用。
//------------------------------insert------------------------
void AVLTree::insert(int newValue){
root = insert(root, newValue);
}//insert
struct BSTNode* AVLTree::insert(BSTNode* n, int newValue){
if (n == NULL){ //if we are at end of tree. Insert.
return new BSTNode(newValue);
}//if
else if (newValue < n->value) { //move left if newValue smaller than n->value
n->left = insert(n->left,newValue);
if (height(n->left) - height(n->right) == 2){
if(newValue < n->left->value)
n = rotateLeft(n);
else
n = doubleLeft(n);
}//if == 2
}//else if
else if (newValue > n->value) { //move right if newValue bigger
n->right = insert(n->right,newValue);
if (height(n->right) - height(n->left) == 2){
if(newValue > n->right->value)
n = rotateRight(n);
else
n = doubleRight(n);
}//if == 2
}//else if
else; //duplicate. Do nothing.
n->height = max(height(n->left),height(n->right)) + 1;
return n;
}//insert
//--------------------call in main ---------------------------
AVLTree *a = new AVLTree();
a->insert(50);