2023年廣工數(shù)據(jù)結構實驗報告平衡二叉樹

度劣與招實驗報告課程名稱數(shù)據(jù)結構實驗學院計算機學院專業(yè)班級計科9班學號學生姓名指導教師爰慶2023年7月6日caseRH:T->bf=LH；rd->bf=EH；break;caseEH:T->bf=rd->bf=EH；break；caseLH：T->bf=EH;rd—>bf=RH；break;)lc->bf=EH;R—Rotate(T->rchild);L_Rotate(T)；break;))/*平衡二叉樹的插入操作*/StatusInsertAVL(BBSTrec&T,RedTypce,Status&tallcr){if(NULL==T){T=(BBSTree)ma11oc(sizeof(BBSTNode))；T->data=e；T->bf=EH;T->lchiId=NULL;T->rchild=NULL;Jelseif(e==T->data)(〃書中已存在和e相等的結點tal1er=FALSE;returnFALSE;}e1seif(e<T->data){if(FALSE==InserlAVL(T->lchild,e,Ia1ler))relumFALSE;if(TRUE==tallcr){switch(T->bf){caseLH:LeftBalanee(T);taiIer=FALSE；break;caseEH:T->bf=LH；taller=TRUE;break;caseRH:T->bf=EH；taIler=FALSE;break;)}}else{if(FALSE==InsertAVL(T—>rchiId,e,ta11er))returnFALSE;if(TRUE==taller){switch(T->bf){caseLH：T->bf=EH;taIler=FALSE：break;caseEH:T->bf=RH;tai1er=TRUE;break;cascRH:RightBalancc(T);ta1ler=FALSE：break；returnTRUE;)/*平衡二叉樹的刪除操作*/StatusDelctcAVL(BBSTree&t,RcdTypcc,Status&shortcr){〃當被刪結點是有兩個孩子，且其前驅(qū)結點是左孩子時,lag=lstaticinttag=0;if(t==NULL){returnFALSE;//假如不存在元素，返回失敗}elseif(e==t->data){BBSTNode*q=NULL;//假如該結點只有一個孩子，則將日子樹取代該結點if(t->lchild==NULL){q=t；t=t—>rchiId;free(q);shorter=TRUE;1elseif(t->rchiId==NULL){q=t;t=t->lchild;frcc(q);shorter=TRUE;}〃假如被刪結點有兩個孩子，則找到結點的前驅(qū)結點,〃并將前驅(qū)結點的值賦給該結點，然后刪除前驅(qū)結點else{q=t->lchild;while(q->rchild){q=q->rchild;It->data=q->data;if(t->lchi1d->data==q->data){lag=1；De1eteAVL(t->lchiId,q->data,shorter);if(tag==l){BBSTreer=t->rchi1d;if(NULL==r)t->bf=0;e1se{switch(r->bf){caseEH:t->bf=-1；break;defauIt:RightBalance(t);break;I)))}eIscif(c<t->data){//左子樹中繼續(xù)查找if(!DeleteAVL(t->lchild,e,shorter)){returnFALSE；}〃刪除完結點之后，調(diào)整結點的平衡因子if(shorter&&(tag==0)){switch(t->bf){caseLH：t->bf=EH;shorter=TRUE;break;caseEH:t->bf=RH；shorter=FALSE;break;//假如本來就是右子樹較高，刪除之后就不平衡，需要做右平。衡操作caseRH:RightBalance(t)；〃右平衡解決if(t—>rchild->bf==EH)shorter=FALSE;e1seshorter=TRUE；break;)})elseif(c>t->data){〃右子樹中繼續(xù)查找if(!De1eteAVL(t->rchild,e,shorter)){returnFALSE;)〃刪除完結點之后，調(diào)整結點的平衡因子if(shorter&&(tag==0)){switch(t->bf){caseLH：LeftBalance(t);//左平衡解決if(t->lchiId->bf==EH)//注意這里，畫圖思考一下shorter=FALSE;e1se

shonershonershonerTRUE;break;shonerTRUE;caseEH：t->bf=LH;shorter=FALSE;break;caseRH：t->bf=EH;shorter=TRUE;break;))if(tag==!){intdepthLeft=BBSTrccDcpth(t->1child)；intdepthRight=BBSTreeDepth(t->rchiId);t—>bf=depthLcft-depthRight;})returnTRUE;)/*平衡二叉樹的直找操作*/BBSTreeScarchAVL(BBSTrceT,RcdTypcc){if(T==NULL)returnNULL；if(e==T->data){relurnT;

Jelseif(e>T->data){returnSearchAVL(T->rchild,e)；}else{returnSearchAVL(T->lchild,e);)/*獲取輸入存到數(shù)組a*/ArrayGetInputToArray(){Arrayhead,p,q;chark;hcad=p=q=NULL;intm;if(k!='\n'){seanp=(ArrayNode*)ma11oc(sizeof(ArrayNode))；head=p；p->data=m;k=getchar()；)whilc(k!='\n'){scanf("%d",&m)；q=(ArrayNode*)ma11oc(sizcof(ArrayNodc))；q->data=m；p->nextq；p->next；k=getchar();if(p!=NULL){p->next=NULL；)returnhead:〃返回存放數(shù)據(jù)的頭指針)/*根據(jù)輸入的字符串建一棵平衡二叉樹文/BBSTreeMakeBBSTree(){inti=0;Statusta1ler=TRUE;BBSTreeT=NULL;Arraya;a=GetlnputToArray();while(a!=NULL){tai1er=TRUE；InsertAVL(T,a->data,taIler)；a=a->next；}returnT;}/*遞歸先序遍歷*/StatusPre0rder_RecTraverse(BBSTreeT){if(NULL==T)returnOK;printf("%d",T->data);PreOrder_RecTraverse(T->1chi1d);PreOrder_RecTraverse(T—>rchild);)/*遞歸中序遍歷*/StatusInOrder_RecTraverse(BBSTreeT){if(T->lchild)InOrder_RecTraverse(T->|chi1d)；printf("%d",T->data);if(T->rchild)In0rder_RecTraverse(T—>rchi1d);)/*遞歸后序遍歷*/StatusLastOrder_RecTraverse(BBSTreeT){if(T->]child)LastOrder_RecTraverse(T->lchiId);if(T->rchi1d)LastOrder_RecTraverse(T->rchi1d);printf("%d",T-Adata)；)/*找到最左結點*/BBSTrceGoFarLeft(BBSTreeT,LStack&S)if(NULL==T)returnNULL；whi1e(T—>lchild!=NULL){

Push_LS(S,T);T=T->lchild:)returnT;)/*非遞歸中序遍歷*/voidInOrderTraverse_I(BBSTreeT){LStackS;InitStack_LS(S);BBSTreep=NULL;p=GoFarLeft(T,S);while(p!=NULL){printf("%d”,p->data)；if(p->rchild!=NULL){p=GoFarLeft(p->rchi1d,S);Ie1seif(StackEmpty_LS(S)!=TRUE)Pop_LS(S,p)；eIsep=NULL;BBSTreeVisitFarLeft(BBSTreeT,LStack&S){if(NULL==T)returnNULL;〃假如T為空，則返回空printf("%d",T->data)；〃先序，先讀取結點數(shù)據(jù)while(T->lchild!=NULL){Push_LS(S,T);//入棧T=T->1child;//遍歷下一個左子樹printf("%dT->data);〃下一個結點的讀取數(shù)據(jù))rcturnT;}/*非遞歸先序遍歷*/voidPreOrderTravese—I(BBSTreeT){LStackS；InitStack_LS(S);BBSTreep;p=VisitFarLeft(T,S);//先將左邊的數(shù)據(jù)先序讀取while(p!=NULL){if(P->rchi1d!=NULL)//假如最左下結點的右子樹不為空p=VisitFarLeft(p->rchild,S);//執(zhí)行遍歷該結點的左子樹elseif(StackEmpty_LS⑸!=TRUE)Pop_LS(S,p)；//假如S不為空棧，出棧elsep=NULL：//假如為空棧，p賦予空))/*非遞歸后序遍歷文/voidLast0rderTravese—I(BBSTreeroot){BBSTreep=root;BBSTreestack[30]；intnum=0;BBSTreehave_visited=NULL;while(NULL!=p||num>0){while(NULL!=p){stack[num++]=p；p=p->lchild;)p=stack[num-l]；if(NULL==p->rchild|Ihave_visited==p->rchi1d){printf("%d",p—>data)；num—;have_visited=p;p二NULL;)e1se(p=p->rchild;})printf("\n");)/*非遞歸層次遍歷輸出一棵二叉樹*/voidLeve1OrederTraverse_Print(BBSTreeT){jf(T==NULL){printf("Thetreeisempty!");if(T!=NULL){LQueueQ;InitQueue_LQ(Q);BBSTreep=T;printf("%d",p->data);EnQueue_LQ(Q,p);whi1e(DeQueue_LQ(Q,p)){if(p->lchild!=NULL){printf("%d”,p->1chi1d->data);EnQueue_LQ(Q,p->lchild)；)if(p->rchild!=NULL){printf("%d",p->rchi1d->data);EnQueue_LQ(Q,p->rchild);))))/*括號表達法輸出平衡二叉樹*/voidBraNotationPrint(BBSTreeT){if(NULL==T){printf("空!)}elsc{if(T!=NULL){if(T!=NULL){printf("%i",T->data);if(T->lchild||T->rchild){

printf(T)；)))if(T->lchildIIT->rchi1d){if(T->1child){BraNotationPrint(T—>lchi1d)：}e1seif(T—>rchild){

printf("#")；)printf；if(T一)rchiId){BraNotationPrint(T->rchiId);)elseif(P>1chiId){printf("#");)printf(T)；)))/*將一棵樹轉(zhuǎn)換為一個數(shù)組*/ArrayGetArrayFromTree(BBSTreeT){StalusfirstTime=TRUE;Arrayhead=NULL；ArrayNode*b=NULL;ArrayNode*q=NULL;if(T==NLJLL){printf("Thetreeisempiy!");)if(T!=NULL){LQueueQ；InitQueue_LQ(Q);BBSTreep=T；q=(Array)maHoc(sizeof(ArrayNode));q->data=p->da(a；if(firstTimc==TRUE){head=q;firstTime=FALSE；b=q；}e1se{b—>next=q;b=b->next;)EnQueue_LQ(Q,p);\vhilc(DcQucuc_LQ(Q?p)){if(p->1child!=NULL){q=(Array)mal1oc(sizcof(ArrayNode));q->data=p->lchild->data;

b->nexlq；b=b—>nextb->nexlq；EnQueue.LQ(Q,p->lchild);)if(p—>rchild!=NULL){q=(Array)ma1loc(sizeof(ArrayNode));q->data=p—>rchild->data；b->next=q;b=b->next;EnQueue_LQ(Q,p->rchild);})if(b!=NULL){?b->ncxt=NULL;。))returnhead；}/*將兩棵平衡二叉樹合并成一顆平衡二叉樹*/BBSTreeCombine2Tree(BBSTreeTl,BBSTreeT2){Status(aller=TRUE;Arraya=NULL;a=GelArrayFromTree(T2)；while(a!=NULL){tai1ertai1ertai1erTRUE;InsertAVL(T1,a—>data,taller);tai1erTRUE;a=a->next;}returnT1;)/*將一棵平衡二叉樹分裂成兩棵平衡二叉樹刃/*參數(shù)1：要進行分裂的樹參數(shù)2:分裂出來的小于等J--x的子樹。參數(shù)3：分裂出來的大于x的子樹。參數(shù)4：關鍵字x*/StatusSplitBBSTrcc(BBSTrceTtl,BBSTree&Tt2,BBSTrec&Tt3,intx){Arraya=NULL;S(atusta11er;a=GctArrayFromTree(Tt1);if(Ttl==NULL)returnFALSE;e1se(whiIe(a!=NULL){if(a->data<=x){tallcr=TRUE；InserlAVL(Tt2,a—>data,taller);a=a->next;tai1er=TRUE；InsertAVL(Tt3,a->data,ta1ler)；a=a->next;retuinTRUE；4.測試(1)建樹操作測試代碼:BBSTreeTl=NULL;printf(”請輸入樹的結點數(shù)據(jù)，按T結束：”)；Tl=MakeBBSTreeO;BraNotationPrint(Tl);//用括號表示法輸出return0;測試數(shù)據(jù)：123456測試結果:清輸入樹的結點數(shù)據(jù)，按-1結束：123456-14(2(1,3),5(#,6))T112Gl

(2)插入操作測試代碼:printf(”\n請輸入要插入的數(shù)據(jù)：");scanf("%dnz&rc);getchar();taller=TRUE;InsertAVL(Tlrm,taller);BraNotationPrint(Tl);//用括號表示法輸出測試數(shù)據(jù)：123456插入8測試結果：請輸入要插入的數(shù)據(jù)：84(2(1,3),6(5,8))測試結果：請輸入要插入的數(shù)據(jù)：84(2(1,3),6(5,8))T12向/、/、/Au1占Rsfol[J測試結果：請輸入要插入的數(shù)據(jù)：84(2(1,3),6(5,8))測試結果：請輸入要插入的數(shù)據(jù)：84(2(1,3),6(5,8))T12向/、/、/Au1占Rsfol[J測試數(shù)據(jù)：123456插入4測試數(shù)據(jù)：123456插入4測試結果:測試數(shù)據(jù)：123456插入4測試結果:清輸入要插入的數(shù)據(jù)：44(2(1,3),5(#,6))12GlT1汨品1I1「0I|3)0|I1「0I|3I1「0I|3)0|測試代碼:princf(”\n請輸入要刪除的數(shù)據(jù)：”)；scanf("%dn,&叫；getchar();shorter=TRUE;DeleteAVL(Tl,ir,shorter);BraNocationPrint(Tl);//用括號表示法輸出測試數(shù)據(jù)：123456刪除6測試結果：清輸入要刪除的數(shù)據(jù)：64(2(1,3),5)T1測試數(shù)據(jù)：123456刪除2測試結果：清輸入要刪除的數(shù)據(jù)：24(1(#,3),5(#,6))1.題目：平衡二叉樹ADTBBSTree{數(shù)據(jù)對象：D={aiIaiGllemSet,i=l,2,n,n^O}數(shù)據(jù)關系：Rl={<ai-1,ai>Iai-1,ai?,i=2,...,n)基本操作：BBSTreeMakeBBSTree()操作結果:創(chuàng)建好一棵樹返回:將創(chuàng)建好的樹返回StatusInsertAVL(BBSTree&T,RcdTypee,Status&ta11er)初始條件：樹T已存在，e存在，ta1ler為真操作結果:將e插入到T中返回:成功TRUE,失敗FALSEStatusDeleteAVL(BBSTree&tzRcdTypee,Status&shorter)初始條件：樹T已存在，e存在，shorter為真操作結果:將e從T中刪除返回：成功TRUE,失敗FALSEBBSTreeSearchAVL(BBSTreeTzRcdTypee)初始條件:樹T已存在，e存在操作結果:從T中找到e返回:以e為根節(jié)點的樹voidL_Rotate(BBSTree&p)初始條件:樹p存在T1、測試數(shù)據(jù)：123456刪除4測試結果：請輸入要刪除的數(shù)據(jù)：43(2(1,#),5(#,6))T1由/'W/[lE//?Gi(4)查找操作測試代碼:princf("\n請輸入要查找的數(shù)據(jù)：;scanf("%dM,&ir);getchar();shorter=TRUE;T1=SearchAVL(Tl,叫；BraNotationPrint(Tl);//用括號表示法輸出測試數(shù)據(jù)：123456查找5測試結果：請輸入要查找的數(shù)據(jù)：55(#,6)T1

rAi(5)輸出測試代碼:BBSTreeT=NULL;princf(R請輸入數(shù)據(jù)：");T=MakeBBSTree();printf(n\nT^J:n);BraNotationPrint(T);printf(n\nn);printf(=\n速歸先序遍歷輸出：");PreOrder_RecTraverse(T);printf(n\nn);printf(叭n菲遞歸先.序遍歷輸出：n);PreOrderTravese_I(T);printf(n\nM);printf(”\n速歸中序遍歷輸出：”)；InOrder_RecTraverse(T);printf(n\nn);print;￡(R\n菲遞歸中序遍歷輸出：w);InOrderTraverse_I(T);printf(;princf(”\n途歸后序遍歷輸出：”)；LastOrder_RecTraverse(T);printf(n\nn);prints(叭n菲遞歸后序遍歷輸出：");LastOrderTravese_I(T);printf(”\n");測試數(shù)據(jù)：123456測試結果:請輸入數(shù)據(jù)：123456789T為：4<2<1,3〉，6<5,8〈7,9〉〉）遞歸先序遍歷輸出：421365879非遞歸先序遍歷輸出：421365879遞歸中序遍歷輸出：123456789非遞歸中序遍歷輸出：123456789遞歸后序遍歷輸出：132579864IE遞歸后序遍歷輸出：132;7986.思考與小結在完畢平衡二叉樹實驗的過程中，所碰到的最大問題就是如何實現(xiàn)平衡二叉樹刪除結點的接口，由于課本沒有涉及到這個知識點,所以自己只能通過閱讀其他書籍和通過參考網(wǎng)上的資料來對這個過程有了進一步的理解。另一方面自己想了一個樹的括號表達法來將一棵樹打印出來，這對于一棵樹的表達是挺有用的?？偟膩碚f,平衡二叉樹這個知識點涉及到的算法大約就是添加結點,刪除結點，查找結點這三個方面，而其他的接口都是以這三個為基礎,實現(xiàn)進一步的拓展。.源代碼/*(1)根據(jù)輸入字符串創(chuàng)建一棵平衡二叉樹BBSTreeMakeBBSTree();(2)平衡二叉樹插入元素操作StatusInser(AVL(BBSTree&T,RcdTypee,Status&taller)；(3)層次遍歷輸出二叉樹voidLevelOrederTraverse_Print(BBSTreeT);(4)括號表達法輸出二叉樹voidBraNolationPrinl(BBSTreeT);(5)平衡二叉樹刪除元素操作StatusDe1etcAVL(BBSTrce&t,RcdTypee,Status&shorter);(6)求平衡二叉樹的深度ntBBSTreeDepth(BBSTrceT);(7)互換所有結點的左右子樹voidExchangcSubTree(BBSTree&T)(8)遞歸先序遍歷StatusPreOrder_RecTraverse(BBSTreeT);(9)遞歸中序遍歷StatusInOrder_RecTraverse(BBSTreeT)；(10)遞歸后序遍歷StatusLastOrder_RecTraverse(BBSTreeT);(11)非遞歸先序遍歷voidPreOrderTraverse_I(BBSTreeT);(12)非遞歸中序遍歷voidInOrderTraverse_I(BBSTreeT);(13)非遞歸后序遍歷voidLaslOrderTraverse—I(BBSTreeT);*/#include<stdio.h>#incIude<malloc.h>#defineOVERFLOW-1#deflneOK1#defineERROROdefineTRUE1defineFALSEOdefineLH+1〃左高defineEH0〃等高defineRH-1//右高typedefintRcdType；typedefintStatus;/*存放輸入數(shù)據(jù)的數(shù)組結構體*/typedefstructArrayNode{RcdTypedata;ArrayNode*next；}ArrayNode,*Array;/*平衡二又樹結構體*/typedefstructBBSTNode!RcdTypedata;intbf;BBSTNodc*1chi1d,*rchild;}BBSTNode,*BBSTree；/*鏈隊列結構體*/typedefstructLQNode{BBSTreeelem；structLQNode*next;}LQNode,*QucuePtr；/*隊列結點結構體*/typedefstruct{QueuePtrfront;QueuePtrrear；}LQueue；/*棧結點結構體字/typedefstructLSNode{BBSTreedata;〃數(shù)據(jù)域structLSNode*next;〃指針域}LSNode,*LStack;〃結點和鏈棧類型/次初始化一個鏈棧*/StatusInitStack_LS(LStack&S){S=NULL；)/文進校操作*/StatusPush_LS(LStack&S,BBSTreee){LSNode*t;t=(LSNode*)malloc(sizeof(LSNode));if(NULL==t)returnOVERFLOW;t->data=e；t->next=S;S=t;returnOK;)/*出棧操作*/StatusPop_LS(LS(ack&S,BBSTree&e){LSNode*t；if(S==NULL)returnERROR;t=s；e=t->data;S=S->next;returnOK;)/*獲得棧頂元素力StatusGetTop_LS(LStackS,BBSTree&e){if(NULL==S)returnERROR;else{e=S->data;returnOK;))/*判斷棧是否為空*/StatusStackEmpty_LS(LStackS){if(NULL==S)returnTRUE;e1sereturnFALSE;)/*初始化鏈隊列*/voidInitQueue_LQ(LQueue&Q){Q.front=NULL;Q.rear=NULL;/*鏈隊列進棧操作*/StatusEnQueue_LQ(LQueue&Q,BBSTreee){LQNode*p；p=(LQNode*)malloc(sizeof(LQNode));if(NULL==p)returnOVERFLOW；p->elem=e;p—>next=NULL;if(NULL==Q.fronl)Q.front=p；//e插入空隊列elseQ.rear—>next=p;插入非空隊列Q.rear=p;〃隊尾指針指向新的隊尾returnOK；)/*鏈隊列出棧操作*/StatusDeQueue_LQ(LQueue&Q,BBSTree&e){LQNode*p;if(NULL==Q.front)returnERROR;p=Q.front；e=p->e1em；Q.front=p->next;if(Q.rear==p)Q.rear=NULL;free(p);rcturnOK：/*求平衡二叉樹的深度*/incBBSTreeDepth(BBSTreeT){intdepthLeft,depthRight;if(NULL==T)return0;else(depthLeft=BBSTreeDepth(T->lchild)；depthRight=BBSTreeDepth(T->rchild);return1+(dcpthLeft>depthRight?depthLcft:dcpthRight);})互換二叉樹所有結點的左右子樹*/voidExchangeSubTree(BBSTree&T){BBSTrectemp;if(NULL!=T){ExchangeSubTree(T->lchild);〃使用遞歸互換左子樹ExchangeSubTree(T->rchild);//使用遞歸互換右子樹if((T->1child!=NULL)||(T->rchild!=NULL)){//假如T的子樹有一個不為空，則互換左右子樹temp=T->1child;T—>lchild=T->rchild;T->rchild—temp；操作結果:對P左旋操作voidR_Rotate(BBSTree&p)初始條件：樹p存在操作結果:對p右旋操作voidLeftBalance(BBSTree&T)初始條件：樹T存在操作結果:對T左平衡操作voidRightBalance(BBSTree&T)初始條件：樹T存在操作結果:對"T右平衡操作voidExchangeSubTree(BBSTree&T)初始條件：樹T存在操作結果:對T所有左右孩子互換intBBSTreeDepth(BBSTreeT)初始條件:樹T已存在操作結果:求樹T的深度返1可：樹的深度BBSTreeCombine2Tree(BBsTreeT1,BBSTreeT2)初始條件:樹T1和T2已存在操作結果:將T1和T2合并返回:合并后的樹StatusSplitBBSTree(BBSTreeTtl,BBSTree&Tt2,oooBBSTree&Tt3,intx)初始條件:樹Tt1,Tt2,Tt3已存在,x存在操作結果：將Tt1分裂成Tt2和Tt3/*左旋調(diào)整*/voidL_Rotate(BBSTree&P){BBSTreerc=p->rchiId;p->rchild=rc->lchild；rc—>lchiId=p;p=rc;I/*右旋調(diào)整*/voidR_Ro(ate(BBSTree&p){BBSTree1c=p->lchiId;p->lchild=lc->rchild;lc->rchild=p;P=lc;I/*左平衡解決操作*/voidLeftBa1ance(BBSTree&T){BBSTree1c,rd;1c=T->lchiId；switch(lc—>bf){caseLH：T->bf=lc->bf=EH;R_Rotate(T)；break;caseRH:rd=Ic->rchild;switch(rd->bf){caseLH：T—>bf=RH;1c->bf=EH;break;caseEH:T->bf=1c->bf=EH；break；caseRH：T->bf=EH;1c->bf=LH;break;}rd->bf=EH：L_Rotate(T->1child);R_Rotate(T);break;})/*右平衡解決操作*/voidRightBalance(BBSTree&T){BBSTrecrd,1c：rd=T->rchiId;switch(rd->bf)(caseRH：T->bf=rd—>bf=EH；L_Rotate(T);break;caseLH:lc=rd->lchiId；switch(lc->bf){cascRH:T->bf=LH；rd->bf=EH;break：caseEH:T->bf=rd—>bf=EH;break;caseLH：T->bf=EH：rd->bf=RH;break;lc->bf=EH：R_Rotate(T->rchiId);L_Rotate(T);break：)}/*平衡二叉樹的插入操作*/StatusInsertAVL(BBSTree&T,RcdTypee.Status&(a1ler){if(NULL==T){T=(BBSTree)ma1loc(sizeof(BBSTNode));T->data=e；T->bf=EH：T->1chi1d=NULL;T->rchild=NULL;Jelseif(e==T->data)(//書中已存在和e相等的結點ta11er=FALSE;returnFALSE：}e1seif(e<T->data){if(FALSE==InsertAVL(T->1chi1d,e,ta1ler))returnFALSE;if(TRUE==talier){switch(T->bf){caseLH:LcftBalance(T);tai1er=FALSE;break;caseEH:T->bf=LH;taller=TRUE;break;caseRH:T->bf=EH;taller=FALSE;break;}else{if(FALSE==InsertAVL(T->rchild.e,tai1er))returnFALSE;if(TRUE==taller){switch(T->bf){caseLH：T->bf=EH；ta11er=FALSE;break;caseEH：T->bf=RH;tal1er=TRUE;break;caseRH：RightBa1ance(T)；tallcr=FALSE；break;})}relurnTRUE;I/*平衡二叉樹的刪除操作力StatusDe1eteAVL(BBSTree&t,RedTypee,Status&shorter){//當被刪結點是有兩個孩子，且其前驅(qū)結點是左孩子時，ug=Istaticinttag=0：if(t==NULL){returnFALSE;〃假如不存在元素，返回失敗Jelseif(e==t->data){BBSTNode*q=NULL;〃假如該結點只有一個孩子，則將自子樹取代該結點if(t->lchi1d==NULL){

q=t;t->rchild;free(q);shorter=TRUE;)elseif(t->rchi1d==NULL){Q=t;t=t->lchild;frcc(q);shorter=TRUE;)//假如被刪結點有兩個孩子，則找到結點的前驅(qū)結點，//并將前驅(qū)結點的值賦給該結點，然后刪除前驅(qū)結點else{q=t->lchi1d;while(q->rchild){q=q->rchild;)t->data=q->data;if(t->lchild—>data==q->data){tag=1；}DeleteAVL(t->lchi1d,q->data,shorter);if(tag==1){BBSTreer=t->rchild；if(NULL==r)t->bf=0;eIse{caseEH:t->bf=-1;break;default:RightBa1ance(t);break；)))}}clseif(c<t->data){//左子樹中繼續(xù)查找if(!De1eteAVL(t->lchild,e,shorter)){returnFALSE；I//刪除完結點之后，調(diào)整結點的平衡因子if(shorler&&(tag==0)){switch(t->bf){cascLH:t->bf=EH;shorter=TRUE；break;caseEH：t->bf=RH；shorter=FALSE;break；〃假如本來就是右子樹較高，刪除之后就不平衡，需要做右平衡操作caseRH：RightBalance(t);//右平衡解決if(t->rchild->bf==EH)shorter=FALSE；elseshorter=TRUE；break;)1seif(e>t->data){〃右子樹中繼續(xù)查找if(!DeleteAVL(t->rchild,e,shortcr)){returnFALSE;}〃刪除完結點之后,調(diào)整結點的平衡因子if(shorter&&(tag==0)){swiIch(t->bf){caseLH:LeftBalancc(t)；〃左平衡解決if(t->lchild->bf==EH)〃注意這里，畫圖思考一下shorter=FALSE;elseshorter=TRUE；break；caseEH:t->bf=LH;shorter=FALSE;break;caseRH：t->bf=EH;shorter=TRUE；break;)if(tag==l){intdepthLeft=BBSTreeDepth(t->1child);intdepthRight=BBSTreeDepth(t->rchild);t->bf=depthLeft-dcpthRight；)}returnTRUE；)/*平衡二叉樹的查找操作*/BBSTreeSearchAVL(BBSTreeT,RcdTypce){if(T==NULL)returnNULL；if(e==T->data){returnT;}elseif(e>T->data){retumSearchAVL(T->rchild,e)；(else(returnSearchAVL(l^>lchild,e);/*獲取輸入存到數(shù)組a*/ArrayGellnpulToArray(){Arrayhead,p,q;chark;head=p=q=NULL;intm;if(k!='\n,){scanf(u%d",&m)；p=(ArrayNode*)mal1oc(sizeof(ArrayNode))；head=p；p->data=m;k=getchar();)while(k!=*\nz){scanfC'%d",&m);q=(ArrayNode*)mal1oc(sizeof(AirayNode));q->data=m；p->next=q；p=p->next;k=getchar();}if(p!=NULL){p->next=NULL;returnhead；//返回存放數(shù)據(jù)的頭指針/*根據(jù)輸入的字符串建一棵平衡二又樹*/BBSTreeMakeBBSTree(){inti=();Statustaller=TRUE;BBSTreeT=NULL;Arraya；a=GctlnputToArray();while(a!=NULL){tai1er=TRUE;InsertAVL(T,a—>data,talier)；a=a->next;)returnT;I/*遞歸先序遍歷*/SlatusPreOrder_RecTraverse(BBSTreeT){if(NULL==T)returnOK；printf("%d",T->data);PreOrder_RecTraverse(T->lchi1d);PreOrder_RecTraverse(T->rchild);}/*遞歸中序遍歷*/StatusInOrdcr_RccTraverse(BBSTrceT){if(T->IchiId)InOrder_RecTraverse(T->lchi1d);返回：以e為根節(jié)點的樹StatusPreOrder_RecTraverse(BBSTreeT)初始條件:樹T已存在操作結果：對樹T進行遞歸先序遍歷輸出返回:成功TRUE失敗FALSEStatusInOrder_RecTraverse(BBSTreeT)初始條件：樹T已存在操作結果：對樹T進行遞歸中序遍歷輸出返回：成功TRUE失敗FALSEStatusLastOrder_RecTraverse(BBSTreeT)初始條件：樹T已存在操作結果：對樹T進行遞歸后序遍歷輸出返回：成功TRUE失敗FALSEvoidPre0rderTravese_I(BBSTreeT)初始條件:樹T已存在操作結果:對樹T進行非遞歸先序遍歷輸出voidInOrderTraverse_I(BBSTreeT)初始條件:樹T已存在操作結果：對樹T進行非遞歸中序遍歷輸出voidLastOrderTravese_l(BBSTreeT)初始條件：樹T已存在操作結果：對樹T進行非遞歸后序遍歷輸出voidLevelOrederTraverse_Print(BBSTreeT)初始條件:樹T已存在操作結果:對樹T進行非遞歸層次遍歷輸出voidBraNotationPrint(BBSTreeT)printf(u%d",T->data);if(T->rchild)InOrder_RecTraverse(T->rchiId)；}/*遞歸后序遍歷*/StatusLasiOrder_RccTraverse(BBSTreeT){if(T->lchi1d)LastOrdcr_RccTraverse(T->lchild)；if(T->rchild)LastOrder_RecTraverse(T->rchiId);printf("%d",T->data)；}/*找到最左結點*/BBSTreeGoFarLeft(BBSTreeT,LStack&S){if(NULL==T)returnNULL;while(T->lchi1d!=NULL){Push_LS(S>T)；T=T->lchi1d;)returnT;)/*非遞歸中序遍歷*/voidInOrderTraverse.I(BBSTreeT){LStackS；

InitStack_LS(S);BESTreep=NULL;p=GoFarLeft(T,S);while(p!=NULL){printf("%d",p->data);if(p->rchild!=NULL){p=GoFarLcft(p->rchi1d,S);)elseif(StackEmpty_LS(S)!=TRUE)Pop_LS(S,p);eIsep=NULL;}BBSTrccVisitFarLeft(BBSTrccT,if(NULL==T)returnNULLBBSTrccVisitFarLeft(BBSTrccT,if(NULL==T)returnNULL；printf("%d",T->data);while(T->lchild!=NULL){Push_LS(S,T)；T=T->lchild;printf("%d",T->data)；)returnT;BBSTrccVisitFarLeft(BBSTrccT,if(NULL==T)returnNULL；printf("%d",T->data);while(T->lchild!=NULL){BBSTrccVisitFarLeft(BBSTrccT,if(NULL==T)returnNULL；printf("%d",T->data);while(T->lchild!=NULL){Push_LS(S,T)；T=T->lchild;printf("%d",T->data)；)returnT;LStack&S){〃假如T為空，則返回空〃先序，先讀取結點數(shù)據(jù)〃入棧//遍歷下一個左子樹〃下一個結點的讀取數(shù)據(jù)voidPreOrderTravese_I(BBSTreeT){LStackS;InitStack—LS(S);BBSTreep;P=VisitFarLeft(T,S);〃先將左邊的數(shù)據(jù)先序讀取while(p!=NULL){if(p->rchild!=NULL)〃假如最左下結點的右子樹不為空p=VisitFarLeft(p—>rchi1d,S);//執(zhí)行遍歷該結點的左子樹elseif(StackEmpty_LS(S)!=TRUE)Pop_LS(S,P);//假如S不為空棧,出校elsep=NULL;〃假如為空棧，P賦予空/*非遞歸后序遍歷*/voidLast0rderTravese_I(BBSTreeroot){BBSTreep=root；BBSTreestack[3O];intnum=0;BBSTreehave_visited=NULL；while(NULL!=pI|num>0){while(NULL!=p){stack[num++]=p;p=p->lchi1d：Ip=stack[num-l];if(NULL==p—>rchild||have_visited==p->rchild){printf("%d",p->data);num--：have_visited=p;p=NULL;)else{p=p->rchild；)}printf(°\n")；)/*非遞歸層次遍歷輸出一棵二叉樹*/voidLevel0redcrTraverse_Print(BBSTreeT){if(T==NULL){printf(*'Thetreeisempty!");)if(T!=NULL){LQueueQ;Ini(Queue—LQ(Q)；BBSTrccp=T;Printf("%d",p->data);EnQucuc_LQ(Q,p);whi1e(DeQueue_LQ(Q.p)){if(p->1child!=NULL){printf("%d",p->lchiId—〉data);EnQueue_LQ(Q,p—>lchi1d);if(p->rchild!=NULL){printf("%d",p->rchild->data);EnQueue_LQ(Q,p—>rchild);/*括號表達法輸出平衡二叉樹*/voidBraNotationPrint(BBSTreeT){if(NULL==T){Printf("空！”)；}else{if(T!=NULL){if(T!=NULL){printf("%i",T->data);if(T->lchild||T->rchi1d){printf("(")：if(T->lchild||T->rchild){if(T->1child){BraNotationPrint(T->lchiId);}elseif(T->rchiId){printfC'#");)printf(",”)：if(T->rchild){BraNotationPrint(T->rchild)；}eIseif(T—>1chi1d){print;}printf(")")；})I/*將一棵樹轉(zhuǎn)換為一個數(shù)組*/ArrayGetArrayFromTree(BBSTreeT){StatusfirstTime=TRUE；Arrayhead=NULL;ArrayNode*b=NULL;ArrayNodc*q=NULL；if(T==NULL){printf("Thetreeisempty!M);)if(T!=NULL){LQueueQ;InitQueue_LQ(Q);BBSTreep=T;q=(Array)malloc(sizeof(ArrayNode))；q->data=p->data;if(firstTime==TRUE){head=q;firstTime=FALSE;b=q;}e1se{b->next=q;b=b->next;}EnQueue_LQ(Q,p)；while(DeQueue_LQ(Q,p)){if(p->ichild!=NULL){q=(Array)ma11oc(sizeof(ArrayNode))；

q->data=p—>1child->data;b->next=q；b=b->next;EnQueue_LQ(Q,p->lchiId)；)if(p->rchi1d!=NULL){q=(Array)mal1oc(sizeof(ArrayNode));q—>data=p->rchild->data;b->next=q;b=b->next；EnQueue_LQ(Q.p—>rchild);if(b!=NULL){ab->next=NULL;))returnhead；I/*將兩棵平衡二又樹合并成一顆平衡二叉樹*/BBSTreeCombine2Tree(BBSTreeTl,BBSTreeT2)(Statustaller=TRUE;Arraya=NULL;a=GetArrayFromTrec(T2);while(a!=NULL){tailer=TRUE；InsertAVL(T1,a->data,la11er);a=a—>next;IreturnT1;)/*將一棵平衡二叉樹分裂成兩棵平衡二叉樹火//*。參數(shù)1：要進行分裂的樹參數(shù)2:分裂出來的小于等于x的子樹。參數(shù)3：分裂出來的大于x的子樹參數(shù)4：關鍵字x*/StatusSplitBBSTree(BBSTreeTt1,BBSTree&Tt2,BBSTree&Tt3?intx)