请教大家一个关于AVL树的代码...部分地方不懂
本帖最后由 zfqkjxy 于 2013-02-27 12:47:05 编辑 最近看了一个关于一个AVL树的程序，界面是MFC写的，节点的旁边有标注节点的平衡值。 但是大家请看如下代码，思想很易懂，但是为什么我觉得平衡值不太对啊。详见下：
左旋 //和普通的旋转一样，只不过后面改了平衡值
void RotateLeft(BSTree &tree) { //左单旋转的算法
BSTNode *temp = tree->rchild; //RR
tree->rchild = temp->lchild;
temp->lchild = tree;
tree->balance = 0;
temp->balance =0;
tree = temp;
}void RotateRight(BSTree &tree) { //右单旋转的算法
BSTNode *temp = tree->lchild; //LL
tree->lchild = temp->rchild;
temp->rchild = tree;
//tree->balance = 0;
temp->balance =0;
tree = temp;
}int Insert(BSTree &tree, int x, int &taller) { //AVL树的插入算法
int success = 0;
if(tree==0) {
tree=(BSTree)malloc(sizeof(BSTNode));
tree->data = x;
tree->balance=0;
tree->lchild=NULL;
tree->rchild=NULL;
success = tree!=0?1:0;
if(success)
taller = 1;
}
else if(x<tree->data) {
success = Insert(tree->lchild, x, taller);
if(taller)
switch(tree->balance) {
case -1:
LeftBalance(tree, taller);
break;
case 0:
tree->balance = -1;
break;
case 1:
tree->balance = 0;
taller = 0;
break;
}
}
else if(x>tree->data) {
success = Insert(tree->rchild, x, taller);
if(taller)
switch(tree->balance) {
case 1:
RightBalance(tree, taller);
break;
case 0:
tree->balance = 1;
break;
case -1:
tree->balance = 0;
taller = 0;
break;
}
}
return success;
}
int Insert(BSTree &tree,int x) {
int taller;
return Insert(tree, x, taller);
}