平衡二叉树的插入与生成

1、#include #include typedef int KeyType;typedef char InfoType;/*定义关键字类型*/typedef struct nodeKeyType key;int bf;InfoType data;struct node *lchild,*rchild; BSTNode;/*记录类型*/*关键字项*/*平衡因子*/*其他数据域*/*左右孩子指针*/void LeftProcess(BSTNode *p,int *taller)/*对以指针p所指结点为根的二叉树作左平衡旋转处理，本算法结束时，指针p指向新的根结占*/八、BSTNode *p1,*p

2、2;if (*p)-bf=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)/*新结点插入在的左孩子的左子树上，要作LL调整*/(*p)-lchild=p1-rchild;p1-rchild=*p;(*p)-bf=p1-bf=0;*p=p1;else if (p1-bf=-1)/*新

3、结点插入在的左孩子的右子树上，要作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;else if (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

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

5、新结点插入在的右孩子的右子树上，要作RR调整*/ (*p)-rchild=p1-lchild; p1-lchild=*p; (*p)-bf=p1-bf=0; *p=p1; else if (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; else if (p2-bf=-1)/*新结点插在*p2的右子树上

6、的情况*/p1-bf=0;(*p)-bf=1; else/*新结点插在*p2的左子树上的情况*/ p1-bf=-1;(*p)-bf=0; *p=p2;(*p)-bf=0;/*仍将p指向新的根结点,并置其bf值为0*/ *taller=0; int InsertAVL(BSTNode *b,KeyType e,int *taller) /*若在平衡的二叉排序树b中不存在和e有相同关键字的结点，则插入一个 数据元素为e的新结点,并返回1,否则返回0。若因插入而使二叉排序树 失去平衡，则作平衡旋转处理，布尔变量taller反映b长高与否*/ if(*b=NULL)/*原为空树,插入新结点，树“长高”

7、，置taller为1*/ *b=(BSTNode *)malloc(sizeof(BSTNode); (*b)-key=e; (*b)-lchild=(*b)-rchild=NULL; (*b)-bf=0; *taller=1; else if (e=(*b)-key)/*树中已存在和e有相同关键字的结点则不再插入*/ *taller=0; return 0; if (ekey)/*应继续在*6的左子树中进行搜索*/if (InsertAVL(&(*b)-lchild),e,taller)=0) /* 未插入*/ return 0;if (*taller=1)/*已插入到的左子树中且左子树“长

8、高” */LeftProcess(b,taller);else/*应继续在的右子树中进行搜索*/if (InsertAVL(&(*b)-rchild),e,taller)=0) /* 未插入*/ return 0;if (*taller=1)/*已插入到b的右子树且右子树“长高” */RightProcess(b,taller);return 1;void DispBSTree(BSTNode *b)/* 以括号表示法输出 AVL*/if (b!=NULL)printf(%d”,b-key);if (b-lchild!=NULL | b-rchild!=NULL)printf();DispBS

9、Tree(b-lchild);if (b-rchild!=NULL) printf(,);DispBSTree(b-rchild);printf()”);void LeftProcess1(BSTNode *p,int *taller) /* 在删除结点时进行左处理 */BSTNode *p1,*p2;if (*p)-bf=1)(*p)-bf=0;*taller=1;else if (*p)-bf=0)(*p)-bf=-1;*taller=0;else /*p-bf=-1*/p1=(*p)-rchild;/*需作RR调整*/if (p1-bf=0)(*p)-rchild=p1-lchild;

10、p1-lchild=*p; p1-bf=1;(*p)-bf=-1; *p=p1; *taller=0; else if (p1-bf=-1)/*需作 RR 调整*/ (*p)-rchild=p1-lchild; p1-lchild=*p; (*p)-bf=p1-bf=0; *p=p1; *taller=1; else/*需作RL调整*/ p2=p1-lchild; p1-lchild=p2-rchild; p2-rchild=p1; (*p)-rchild=p2-lchild; p2-lchild=*p; if (p2-bf=0) (*p)-bf=0;p1-bf=0; else if (p2-

11、bf=-1) (*p)-bf=1;p1-bf=0; else (*p)-bf=0;p1-bf=-1; p2-bf=0; *p=p2; *taller=1; void RightProcess1(BSTNode *p,int *taller) /*在删除结点时进行右处理 */ BSTNode *p1,*p2; if (*p)-bf=-1)(*p)-bf=0;*taller=-1;else if (*p)-bf=0)(*p)-bf=1;*taller=0;else /*p-bf=1*/p1=(*p)-lchild;if (p1-bf=0)/*需作 LL 调整*/(*p)-lchild=p1-rch

12、ild;p1-rchild=*p;p1-bf=-1;(*p)-bf=1;*p=p1;*taller=0;else if (p1-bf=1)/*需作 LL 调整*/(*p)-lchild=p1-rchild;p1-rchild=*p;(*p)-bf=p1-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;else if (p2-bf=1)(*p)-bf=-1

13、;p1-bf=0;else(*p)-bf=0;p1-bf=1;p2-bf=0;*p=p2;*taller=1;void Delete2(BSTNode *q,BSTNode *r,int *taller)/*由DeleteAVL()调用，用于处理被删结点左右子树均不空的情况*/if (*r)-rchild=NULL)q-key=(*r)-key;q=*r;(*r)=(*r)-lchild;free(q);*taller=1;elseDelete2(q,&(*r)-rchild),taller);if (*taller=1)RightProcess1(r,taller);int DeleteAV

14、L(BSTNode *p,KeyType x,int *taller) /*在 AVL树 p 中删除关键字为 x 的结点*/ int k;BSTNode *q;if (*p=NULL)return 0;else if (xkey)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;e

15、lse/*找到了关键字为x的结点，由p指向它*/q=*p；if (*p)-rchild=NULL)/*被删结点右子树为空*/ *p=(*p)-lchild;free(q);*taller=1;else if (*p)-lchild=NULL)/* 被删结点左子树为空 */*p=(*p)-rchild;free(q);*taller=1;else/*被删结点左右子树均不空*/Delete2(q,&(q-lchild),taller);if (*taller=1)LeftProcess1(q，taller);*p=q;return 1;void main()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;in;i+) printf(第d 步，插入d 元素:,i+1,ai);InsertAVL(&b,ai,&j