數(shù)據(jù)結(jié)構(gòu)平衡二叉樹的操作演示

數(shù)據(jù)結(jié)構(gòu)平衡二叉樹的操作演示.v.平衡二叉樹操作的演示需求分析本程序是利用平衡二叉樹，實(shí)現(xiàn)動(dòng)態(tài)查找表的根本功能：創(chuàng)立表，查找、插入、刪除。具體功能：初始，平衡二叉樹為空樹，操作界面給出創(chuàng)立、查找、插入、刪除、合并、分裂六種操作供選擇。每種操作均提示輸入關(guān)鍵字。每次插入或刪除一個(gè)結(jié)點(diǎn)后，更新平衡二叉樹的顯示。平衡二叉樹的顯示采用凹入表現(xiàn)形式。合并兩棵平衡二叉樹。把一棵二叉樹分裂為兩棵平衡二叉樹，使得在一棵樹中的所有關(guān)鍵字都小于或等于x，另一棵樹中的任一關(guān)鍵字都大于x。如以下圖：2．概要設(shè)計(jì)平衡二叉樹是在構(gòu)造二叉排序樹的過程中，每當(dāng)插入一個(gè)新結(jié)點(diǎn)時(shí)，首先檢查是否因插入新結(jié)點(diǎn)而破壞了二叉排序樹的平衡性，假設(shè)是那么找出其中的最小不平衡子樹，在保持二叉排序樹特性的前提下，調(diào)整最小不平衡子樹中各結(jié)點(diǎn)之間的關(guān)系，進(jìn)展相應(yīng)的旋轉(zhuǎn)，使之成為新的平衡子樹。具體步驟：每當(dāng)插入一個(gè)新結(jié)點(diǎn)，從該結(jié)點(diǎn)開場(chǎng)向上計(jì)算各結(jié)點(diǎn)的平衡因子，即計(jì)算該結(jié)點(diǎn)的祖先結(jié)點(diǎn)的平衡因子，假設(shè)該結(jié)點(diǎn)的祖先結(jié)點(diǎn)的平衡因子的絕對(duì)值不超過1，那么平衡二叉樹沒有失去平衡，繼續(xù)插入結(jié)點(diǎn)；假設(shè)插入結(jié)點(diǎn)的某祖先結(jié)點(diǎn)的平衡因子的絕對(duì)值大于1，那么找出其中最小不平衡子樹的根結(jié)點(diǎn)；判斷新插入的結(jié)點(diǎn)與最小不平衡子樹的根結(jié)點(diǎn)個(gè)關(guān)系，確定是那種類型的調(diào)整；如果是LL型或RR型，只需應(yīng)用扁擔(dān)原理旋轉(zhuǎn)一次，在旋轉(zhuǎn)過程中，如果出現(xiàn)沖突，應(yīng)用旋轉(zhuǎn)優(yōu)先原那么調(diào)整沖突；如果是LR型或RL型，那么需應(yīng)用扁擔(dān)原理旋轉(zhuǎn)兩次，第一次最小不平衡子樹的根結(jié)點(diǎn)先不動(dòng)，調(diào)整插入結(jié)點(diǎn)所在子樹，第二次再調(diào)整最小不平衡子樹，在旋轉(zhuǎn)過程中，如果出現(xiàn)沖突，應(yīng)用旋轉(zhuǎn)優(yōu)先原那么調(diào)整沖突；數(shù)據(jù)結(jié)構(gòu)平衡二叉樹的操作演示全文共14頁，當(dāng)前為第1頁。計(jì)算調(diào)整后的平衡二叉樹中各結(jié)點(diǎn)的平衡因子，檢驗(yàn)是否因?yàn)樾D(zhuǎn)而破壞其他結(jié)點(diǎn)的平衡因子，以及調(diào)整后平衡二叉樹中是否存在平衡因子大于1的結(jié)點(diǎn)。數(shù)據(jù)結(jié)構(gòu)平衡二叉樹的操作演示全文共14頁，當(dāng)前為第1頁。流程圖詳細(xì)設(shè)計(jì)二叉樹類型定義：typedefintStatus;typedefintElemType;typedefstructBSTNode{ElemTypedata;intbf;structBSTNode*lchild,*rchild;}BSTNode,*BSTree;StatusSearchBST(BSTreeT,ElemTypee)//查找voidR_Rotate(BSTree&p)//右旋voidL_Rotate(BSTree&p)//左旋voidLeftBalance(BSTree&T)//插入平衡調(diào)整voidRightBalance(BSTree&T)//插入平衡調(diào)整StatusInsertAVL(BSTree&T,ElemTypee,int&taller)//插入voidDELeftBalance(BSTree&T)//刪除平衡調(diào)整voidDERightBalance(BSTree&T)//刪除平衡調(diào)整StatusDelete(BSTree&T,int&shorter)//刪除操作StatusDeleteAVL(BSTree&T,ElemTypee,int&shorter)//刪除操作voidmerge(BSTree&T1,BSTree&T2)//合并操作數(shù)據(jù)結(jié)構(gòu)平衡二叉樹的操作演示全文共14頁，當(dāng)前為第2頁。voidsplitBSTree(BSTreeT,ElemTypee,BSTree&T1,BSTree&T2)//數(shù)據(jù)結(jié)構(gòu)平衡二叉樹的操作演示全文共14頁，當(dāng)前為第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;//結(jié)點(diǎn)的平衡因子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;//處理之前的左子樹根結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)平衡二叉樹的操作演示全文共14頁，當(dāng)前為第3頁。lc=p->lchild;//lc指向的*p數(shù)據(jù)結(jié)構(gòu)平衡二叉樹的操作演示全文共14頁，當(dāng)前為第3頁。p->lchild=lc->rchild;//lc的右子樹掛接為*P的左子樹lc->rchild=p;p=lc;//p指向新的根結(jié)點(diǎn)}//左旋voidL_Rotate(BSTree&p){BSTreerc;rc=p->rchild;//rc指向的*p的右子樹根結(jié)點(diǎn)p->rchild=rc->lchild;//rc的左子樹掛接為*p的右子樹rc->lchild=p;p=rc;//p指向新的根結(jié)點(diǎn)}//對(duì)以指針T所指結(jié)點(diǎn)為根結(jié)點(diǎn)的二叉樹作左平衡旋轉(zhuǎn)處理，//本算法完畢時(shí)指針T指向新的根結(jié)點(diǎn)voidLeftBalance(BSTree&T){BSTreelc,rd;lc=T->lchild;//lc指向*T的左子樹根結(jié)點(diǎn)switch(lc->bf){//檢查*T的左子樹的平衡度，并做相應(yīng)的平衡處理caseLH://新結(jié)點(diǎn)插入在*T的左孩子的左子樹，要做單右旋處理T->bf=lc->bf=EH;R_Rotate(T);break;caseRH://新結(jié)點(diǎn)插入在*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);//對(duì)*T的左子樹作左旋平衡處理R_Rotate(T);//對(duì)*T作右旋平衡處理}}//右平衡旋轉(zhuǎn)處理voidRightBalance(BSTree&T){BSTreerc,ld;rc=T->rchild;switch(rc->bf){數(shù)據(jù)結(jié)構(gòu)平衡二叉樹的操作演示全文共14頁，當(dāng)前為第4頁。數(shù)據(jù)結(jié)構(gòu)平衡二叉樹的操作演示全文共14頁，當(dāng)前為第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);}}//插入結(jié)點(diǎn)StatusInsertAVL(BSTree&T,ElemTypee,int&taller){//taller反響T長(zhǎng)高與否if(!T){//插入新結(jié)點(diǎn)，樹長(zhǎng)高，置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的左子樹中且左子樹長(zhǎng)高switch(T->bf){//檢查*T的平衡度，作相應(yīng)的平衡處理caseLH:LeftBalance(T);taller=0;break;caseEH:T->bf=LH;數(shù)據(jù)結(jié)構(gòu)平衡二叉樹的操作演示全文共14頁，當(dāng)前為第5頁。數(shù)據(jù)結(jié)構(gòu)平衡二叉樹的操作演示全文共14頁，當(dāng)前為第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){//刪除平衡調(diào)整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);數(shù)據(jù)結(jié)構(gòu)平衡二叉樹的操作演示全文共14頁，當(dāng)前為第6頁。數(shù)據(jù)結(jié)構(gòu)平衡二叉樹的操作演示全文共14頁，當(dāng)前為第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)//刪除平衡調(diào)整{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);數(shù)據(jù)結(jié)構(gòu)平衡二叉樹的操作演示全文共14頁，當(dāng)前為第7頁。數(shù)據(jù)結(jié)構(gòu)平衡二叉樹的操作演示全文共14頁，當(dāng)前為第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;}//刪除結(jié)點(diǎn)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;}數(shù)據(jù)結(jié)構(gòu)平衡二叉樹的操作演示全文共14頁，當(dāng)前為第8頁。數(shù)據(jù)結(jié)構(gòu)平衡二叉樹的操作演示全文共14頁，當(dāng)前為第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);數(shù)據(jù)結(jié)構(gòu)平衡二叉樹的操作演示全文共14頁，當(dāng)前為第9頁。sh數(shù)據(jù)結(jié)構(gòu)平衡二叉樹的操作演示全文共14頁，當(dāng)前為第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);數(shù)據(jù)結(jié)構(gòu)平衡二叉樹的操作演示全文共14頁，當(dāng)前為第10頁。數(shù)據(jù)結(jié)構(gòu)平衡二叉樹的操作演示全文共14頁，當(dāng)前為第10頁。}//分裂voidsplitBSTree(BSTreeT,ElemTypee,BSTree&T1,BSTree&T2){BSTreet1=NULL,t2=NULL;split(T,e,t1,t2);T1=t1;T2=t2;return;}//構(gòu)建voidCreatBSTree(BSTree&T){intnum,i,e,taller=0;printf("輸入結(jié)點(diǎn)個(gè)數(shù):");scanf("%d",&num);printf("請(qǐng)順序輸入結(jié)點(diǎn)值\n");for(i=0;i<num;i++){printf("第%d個(gè)結(jié)點(diǎn)的值",i+1);scanf("%d",&e);InsertAVL(T,e,taller);}printf("構(gòu)建成功，輸入任意字符返回\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");數(shù)據(jù)結(jié)構(gòu)平衡二叉樹的操作演示全文共14頁，當(dāng)前為第11頁。printf("平衡二叉樹顯示區(qū)數(shù)據(jù)結(jié)構(gòu)平衡二叉樹的操作演示全文共14頁，當(dāng)前為第11頁。printf("T1樹\n");if(!T1)printf("\n當(dāng)前為空樹\n");else{PrintBSTree(T1,1);}printf("T2樹\n");if(!T2)printf("\n當(dāng)前為空樹\n");elsePrintBSTree(T2,1);printf("\n******************************************************************************\n");printf("T1操作：1.創(chuàng)立2.插入3.查找4.刪除10.分裂\n");printf("T2操作：5.創(chuàng)立6.插入7.查找8.刪除11.分裂\n");printf("9.合并T1,T20.退出\n");printf("******************************************************************************\n");printf("輸入你要進(jìn)展的操作：");scanf("%d",&cho);switch(cho){case1:CreatBSTree(T1);break;case2:printf("請(qǐng)輸入要插入關(guān)鍵字的值");scanf("%d",&e);InsertAVL(T1,e,taller);break;case3:printf("請(qǐng)輸入要查找關(guān)鍵字的值");scanf("%d",&e);if(SearchBST(T1,e))printf("查找成功！\n");elseprintf("查找失??！\n");printf("按任意鍵返回87");getchar();getchar();break;case4:printf("請(qǐng)輸入要?jiǎng)h除關(guān)鍵字的值");scanf("%d",&e);if(DeleteAVL(T1,e,k))printf("刪除成功！\n");數(shù)據(jù)結(jié)構(gòu)平衡二叉樹的操作演示全文共14頁，當(dāng)前為第12頁。數(shù)據(jù)結(jié)構(gòu)平衡二叉樹的操作演示全文共14頁，當(dāng)前為第12頁。printf("刪除失?。n");printf("按任意鍵返回");g