平衡二叉树操作的演示

1、平衡二叉树操作的演示#in clude<stdio.h>#in clude<malloc.h>typedef int KeyType;/定义关键字类型typedef struct node/记录类型KeyType key;/关键字项int bf;/平衡因子struct node *lchild,*rchild;/左右孩子指针BSTNode;void LeftProcess(BSTNode *&p,i nt & taller)/对以指针p所指结点为根的二叉树作左平衡旋转处理，本算法结束时，/指针p指向新的根结点BSTNode *p1,*p2;if(p-&g

2、t;b 仁=0)/ 原本左右子树等高，现因左子树增高而使树增高p->bf=1;taller=1;/原本else if(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；/新结LR调else if(p1->b

3、f=-1)点插入在*p的左孩子的右子树上，要做 整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;else if(p2->bf=1) 点插在*p2的左子树上的情况p1->bf=0;p->bf=-1; else结点插在*p2的右子树上的情况p1->bf=1;p->bf=0; p=p2； p

4、->bf=0;/新/新结/新/仍将p指向新的根结点，并置其bf值为0 taller=O;void RightProcess(BSTNode *&p,int &taller)/对以指针p所指结点为根的二叉树作右平衡旋转处理，本算法结束时，/指针p指向新的根结点BSTNode *p1,*p2;if(p->b 仁=0)/ 原本左右子树等高，现因右子树增高而使树增高p->bf=-1;taller=1;else if(p->bf=1)/ 原本左子树比右子树高，现左右子树等高p->bf=0;taller=0;else/ 原本右子树比左子树高，须作右子树的平衡处

5、理p1=p->rchild;/p 指向*p的右子树根结点if(p1->bf=-1)点插入在*p的右孩子的左子树上，要做p->rchild=p1->lchild;p1->lchild=p;p->bf=p1->bf=0;p=p1；else if(p1->bf=1)点插入在*p的右孩子的左子树上，要做p2=p1->lchild; p1->lchild=p2->rchild; p2->rchild=p1; p->rchild=p2->lchild; p2->lchild=p; if(p2->bf=0)结点插

6、在*p2处作为叶子结点的情况p->bf=p1->bf=0;else if(p2->bf=-1)点插在*p2的右子树上的情况新结RR调/新结RL调/新/新结p1->bf=0;p->bf=1;else/ 新结点插在*p2的左子树上的情况p1->b 仁-1; p->b 仁0;p=p2；p->b 仁0;/ 仍将p指向新的结点，并置其bf值为0taller=0;intIn sertA VL(BSTNode*&b,KeyTypee,i nt&taller)/若在平衡二叉排序树b中不存在和e有相同关 键字的结点，则插入一个数据元素为e的新结占八

7、、)并返回1,否则返回0。若因插入而使二叉排 序树失去平衡，则作平衡旋转处理，布尔变量 taller反映b长高与否if(b=NULL)/原树为空，插入新结点，树长高，置 taller为1 b=(BSTNode*)malloc(sizeof(BSTNode);b->key=e;b->lchild=b->rchild=NULL;b->bf=0;taller=1;elseif(e=b->key)/ 树中已存在和e有相同关键字的结点则不插入 taller=0;return 0;if(e<b->key)/ 继续在*b的左子树中进行搜索if(InsertA VL(

8、b->lchild,e,taller)=0)/未插入return 0;if(taller=1)/ 已插入到*b的左子树中且左子树长高LeftProcess(b,taller);/继/已插续在*b的右子树中进行搜索elseif(lnsertA VL(b->rchild,e,taller)=O)未插入return 0;if(taller=1)入到*b的右子树中且右子树长高RightProcess(b,taller); return 1;void DispBSTree(BSTNode *b)/以括号表示法输出AVLif(b!=NULL)pri ntf("%d",b-&

9、gt;key);if(b->lchild匸NULL|b->rchild匸NULL)pri ntf("(");DispBSTree(b->lchild);if(b->rchild匸NULL)pri ntf(",");DispBSTree(b->rchild);prin tf(")");voidLeftProcess1(BSTNode*&p,i nt&taller)在删除结点时进行左处理BSTNode *p1,*p2;if(p->bf=1)p->bf=0;taller=1;else

10、 if(p->bf=0)p->bf=-1;taller=0;elsep1=p->rchild;if(p1->bf=0)须作RR调整p->rchild=p1->lchild;p1->lchild=p;p->bf=1;p1->bf=-1;p=p1；taller=O;else if(p1->bf=-1)/须作RR调整p->rchild=p1->lchild;p1->lchild=p;p1->bf=p->bf=0;p=p1；taller=1;else须作RL调整p2=p1->lchild;p1->lc

11、hild=p2->rchild;p2->rchild=p1;p->rchild=p2->lchild;p2->lchild=p;if(p2->bf=0)p->bf=O;p1->bf=0;else if(p2->bf=-1)p1->bf=1;p->bf=0;elsep1->bf=0;p->bf=-1;p2->bf=0;p=p2；taller=1;voidRightProcess1(BSTNode*&p,i nt&taller)在删除结点是进行右处理BSTNode *p1,*p2;if(p->

12、bf=-1)p->bf=O;taller=1;else if(p->bf=0)p->bf=1;taller=0;elsep1=p->lchild;if(p1->bf=0)须作LL调整p->lchild=p1->rchild; p1->rchild=p;p->bf=-1;p1->bf=1;p=p1；taller=0;else if(p1->bf=1)/须作LL调整p->lchild=p1->rchild;p1->rchild=p; p1->bf=p->bf=0; p=p1； taller=1;else

13、须作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;else if(p2->bf=1) p1->bf=-1;p->bf=0;elsep1->bf=0;p->bf=1;p2->b 仁0;P=P2；taller=1;voidDelete(BSTNode*q,BSTNode*&r,int&tal

14、ler)/由DeleteAVL调用，用于处理被删结点左右子 树均不空的情况if(r->rchild=NULL)q->key=r->key;q=r;r=r->lchild;free(q);taller=1;elseDelete(q,r->rchild,taller);if(taller=1)RightProcess1(r,taller);x,i ntint DeleteAVL(BSTNode*&p,KeyType&taller)/在AVL树中删除关键字为x的结点int k;BSTNode *q;if(p=NULL)return 0;else if(x

15、<p->key)k=DeleteAVL(p->lchild,x,taller);if(taller=1)LeftProcess1(p,taller);return k;else if(x>p->key)k=DeleteAVL(p->rchild,x,taller);if(taller=1)RightProcess1(p,taller);return k;else找到了关键字为x的结点，q=p;if(p->rchild=NULL)被删结点右子树为空p=p->lchild;free(q);taller=1;else if(p->lchild=N

16、ULL)删结点左子树为空p=p->rchild;free(q);taller=1;else删结点左右子树均不为空/p指向它/被Delete(q,q->lchild,taller); if(taller=1) LeftProcess1(q,taller); p=q；return 1;void mai n()BSTNode *b=NULL;int i,j,k;KeyType a=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,ai);In sertAVL(b,ai,j);DispBSTree(b);prin tf("n");printf("A VL:");DispBSTree(b);prin tf("