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

^.实验报告课程名称数据结构实验学院计算机学院专业班级计科9班学号学生姓名指导教师苏庆2015年7月6日^.^.1.题目:平衡二叉树ADTBBSTree{数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{ai-1,ai|ai-1,ai∈D,i=2,...,n}基本操作：BBSTreeMakeBBSTree()操作结果：创建好一棵树返回：将创建好的树返回StatusInsertAVL(BBSTree&T,RcdTypee,Status&taller)初始条件：树T已存在，e存在，taller为真操作结果：将e插入到T中返回：成功TRUE，失败FALSEStatusDeleteAVL(BBSTree&t,RcdTypee,Status&shorter)初始条件：树T已存在，e存在，shorter为真操作结果：将e从T中删除返回：成功TRUE，失败FALSEBBSTreeSearchAVL(BBSTreeT,RcdTypee)初始条件：树T已存在，e存在操作结果：从T中找到e返回：以e为根节点的树voidL_Rotate(BBSTree&p)初始条件：树p存在操作结果：对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的深度返回：树的深度BBSTreeCombine2Tree(BBSTreeT1,BBSTreeT2)初始条件：树T1和T2已存在^.操作结果：将T1和T2合并返回：合并后的树StatusSplitBBSTree(BBSTreeTt1,BBSTree&Tt2,BBSTree&Tt3,intx)初始条件：树Tt1，Tt2，Tt3已存在，x存在操作结果：将Tt1分裂成Tt2和Tt3返回：以e为根节点的树StatusPreOrder_RecTraverse(BBSTreeT)初始条件：树T已存在操作结果：对树T进行递归先序遍历输出返回：成功TRUE失败FALSEStatusInOrder_RecTraverse(BBSTreeT)初始条件：树T已存在操作结果：对树T进行递归中序遍历输出返回：成功TRUE失败FALSEStatusLastOrder_RecTraverse(BBSTreeT)初始条件：树T已存在操作结果：对树T进行递归后序遍历输出返回：成功TRUE失败FALSEvoidPreOrderTravese_I(BBSTreeT)初始条件：树T已存在操作结果：对树T进行非递归先序遍历输出voidInOrderTraverse_I(BBSTreeT)初始条件：树T已存在操作结果：对树T进行非递归中序遍历输出voidLastOrderTravese_I(BBSTreeT)初始条件：树T已存在操作结果：对树T进行非递归后序遍历输出voidLevelOrederTraverse_Print(BBSTreeT)初始条件：树T已存在操作结果：对树T进行非递归层次遍历输出voidBraNotationPrint(BBSTreeT)初始条件：树T已存在操作结果：对树T用括号表示法输出}ADTBBSTree2.存储结构定义#includestdio.h#includemalloc.h#defineOVERFLOW-1#defineOK1^.#defineERROR0#defineTRUE1#defineFALSE0#defineLH+1//左高#defineEH0//等高#defineRH-1//右高typedefintRcdType;typedefintStatus;/*平衡二叉树结构体*/typedefstructBBSTNode{RcdTypedata;intbf;BBSTNode*lchild,*rchild;}BBSTNode,*BBSTree;3.算法设计/*求平衡二叉树的深度*/intBBSTreeDepth(BBSTreeT){intdepthLeft,depthRight;if(NULL==T)return0;else{depthLeft=BBSTreeDepth(T-lchild);depthRight=BBSTreeDepth(T-rchild);return1+(depthLeftdepthRight?depthLeft:depthRight);}}/*交换二叉树所有结点的左右子树*/voidExchangeSubTree(BBSTree&T){BBSTreetemp;if(NULL!=T){ExchangeSubTree(T-lchild);//使用递归交换左子树ExchangeSubTree(T-rchild);//使用递归交换右子树if((T-lchild!=NULL)||(T-rchild!=NULL)){//如果T的子树有一个不为空，则交换左右子树temp=T-lchild;T-lchild=T-rchild;T-rchild=temp;}^.}}/*左旋调整*/voidL_Rotate(BBSTree&p){BBSTreerc=p-rchild;p-rchild=rc-lchild;rc-lchild=p;p=rc;}/*右旋调整*/voidR_Rotate(BBSTree&p){BBSTreelc=p-lchild;p-lchild=lc-rchild;lc-rchild=p;p=lc;}/*左平衡处理操作*/voidLeftBalance(BBSTree&T){BBSTreelc,rd;lc=T-lchild;switch(lc-bf){caseLH:T-bf=lc-bf=EH;R_Rotate(T);break;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);break;}}/*右平衡处理操作*/voidRightBalance(BBSTree&T){^.BBSTreerd,lc;rd=T-rchild;switch(rd-bf){caseRH:T-bf=rd-bf=EH;L_Rotate(T);break;caseLH:lc=rd-lchild;switch(lc-bf){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(BBSTree&T,RcdTypee,Status&taller){if(NULL==T){T=(BBSTree)malloc(sizeof(BBSTNode));T-data=e;T-bf=EH;T-lchild=NULL;T-rchild=NULL;}elseif(e==T-data){//书中已存在和e相等的结点taller=FALSE;returnFALSE;}elseif(eT-data){if(FALSE==InsertAVL(T-lchild,e,taller))returnFALSE;if(TRUE==taller){switch(T-bf){caseLH:LeftBalance(T);taller=FALSE;break;caseEH:T-bf=LH;taller=TRUE;break;caseRH:T-bf=EH;taller=FALSE;break;}}}else{if(FALSE==InsertAVL(T-rchild,e,taller))returnFALSE;if(TRUE==taller){switch(T-bf){^.caseLH:T-bf=EH;taller=FALSE;break;caseEH:T-bf=RH;taller=TRUE;break;caseRH:RightBalance(T);taller=FALSE;break;}}}returnTRUE;}/*平衡二叉树的删除操作*/StatusDeleteAVL(BBSTree&t,RcdTypee,Status&shorter){//当被删结点是有两个孩子，且其前驱结点是左孩子时，tag=1staticinttag=0;if(t==NULL){returnFALSE;//如果不存在元素，返回失败}elseif(e==t-data){BBSTNode*q=NULL;//如果该结点只有一个孩子，则将自子树取代该结点if(t-lchild==NULL){q=t;t=t-rchild;free(q);shorter=TRUE;}elseif(t-rchild==NULL){q=t;t=t-lchild;free(q);shorter=TRUE;}//如果被删结点有两个孩子，则找到结点的前驱结点，//并将前驱结点的值赋给该结点，然后删除前驱结点else{q=t-lchild;while(q-rchild){q=q-rchild;}t-data=q-data;if(t-lchild-data==q-data){tag=1;}DeleteAVL(t-lchild,q-data,shorter);if(tag==1){BBSTreer=t-rchild;^.if(NULL==r)t-bf=0;else{switch(r-bf){caseEH:t-bf=-1;break;default:RightBalance(t);break;}}}}}elseif(et-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;elseshorter=TRUE;break;}}}elseif(et-data){//右子树中继续查找if(!DeleteAVL(t-rchild,e,shorter)){returnFALSE;}//删除完结点之后，调整结点的平衡因子if(shorter&&(tag==0)){switch(t-bf){caseLH:LeftBalance(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==1){i