平衡二叉树操作的演示

#include<stdio.h>#include<malloc.h>typedefintKeyType;//定义关键字类型typedefstructnode//记录类型{KeyTypekey;//关键字项intbf;//平衡因子structnode*lchild,*rchild;//左右孩子指针}BSTNode;voidLeftProcess(BSTNode*&p,int&taller){//对以指针p所指结点为根的二叉树作左平衡旋转处理，本算法结束时，//指针p指向新的根结点BSTNode*p1,*p2;if(p->bf==0)//原本左右子树等高，现因左子树增高而使树增高{p->bf=1;taller=1;}elseif(p->bf==-1)//原本右子树比左子树高，现左右子树等高{p->bf=0;taller=0;}else//原本左子树比右子树高，须作左子树的平衡处理{p1=p->lchild;//p指向*p的左子树根节点if(p1->bf==1)//新结点插入在*p的左孩子的左子树上，要做LL调整{p->lchild=p1->rchild;p1->rchild=p;p->bf=p1->bf=0;p=p1;}elseif(p1->bf==-1)//新结点插入在*p的左孩子的右子树上，要做LR调整{p2=p1->rchild;p1->rchild=p2->lchild;p2->lchild=p1;p->lchild=p2->rchild;p2->rchild=p;if(p2->bf==0)//新结点插入在*p2处作为叶子结点的情况 p->bf=p1->bf=0;elseif(p2->bf==1)//新结点插在*p2的左子树上的情况{p1->bf=0;p->bf=-1;}else//新结点插在*p2的右子树上的情况{p1->bf=1;p->bf=0;}p=p2;p->bf=0;//仍将p指向新的根结点，并置其bf值为0}taller=0;}}voidRightProcess(BSTNode*&p,int&taller){//对以指针p所指结点为根的二叉树作右平衡旋转处理，本算法结束时，//指针p指向新的根结点BSTNode*p1,*p2;if(p->bf==0)//原本左右子树等高，现因右子树增高而使树增高{p->bf=-1;taller=1;}elseif(p->bf==1)//原本左子树比右子树高，现左右子树等高{p->bf=0;taller=0;}else//原本右子树比左子树高，须作右子树的平衡处理{p1=p->rchild;//p指向*p的右子树根结点if(p1->bf==-1)//新结点插入在*p的右孩子的左子树上，要做RR调整{p->rchild=p1->lchild;p1->lchild=p;p->bf=p1->bf=0;p=p1;}elseif(p1->bf==1)//新结点插入在*p的右孩子的左子树上，要做RL调整{p2=p1->lchild;p1->lchild=p2->rchild;p2->rchild=p1;p->rchild=p2->lchild;p2->lchild=p;if(p2->bf==0)//新结点插在*p2处作为叶子结点的情况 p->bf=p1->bf=0;elseif(p2->bf==-1)//新结点插在*p2的右子树上的情况{p1->bf=0;p->bf=1;{p->lchild=p1->rchild;p1->rchild=p;p1->bf=p->bf=0;p=p1;taller=1;}else//须作LR调整{p2=p1->rchild;p1->rchild=p2->lchild;p2->lchild=p1;p->lchild=p2->rchild;p2->rchild=p;if(p2->bf==0){p->bf=0;p1->bf=0;}elseif(p2->bf==1){p1->bf=-1;p->bf=0;}else{p1->bf=0;p->bf=1;}p2->bf=0;p=p2;taller=1;}}}voidDelete(BSTNode*q,BSTNode*&r,int&taller){//由DeleteAVL调用，用于处理被删结点左右子树均不空的情况if(r->rchild==NULL){q->key=r->key;q=r;r=r->lchild;free(q);taller=1;}else{Delete(q,r->rchild,taller);if(taller==1) RightProcess1(r,taller);}}intDeleteAVL(BSTNode*&p,KeyTypex,int&taller){//在AVL树中删除关键字为x的结点intk;BSTNode*q;if(p==NULL) return0;elseif(x<p->key){k=DeleteAVL(p->lchild,x,taller);if(taller==1) LeftProcess1(p,taller);returnk;}elseif(x>p->key){k=DeleteAVL(p->rchild,x,taller);if(taller==1) RightProcess1(p,taller);returnk;}else//找到了关键字为x的结点，由p指向它{q=p;if(p->rchild==NULL)//被删结点右子树为空{p=p->lchild;free(q);taller=1;}elseif(p->lchild==NULL)//被删结点左子树为空{p=p->rchild;free(q);taller=1;}else//被删结点左右子树均不为空{Delete(q,q->lchild,taller);if(taller==1) LeftProcess1(q,taller);p=q;}return1;}}voidmain(){BSTNode*b=NULL;inti,j,k;KeyTypea[]={4,9,0,1,8,6,3,5,2,7},n=10;printf("创建一棵AVL树:\n");for(i=0;i<n;i++){printf("第%d步，插入%d元素:",i+1,a[i]);InsertAVL(b,a[i],j);DispBSTree(b);printf("\n");}printf("AVL:");DispBSTree(b);printf("\n");prin