2023年广工数据结构实验报告平衡二叉树

度劣与招实验报告课程名称数据结构实验学院计算机学院专业班级计科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){〃当被删结点是有两个孩子，且其前驱结点是左孩子时,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;}〃假如被删结点有两个孩子，则找到结点的前驱结点,〃并将前驱结点的值赋给该结点，然后删除前驱结点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){//左子树中继续查找if(!DeleteAVL(t->lchild,e,shorter)){returnFALSE；}〃删除完结点之后，调整结点的平衡因子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){〃右子树中继续查找if(!De1eteAVL(t->rchild,e,shorter)){returnFALSE;)〃删除完结点之后，调整结点的平衡因子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);)/*获取输入存到数组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:〃返回存放数据的头指针)/*根据输入的字符串建一棵平衡二叉树文/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)；〃先序，先读取结点数据while(T->lchild!=NULL){Push_LS(S,T);//入栈T=T->1child;//遍历下一个左子树printf("%dT->data);〃下一个结点的读取数据)rcturnT;}/*非递归先序遍历*/voidPreOrderTravese—I(BBSTreeT){LStackS；InitStack_LS(S);BBSTreep;p=VisitFarLeft(T,S);//先将左边的数据先序读取while(p!=NULL){if(P->rchi1d!=NULL)//假如最左下结点的右子树不为空p=VisitFarLeft(p->rchild,S);//执行遍历该结点的左子树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)；)))/*将一棵树转换为一个数组*/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;)/*将一棵平衡二叉树分裂成两棵平衡二叉树刃/*参数1：要进行分裂的树参数2:分裂出来的小于等J--x的子树。参数3：分裂出来的大于x的子树。参数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(”请输入树的结点数据，按T结束：”)；Tl=MakeBBSTreeO;BraNotationPrint(Tl);//用括号表示法输出return0;测试数据：123456测试结果:清输入树的结点数据，按-1结束：123456-14(2(1,3),5(#,6))T112Gl

(2)插入操作测试代码:printf(”\n请输入要插入的数据：");scanf("%dnz&rc);getchar();taller=TRUE;InsertAVL(Tlrm,taller);BraNotationPrint(Tl);//用括号表示法输出测试数据：123456插入8测试结果：请输入要插入的数据：84(2(1,3),6(5,8))测试结果：请输入要插入的数据：84(2(1,3),6(5,8))T12向/、/、/Au1占Rsfol[J测试结果：请输入要插入的数据：84(2(1,3),6(5,8))测试结果：请输入要插入的数据：84(2(1,3),6(5,8))T12向/、/、/Au1占Rsfol[J测试数据：123456插入4测试数据：123456插入4测试结果:测试数据：123456插入4测试结果:清输入要插入的数据：44(2(1,3),5(#,6))12GlT1汨品1I1「0I|3)0|I1「0I|3I1「0I|3)0|测试代码:princf(”\n请输入要删除的数据：”)；scanf("%dn,&叫；getchar();shorter=TRUE;DeleteAVL(Tl,ir,shorter);BraNocationPrint(Tl);//用括号表示法输出测试数据：123456删除6测试结果：清输入要删除的数据：64(2(1,3),5)T1测试数据：123456删除2测试结果：清输入要删除的数据：24(1(#,3),5(#,6))1.题目：平衡二叉树ADTBBSTree{数据对象：D={aiIaiGllemSet,i=l,2,n,n^O}数据关系：Rl={<ai-1,ai>Iai-1,ai®,i=2,...,n)基本操作：BBSTreeMakeBBSTree()操作结果:创建好一棵树返回:将创建好的树返回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为根节点的树voidL_Rotate(BBSTree&p)初始条件:树p存在T1、测试数据：123456删除4测试结果：请输入要删除的数据：43(2(1,#),5(#,6))T1由/'W/[lE//♦Gi(4)查找操作测试代码:princf("\n请输入要查找的数据：;scanf("%dM,&ir);getchar();shorter=TRUE;T1=SearchAVL(Tl,叫；BraNotationPrint(Tl);//用括号表示法输出测试数据：123456查找5测试结果：请输入要查找的数据：55(#,6)T1

rAi(5)输出测试代码:BBSTreeT=NULL;princf(R请输入数据：");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");测试数据：123456测试结果:请输入数据：123456789T为：4<2<1,3〉，6<5,8〈7,9〉〉）递归先序遍历输出：421365879非递归先序遍历输出：421365879递归中序遍历输出：123456789非递归中序遍历输出：123456789递归后序遍历输出：132579864IE递归后序遍历输出：132;7986.思考与小结在完毕平衡二叉树实验的过程中，所碰到的最大问题就是如何实现平衡二叉树删除结点的接口，由于课本没有涉及到这个知识点,所以自己只能通过阅读其他书籍和通过参考网上的资料来对这个过程有了进一步的理解。另一方面自己想了一个树的括号表达法来将一棵树打印出来，这对于一棵树的表达是挺有用的。总的来说,平衡二叉树这个知识点涉及到的算法大约就是添加结点,删除结点，查找结点这三个方面，而其他的接口都是以这三个为基础,实现进一步的拓展。.源代码/*(1)根据输入字符串创建一棵平衡二叉树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;/*存放输入数据的数组结构体*/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;〃数据域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/*左旋调整*/voidL_Rotate(BBSTree&P){BBSTreerc=p->rchiId;p->rchild=rc->lchild；rc—>lchiId=p;p=rc;I/*右旋调整*/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){//当被删结点是有两个孩子，且其前驱结点是左孩子时，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;)//假如被删结点有两个孩子，则找到结点的前驱结点，//并将前驱结点的值赋给该结点，然后删除前驱结点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){//左子树中继续查找if(!De1eteAVL(t->lchild,e,shorter)){returnFALSE；I//删除完结点之后，调整结点的平衡因子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){〃右子树中继续查找if(!DeleteAVL(t->rchild,e,shortcr)){returnFALSE;}〃删除完结点之后,调整结点的平衡因子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);/*获取输入存到数组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；//返回存放数据的头指针/*根据输入的字符串建一棵平衡二又树*/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为根节点的树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为空，则返回空〃先序，先读取结点数据〃入栈//遍历下一个左子树〃下一个结点的读取数据voidPreOrderTravese_I(BBSTreeT){LStackS;InitStack—LS(S);BBSTreep;P=VisitFarLeft(T,S);〃先将左边的数据先序读取while(p!=NULL){if(p->rchild!=NULL)〃假如最左下结点的右子树不为空p=VisitFarLeft(p—>rchi1d,S);//执行遍历该结点的左子树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/*将一棵树转换为一个数组*/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;)/*将一棵平衡二叉树分裂成两棵平衡二叉树火//*。参数1：要进行分裂的树参数2:分裂出来的小于等于x的子树。参数3：分裂出来的大于x的子树参数4：关键字x*/StatusSplitBBSTree(BBSTreeTt1,BBSTree&Tt2,BBSTree&Tt3»intx)