数据结构平衡二叉树的操作演示

数据结构平衡二叉树的操作演示.v.平衡二叉树操作的演示需求分析本程序是利用平衡二叉树，实现动态查找表的根本功能：创立表，查找、插入、删除。具体功能：初始，平衡二叉树为空树，操作界面给出创立、查找、插入、删除、合并、分裂六种操作供选择。每种操作均提示输入关键字。每次插入或删除一个结点后，更新平衡二叉树的显示。平衡二叉树的显示采用凹入表现形式。合并两棵平衡二叉树。把一棵二叉树分裂为两棵平衡二叉树，使得在一棵树中的所有关键字都小于或等于x，另一棵树中的任一关键字都大于x。如以下图：2．概要设计平衡二叉树是在构造二叉排序树的过程中，每当插入一个新结点时，首先检查是否因插入新结点而破坏了二叉排序树的平衡性，假设是那么找出其中的最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的关系，进展相应的旋转，使之成为新的平衡子树。具体步骤：每当插入一个新结点，从该结点开场向上计算各结点的平衡因子，即计算该结点的祖先结点的平衡因子，假设该结点的祖先结点的平衡因子的绝对值不超过1，那么平衡二叉树没有失去平衡，继续插入结点；假设插入结点的某祖先结点的平衡因子的绝对值大于1，那么找出其中最小不平衡子树的根结点；判断新插入的结点与最小不平衡子树的根结点个关系，确定是那种类型的调整；如果是LL型或RR型，只需应用扁担原理旋转一次，在旋转过程中，如果出现冲突，应用旋转优先原那么调整冲突；如果是LR型或RL型，那么需应用扁担原理旋转两次，第一次最小不平衡子树的根结点先不动，调整插入结点所在子树，第二次再调整最小不平衡子树，在旋转过程中，如果出现冲突，应用旋转优先原那么调整冲突；数据结构平衡二叉树的操作演示全文共14页，当前为第1页。计算调整后的平衡二叉树中各结点的平衡因子，检验是否因为旋转而破坏其他结点的平衡因子，以及调整后平衡二叉树中是否存在平衡因子大于1的结点。数据结构平衡二叉树的操作演示全文共14页，当前为第1页。流程图详细设计二叉树类型定义：typedefintStatus;typedefintElemType;typedefstructBSTNode{ElemTypedata;intbf;structBSTNode*lchild,*rchild;}BSTNode,*BSTree;StatusSearchBST(BSTreeT,ElemTypee)//查找voidR_Rotate(BSTree&p)//右旋voidL_Rotate(BSTree&p)//左旋voidLeftBalance(BSTree&T)//插入平衡调整voidRightBalance(BSTree&T)//插入平衡调整StatusInsertAVL(BSTree&T,ElemTypee,int&taller)//插入voidDELeftBalance(BSTree&T)//删除平衡调整voidDERightBalance(BSTree&T)//删除平衡调整StatusDelete(BSTree&T,int&shorter)//删除操作StatusDeleteAVL(BSTree&T,ElemTypee,int&shorter)//删除操作voidmerge(BSTree&T1,BSTree&T2)//合并操作数据结构平衡二叉树的操作演示全文共14页，当前为第2页。voidsplitBSTree(BSTreeT,ElemTypee,BSTree&T1,BSTree&T2)//数据结构平衡二叉树的操作演示全文共14页，当前为第2页。voidPrintBSTree(BSTree&T,intlev)//凹入表显示附录源代码：*include<stdio.h>*include<stdlib.h>//*defineTRUE1//*defineFALSE0//*defineOK1//*defineERROR0*defineLH+1*defineEH0*defineRH-1//二叉类型树的类型定义typedefintStatus;typedefintElemType;typedefstructBSTNode{ElemTypedata;intbf;//结点的平衡因子structBSTNode*lchild,*rchild;//左、右孩子指针}BSTNode,*BSTree;/*查找算法*/StatusSearchBST(BSTreeT,ElemTypee){if(!T){return0;//查找失败}elseif(e==T->data){return1;//查找成功}elseif(e<T->data){returnSearchBST(T->lchild,e);}else{returnSearchBST(T->rchild,e);}}//右旋voidR_Rotate(BSTree&p){BSTreelc;//处理之前的左子树根结点数据结构平衡二叉树的操作演示全文共14页，当前为第3页。lc=p->lchild;//lc指向的*p数据结构平衡二叉树的操作演示全文共14页，当前为第3页。p->lchild=lc->rchild;//lc的右子树挂接为*P的左子树lc->rchild=p;p=lc;//p指向新的根结点}//左旋voidL_Rotate(BSTree&p){BSTreerc;rc=p->rchild;//rc指向的*p的右子树根结点p->rchild=rc->lchild;//rc的左子树挂接为*p的右子树rc->lchild=p;p=rc;//p指向新的根结点}//对以指针T所指结点为根结点的二叉树作左平衡旋转处理，//本算法完毕时指针T指向新的根结点voidLeftBalance(BSTree&T){BSTreelc,rd;lc=T->lchild;//lc指向*T的左子树根结点switch(lc->bf){//检查*T的左子树的平衡度，并做相应的平衡处理caseLH://新结点插入在*T的左孩子的左子树，要做单右旋处理T->bf=lc->bf=EH;R_Rotate(T);break;caseRH://新结点插入在*T的左孩子的右子树上，做双旋处理rd=lc->rchild;//rd指向*T的左孩子的右子树根switch(rd->bf){//修改*T及其左孩子的平衡因子caseLH:T->bf=RH;lc->bf=EH;break;caseEH:T->bf=lc->bf=EH;break;caseRH:T->bf=EH;lc->bf=LH;break;}rd->bf=EH;L_Rotate(T->lchild);//对*T的左子树作左旋平衡处理R_Rotate(T);//对*T作右旋平衡处理}}//右平衡旋转处理voidRightBalance(BSTree&T){BSTreerc,ld;rc=T->rchild;switch(rc->bf){数据结构平衡二叉树的操作演示全文共14页，当前为第4页。数据结构平衡二叉树的操作演示全文共14页，当前为第4页。T->bf=rc->bf=EH;L_Rotate(T);break;caseLH:ld=rc->lchild;switch(ld->bf){caseLH:T->bf=RH;rc->bf=EH;break;caseEH:T->bf=rc->bf=EH;break;caseRH:T->bf=EH;rc->bf=LH;break;}ld->bf=EH;R_Rotate(T->rchild);L_Rotate(T);}}//插入结点StatusInsertAVL(BSTree&T,ElemTypee,int&taller){//taller反响T长高与否if(!T){//插入新结点，树长高，置taller为trueT=(BSTree)malloc(sizeof(BSTNode));T->data=e;T->lchild=T->rchild=NULL;T->bf=EH;taller=1;}else{if(e==T->data){taller=0;return0;}if(e<T->data){if(!InsertAVL(T->lchild,e,taller))//未插入return0;if(taller)//已插入到*T的左子树中且左子树长高switch(T->bf){//检查*T的平衡度，作相应的平衡处理caseLH:LeftBalance(T);taller=0;break;caseEH:T->bf=LH;数据结构平衡二叉树的操作演示全文共14页，当前为第5页。数据结构平衡二叉树的操作演示全文共14页，当前为第5页。break;caseRH:T->bf=EH;taller=0;break;}}else{if(!InsertAVL(T->rchild,e,taller)){return0;}if(taller)//插入到*T的右子树且右子树增高switch(T->bf){//检查*T的平衡度caseLH:T->bf=EH;taller=0;break;caseEH:T->bf=RH;taller=1;break;caseRH:RightBalance(T);taller=0;break;}}}return1;}voidDELeftBalance(BSTree&T){//删除平衡调整BSTreelc,rd;lc=T->lchild;switch(lc->bf){caseLH:T->bf=EH;//lc->bf=EH;R_Rotate(T);break;caseEH:T->bf=EH;lc->bf=EH;R_Rotate(T);数据结构平衡二叉树的操作演示全文共14页，当前为第6页。数据结构平衡二叉树的操作演示全文共14页，当前为第6页。caseRH:rd=lc->rchild;switch(rd->bf){caseLH:T->bf=RH;lc->bf=EH;break;caseEH:T->bf=lc->bf=EH;break;caseRH:T->bf=EH;lc->bf=LH;break;}rd->bf=EH;L_Rotate(T->lchild);R_Rotate(T);}}voidDERightBalance(BSTree&T)//删除平衡调整{BSTreerc,ld;rc=T->rchild;switch(rc->bf){caseRH:T->bf=EH;//rc->bf=EH;L_Rotate(T);break;caseEH:T->bf=EH;//rc->bf=EH;L_Rotate(T);break;caseLH:ld=rc->lchild;switch(ld->bf){caseLH:T->bf=RH;rc->bf=EH;break;caseEH:T->bf=rc->bf=EH;break;caseRH:T->bf=EH;rc->bf=LH;break;}ld->bf=EH;R_Rotate(T->rchild);L_Rotate(T);数据结构平衡二叉树的操作演示全文共14页，当前为第7页。数据结构平衡二叉树的操作演示全文共14页，当前为第7页。}voidSDelete(BSTree&T,BSTree&q,BSTree&s,int&shorter){if(s->rchild){SDelete(T,s,s->rchild,shorter);if(shorter)switch(s->bf){caseEH:s->bf=LH;shorter=0;break;caseRH:s->bf=EH;shorter=1;break;caseLH:DELeftBalance(s);shorter=0;break;}return;}T->data=s->data;if(q!=T)q->rchild=s->lchild;elseq->lchild=s->lchild;shorter=1;}//删除结点StatusDelete(BSTree&T,int&shorter){BSTreeq;if(!T->rchild){q=T;T=T->lchild;free(q);shorter=1;}elseif(!T->lchild){q=T;T=T->rchild;free(q);shorter=1;}数据结构平衡二叉树的操作演示全文共14页，当前为第8页。数据结构平衡二叉树的操作演示全文共14页，当前为第8页。SDelete(T,T,T->lchild,shorter);if(shorter)switch(T->bf){caseEH:T->bf=RH;shorter=0;break;caseLH:T->bf=EH;shorter=1;break;caseRH:DERightBalance(T);shorter=0;break;}}return1;}StatusDeleteAVL(BSTree&T,ElemTypee,int&shorter){intsign=0;if(!T){returnsign;}else{if(e==T->data){sign=Delete(T,shorter);returnsign;}elseif(e<T->data){sign=DeleteAVL(T->lchild,e,shorter);if(shorter)switch(T->bf){caseEH:T->bf=RH;shorter=0;break;caseLH:T->bf=EH;shorter=1;break;caseRH:DERightBalance(T);数据结构平衡二叉树的操作演示全文共14页，当前为第9页。sh数据结构平衡二叉树的操作演示全文共14页，当前为第9页。break;}returnsign;}else{sign=DeleteAVL(T->rchild,e,shorter);if(shorter)switch(T->bf){caseEH:T->bf=LH;shorter=0;break;caseRH:T->bf=EH;break;caseLH:DELeftBalance(T);shorter=0;break;}returnsign;}}}//合并voidmerge(BSTree&T1,BSTree&T2){inttaller=0;if(!T2)return;merge(T1,T2->lchild);InsertAVL(T1,T2->data,taller);merge(T1,T2->rchild);}//分裂voidsplit(BSTreeT,ElemTypee,BSTree&T1,BSTree&T2){inttaller=0;if(!T)return;split(T->lchild,e,T1,T2);if(T->data>e)InsertAVL(T2,T->data,taller);elseInsertAVL(T1,T->data,taller);数据结构平衡二叉树的操作演示全文共14页，当前为第10页。数据结构平衡二叉树的操作演示全文共14页，当前为第10页。}//分裂voidsplitBSTree(BSTreeT,ElemTypee,BSTree&T1,BSTree&T2){BSTreet1=NULL,t2=NULL;split(T,e,t1,t2);T1=t1;T2=t2;return;}//构建voidCreatBSTree(BSTree&T){intnum,i,e,taller=0;printf("输入结点个数:");scanf("%d",&num);printf("请顺序输入结点值\n");for(i=0;i<num;i++){printf("第%d个结点的值",i+1);scanf("%d",&e);InsertAVL(T,e,taller);}printf("构建成功，输入任意字符返回\n");getchar();getchar();}//凹入表形式显示方法voidPrintBSTree(BSTree&T,intlev){inti;if(T->rchild)PrintBSTree(T->rchild,lev+1);for(i=0;i<lev;i++)printf("");printf("%d\n",T->data);if(T->lchild)PrintBSTree(T->lchild,lev+1);}voidStart(BSTree&T1,BSTree&T2){intcho,taller,e,k;taller=0;k=0;while(1){system("cls");printf("平衡二叉树操作的演示\n\n");printf("********************************\n");数据结构平衡二叉树的操作演示全文共14页，当前为第11页。printf("平衡二叉树显示区数据结构平衡二叉树的操作演示全文共14页，当前为第11页。printf("T1树\n");if(!T1)printf("\n当前为空树\n");else{PrintBSTree(T1,1);}printf("T2树\n");if(!T2)printf("\n当前为空树\n");elsePrintBSTree(T2,1);printf("\n******************************************************************************\n");printf("T1操作：1.创立2.插入3.查找4.删除10.分裂\n");printf("T2操作：5.创立6.插入7.查找8.删除11.分裂\n");printf("9.合并T1,T20.退出\n");printf("******************************************************************************\n");printf("输入你要进展的操作：");scanf("%d",&cho);switch(cho){case1:CreatBSTree(T1);break;case2:printf("请输入要插入关键字的值");scanf("%d",&e);InsertAVL(T1,e,taller);break;case3:printf("请输入要查找关键字的值");scanf("%d",&e);if(SearchBST(T1,e))printf("查找成功！\n");elseprintf("查找失败！\n");printf("按任意键返回87");getchar();getchar();break;case4:printf("请输入要删除关键字的值");scanf("%d",&e);if(DeleteAVL(T1,e,k))printf("删除成功！\n");数据结构平衡二叉树的操作演示全文共14页，当前为第12页。数据结构平衡二叉树的操作演示全文共14页，当前为第12页。printf("删除失败！\n");printf("按任意键返回");g