数据结构实验-实现平衡二叉排序树的各种算法

附件A：实验报告封面华南农业大学信息学院综合性、设计性实验起止日期:2011秋学院信息学院专业班级11软件工程3班学号201130690325姓名徐远辉实验题目实现平衡二叉排序树的各种算法自我评价项目算法设计独立完成情况算法熟练程度测试通过成功失败独立帮助掌握了解不懂插入新结点√√√√前序、中序、后序遍历二叉树〔递归〕√√√√前序、中序、后序遍历的非递归算法√√√√层次遍历二叉树√√√√在二叉树中查找给定关键字√√√√交换各结点的左右子树√√√√求二叉树的深度√√√√叶子结点数√√√√删除某结点√√√√A---------完成实验要求的全部功能并运行通过，算法有一定的新意，程序代码符合书写标准，实验报告表达清晰完整，有详尽的分析和总结。B---------完成实验要求的全部功能，程序代码符合书写标准，实验报告表达清晰完整。C---------完成实验要求的大局部功能，实验报告良好。D---------未按时完成实验，或者抄袭。成绩A教师签名：杨秋妹实验题目：实现平衡二叉排序树的各种算法班级：11级软件工程3班姓名：徐远辉学号：201130690325完成日期：2012-11-18分析题目要求答：题目主要是要编写一个程序，用函数实现如下平衡二叉排序树算法：〔1〕插入新结点〔2〕前序、中序、后序遍历二叉树〔递归〕〔3〕前序、中序、后序遍历的非递归算法〔4〕层次遍历二叉树〔5〕在二叉树中查找给定关键字(函数返回值为成功1,失败0)〔6〕交换各结点的左右子树〔7〕求二叉树的深度〔8〕叶子结点数〔9〕删除某结点以下几点是在程序中的规定：各个函数命名，包含的参数，返回值类型//要用到的结构体和typedef重命名类型//平衡二叉排序树的结构typedefstructTnode{ ElemTypedata; structTnode*lchild,*rchild; intheight;//以该节点为根的子树的高度}BBTnode,*BBTree;//栈定义typedefstruct{ BBTree*base,*top;//栈指针成员 intinitsize;//栈初始长度}Stack;//队列定义typedefstruct{ BBTree*front,*rear;//队列指针成员 intInitSize;//栈初始长度}Queue;constintMAXSIZE=100;//用const比用#define宏定义要好constintOK=1;//用const比用#define宏定义要好constintERROR=0;//用const比用#define宏定义要好typedefintstatus;//用status表示函数返回值状态typedefintElemType;//用ElemType表示元素类型typedefBBTreePosition;//表示节点在树中的位置//要用到的函数如下statusInsertBBT(BBTree&T,ElemTypee);//插入新结点statusCreatStack(Stack&S);//建立栈statusCreatQueue(Queue&Q);//建立队列statusFirstViewRoot(BBTreeT);//递归前序遍历statusMiddleViewRoot(BBTreeT);//递归中序遍历statusLastViewRoot(BBTreeT);//递归后序遍历statusViewAll(BBTreeT);//当经常要遍历时可以用来减少代码量statusNonFirstView(BBTreeT,StackS);//非递归前序遍历statusNonMiddleView(BBTreeT,StackS);//非递归中序遍历statusNonLastView(BBTreeT,StackS);//非递归后序遍历statusNonViewAll(BBTreeT,StackS);//当经常要遍历时可以用来减少代码量statusLevelView(BBTreeT,QueueQ);//层次遍历statusFindKeyword(BBTreeT,ElemTypee);//在二叉树中查找给定关键字(函数返回值为成功1,失败0)statusSwapSubtree(BBTreeT);//交换各结点的左右子树intDeepOfTree(BBTreeT);//求二叉树的深度intTotalNodeNumber(BBTreeT);//总的结点数intLeafNodeNumber(BBTreeT);//叶子结点数statusDeleteBBT(BBTree&T,ElemTypee);//删除某结点//以下函数是为了实现我的平衡树算法而设计PositionFindMin(BBTreeT);//找最小的ElementintHeight(BBTreeT);/*求树的高度(以空树为-1，并定义树的高度为树的层次数减1，如只有一个节点的树的高度为0，两层的树高度为1)*/intMax(intl,intr);//求较大的数BBTreeLL_SingleRotate(BBTreek2);//向左旋转一次BBTreeRR_SingleRotate(BBTreek1);//向右旋转一次BBTreeLR_DoubleRotate(BBTreek3);//向左转一次，向右转一次BBTreeRL_DoubleRotate(BBTreek1);//向右转一次，向左转一次输入的形式和输入值的范围？答：输入形式：当树没创立时，先在第一行输入树的节点数目n，第二行再输入n整数，以空格隔开。输入值的范围是int(32位)类型。并且所有的其他要求输入形式均在程序中的每个输入过程都有设有相应的提示和输入值的范围提示。比方：图1：刚刚开始进入程序时，根据提示输入数据后的界面图2：三个递归遍历后的输出输出的形式？答：输出的形式根据功能不同而不同，在程序代码和运行文件中都有说明。比方：图3：为插入新结点，然后输出是否插入成功图4：查找关键字，成功返回值为1，失败后返回值为0程序所能到达的功能答：在程序中可以到达题目中所有的功能。即：1：插入新结点；2：前序、中序、后序遍历二叉树〔递归〕；3：前序、中序、后序遍历的非递归算法；4：层次遍历二叉树；5：在二叉树中查找给定关键字(函数返回值为成功1,失败0)；6：交换各结点的左右子树；7：求二叉树的深度；8：叶子结点数；9：删除某结点。解题思路对于要实现的各个操作，分别说明其应如何求解，用伪码形式描述其求解过程，求解过程中用到的数据结构。答：在各个操作中，我觉得要数建立AVL树、删除结点、后序非递归遍历AVL树较为复杂点。其余都可以比拟快速实现。下面就来说说思路吧。首先，给出所用到的数据结构如下：typedefstructTnode//平衡二叉排序树的数据结构{ ElemTypedata; structTnode*lchild,*rchild; intheight;//以该节点为根的子树的高度}BBTnode,*BBTree;typedefstruct//栈数据结构{ BBTree*base,*top;//栈指针成员 intinitsize;//栈初始长度}Stack;typedefstruct//队列数据结构{ BBTree*front,*rear;//队列指针成员 intInitSize;//栈初始长度}Queue;下面是一些简略的算法描述1、在我建立的一棵AVL树中，其最少节点数与高度有这样的关系：N(h)=N(h-1)+N(h-2)+1.当h=0时，N(h)=1；当h=1时，N(h)=2..(注：我这里所定义的树的高度与教材有小小不同，即：以空树高度为-1，并定义树的高度为树的层次数减1，如只有一个节点的树的高度为0，两层的树高度为1，n层的高度为n－1)。时间复杂度为O(logn)。当我们要插入元素时，如果所插入的节点破坏了树的平衡性，就要重新平衡，并更新树的高度信息。算法实现如下：statusInsertBBT(BBTree&T,ElemTypee)//插入新结点{ if(T==NULL)//空树，建一个节点给树 { T=(BBTree)malloc(sizeof(BBTnode)); if(!T)returnERROR; T->data=e; T->lchild=T->rchild=NULL; T->height=0; } elseif(e<T->data)//向左插入 { InsertBBT(T->lchild,e); if(Height(T->lchild)-Height(T->rchild)==2)//出现不平衡了 { //如果用序列(5,2,1...)就可会出现LL型，用序列(5,2,3...)就可会出现LR型 if(e<T->lchild->data)//这样对应于LL型 T=LL_SingleRotate(T); else//这个对应于LR型 T=LR_DoubleRotate(T); } } elseif(e>T->data)//向右插入 { InsertBBT(T->rchild,e); if(Height(T->rchild)-Height(T->lchild)==2)//出现不平衡了 { //如果用序列(5,6,7...)就可会出现RR型，用序列(5,7,6...)就可会出现RL型 if(e>T->rchild->data)//这样对应于RR型 T=RR_SingleRotate(T); else//这样对应于RL型 T=RL_DoubleRotate(T); } } //如果e==T->data的话什么也不干，最后要记录T->height T->height=Max(Height(T->lchild),Height(T->rchild))+1; returnOK;}在删除节点时，如果删除的是叶子节点，那么它可以直接被删除；如果要删除的节点有一个孩子，那么只要更改其双亲节点指向其孩子节点即可，如图5如示，删除节点4。图5：删除有一个孩子的节点4之前和之后的图比拟复杂的是删除有两个孩子的节点。我的做法是，在要删除的节点的右子树中找出最小的key，然后用这个节点的key代替要删除的节点的key，然后〔递归删除那个最小的节点〕。这样做可以的原因，是因为在右子树中最小的节点不可能有左孩子，第二个删除是非常容易的。图6展示了一棵树删除前后的状态。被删除的节点是根节点的左孩子，其key为2。它的key被它的右子树中最小的key所代替，即key为3的代替了它，然后对key为3的节点再用上述的方法删除〔在此例中，它属于有一个孩子的节点〕。图6：删除节点2〔有两个孩子〕，左为删除前，右为删除后。算法实现如下：statusDeleteBBT(BBTree&T,ElemTypee)//删除某结点{ Positiontemp; if(T==NULL)returnERROR; elseif(e<T->data) returnDeleteBBT(T->lchild,e); elseif(e>T->data) returnDeleteBBT(T->rchild,e); else//即e==T->data的情况 { if(T->lchild!=NULL&&T->rchild!=NULL)//有两个孩子 { temp=FindMin(T->rchild);//在右子树中找到最小的节点 T->data=temp->data;//用找到的最小节点的key代替要删除节点的key DeleteBBT(T->rchild,T->data);//删除右边刚刚找出的最小的节点 } else//有一个或者没有孩子 { temp=T; if(T->lchild==NULL)//也处理了0个孩子的情况 T=T->rchild; elseif(T->rchild==NULL) T=T->lchild; free(temp); } returnOK; }}PositionFindMin(BBTreeT)//找最小的Element{ if(T==NULL)returnNULL; elseif(T->lchild==NULL)returnT; elsereturnFindMin(T->lchild);}3、后序非递归遍历AVL树时，因为右子树这边比拟复杂，所以要设置一个辅助指针pre用来标记刚刚已访问的节点。以下为算法实现：statusNonLastView(BBTreeT,StackS){ BBTreepre=NULL;//pre用来标记刚刚访问过的节点 while(S.base!=S.top||T!=NULL) { while(T!=NULL)//向左走到最左 { *S.top++=T; T=T->lchild; } T=*(S.top-1);//取栈顶节点 if(T->rchild==NULL||T->rchild==pre)//如果T没有右孩子或者其右孩子刚刚被访问过 { cout<<T->data<<"";//输出元素 S.top--;//已访问，令其出栈 pre=T;//标记为刚刚访问过了 T=NULL;//这步是假设已经遍历完以这个节点为root的子树，如果栈空那么真的完了，没有那么没有完，会继续 } else T=T->rchild;//转向右 } returnOK;}遍历的思路：非递归的遍历都用了栈作为辅助的结构，在树的结点中参加状态〔status〕来记录当前结点的访问状态〔函数是否成功等〕。然后再做对应操作。以下为算法实现：statusNonFirstView(BBTreeT,StackS)//非递归前序遍历{ while(S.base!=S.top||T!=NULL) { while(T!=NULL)//向左走到最左 { cout<<T->data<<"";//输出元素 *S.top++=T; T=T->lchild; } T=*--S.top;//出栈 T=T->rchild;//转向右 } returnOK;}statusNonMiddleView(BBTreeT,StackS)//非递归中序遍历{ while(S.base!=S.top||T!=NULL) { while(T!=NULL)//向左走到最左 { *S.top++=T; T=T->lchild; } T=*--S.top;//出栈 cout<<T->data<<"";//输出元素 T=T->rchild;//转向右 } returnOK;}statusNonLastView(BBTreeT,StackS){ BBTreepre=NULL;//pre用来标记刚刚访问过的节点 while(S.base!=S.top||T!=NULL) { while(T!=NULL)//向左走到最左 { *S.top++=T; T=T->lchild; } T=*(S.top-1);//取栈顶节点 if(T->rchild==NULL||T->rchild==pre)//如果T没有右孩子或者其右孩子刚刚被访问过 { cout<<T->data<<"";//输出元素 S.top--;//已访问，令其出栈 pre=T;//标记为刚刚访问过了 T=NULL;//这步是假设已经遍历完以这个节点为root的子树，如果栈空那么真的完了，没有那么没有完，会继续 } else T=T->rchild;//转向右 } returnOK;}统计深度和叶节点数量的思路：都是用了递归的思想，统计深度是递归求左右子树的深度，取较大值。统计叶节点那么是递归求左右子树的叶节点，最后求和。以下为算法实现：intDeepOfTree(BBTreeT)//求二叉树的深度{ intdeep,ldeep=0,rdeep=0; if(T!=NULL) { ldeep=DeepOfTree(T->lchild); rdeep=DeepOfTree(T->rchild); deep=Max(ldeep,rdeep)+1; } elsereturn0; returndeep;}intTotalNodeNumber(BBTreeT)//总的结点数{ intsum=0,lsum=0,rsum=0; if(T!=NULL) { lsum=TotalNodeNumber(T->lchild); rsum=TotalNodeNumber(T->rchild); sum=lsum+rsum+1; returnsum; } elsereturn0;}intLeafNodeNumber(BBTreeT)//叶子结点数{ intcnt=0,lcnt=0,rcnt=0; if(T!=NULL) { if(T->lchild==NULL&&T->rchild==NULL)cnt=1; else { lcnt=LeafNodeNumber(T->lchild); rcnt=LeafNodeNumber(T->rchild); cnt=lcnt+rcnt; } } elsereturn0; returncnt;}调试分析调试过程中遇到的问题是如何解决的以及对设计与实现的回忆讨论和分析！我采用的是每实现一个功能就进行测试，写完第一个功能〔即新节点的插入〕后，我就开始对它测试和排错。一开始我只用了5个元素〔5，3，2，1，4〕来进行测试。发现没有问题，后来在整个程序都写好了，再用另外一组数据测试，发现除了查找和删除这两个功能之外其他各个功能都不能正经进行。于是我就把数据输入〔105911863271〕，就用FindKeyword函数来一个一个查找刚刚输入的元素，结果发现除了元素6之外，个个都可以找到。然后我就开始减少数据的数量，发现在1059118都能正常插入，但是再插入多一个6之后，就出现问题了。然后我自己手动插入，发现出现问题的是在RL_DoubleRotate函数里的一条语句：k1->rchild=LL_SingleRotate(k1->rchild)；(此为正确的)，但是当时却写成了：k1->lchild=LL_SingleRotate(k1->rchild)；注意到那里只是k1左右子树那里写错了。但是算法我是很清楚的，所以我找到最终造成这个bug的是编译器的“方便功能”，也就是我写了k1->之后，它就弹出了如下图，当时就是由于失误选到了lchild，而自己却没有发现，所以导致了一个大大的bug。使用的测试数据〔要求多组〕第一组：53214第二组：105911863271第三组：810954540235977166第四组：32145671615141312111089算法的效率分析和改良设想答：插入和删除的算法均是用了二叉排序树的性质来进行，故算法的效率大概为O(lgn)。而遍历的非递归算法均是以栈结构实现。故应该以O(n)的效率进行。由于算法设计的不完善，删除和插入函数的旋转操作都可以进一步提升效率，判断情况也可以尽量减少冗余。这样可以让时间复杂度前面的系数变小，从而提高算法整体效率。经验和体会答：通过这次AVL树的各种操作，让我更加深入理解了树的概念，及其优越的查找删除效率。而且AVL的中序遍历还是一个排好序的序列，所以也是一个用于排序的好的方法，可以尝试用算法实现。这次实验收获的一个经验就是，对于每个要求，可以一个一个来实现。还有就是如果中途有需要中断程序的编写时，可以做个标记，方便下次可以快速找到要编写的地方。附录//以下为带注释的源程序。#include<iostream>#include<cstdlib>usingnamespacestd;constintMAXSIZE=100;//用const比用#define宏定义要好constintOK=1;//用const比用#define宏定义要好constintERROR=0;//用const比用#define宏定义要好typedefintstatus;typedefintElemType;//平衡二叉排序树的结构typedefstructTnode{ ElemTypedata; structTnode*lchild,*rchild; intheight;//以该节点为根的子树的高度}BBTnode,*BBTree;typedefBBTreePosition;//栈定义typedefstruct{ BBTree*base,*top;//栈指针成员 intinitsize;//栈初始长度}Stack;//队列定义typedefstruct{ BBTree*front,*rear;//队列指针成员 intInitSize;//栈初始长度}Queue;//要用到的函数如下statusInsertBBT(BBTree&T,ElemTypee);//插入新结点statusCreatStack(Stack&S);//建立栈statusCreatQueue(Queue&Q);//建立队列statusFirstViewRoot(BBTreeT);//递归前序遍历statusMiddleViewRoot(BBTreeT);//递归中序遍历statusLastViewRoot(BBTreeT);//递归后序遍历statusViewAll(BBTreeT);//当经常要遍历时可以用来减少代码量statusNonFirstView(BBTreeT,StackS);//非递归前序遍历statusNonMiddleView(BBTreeT,StackS);//非递归中序遍历statusNonLastView(BBTreeT,StackS);//非递归后序遍历statusNonViewAll(BBTreeT,StackS);//当经常要遍历时可以用来减少代码量statusLevelView(BBTreeT,QueueQ);//层次遍历statusFindKeyword(BBTreeT,ElemTypee);//在二叉树中查找给定关键字(函数返回值为成功1,失败0)statusSwapSubtree(BBTreeT);//交换各结点的左右子树intDeepOfTree(BBTreeT);//求二叉树的深度intTotalNodeNumber(BBTreeT);//总的结点数intLeafNodeNumber(BBTreeT);//叶子结点数statusDeleteBBT(BBTree&T,ElemTypee);//删除某结点//以下函数是为了实现我的平衡树算法而设计PositionFindMin(BBTreeT);//找最小的ElementintHeight(BBTreeT);/*求树的高度(以空树为-1，并定义树的高度为树的层次数减1，如只有一个节点的树的高度为0，两层的树高度为1)*/intMax(intl,intr);//求较大的数BBTreeLL_SingleRotate(BBTreek2);//向左旋转一次BBTreeRR_SingleRotate(BBTreek1);//向右旋转一次BBTreeLR_DoubleRotate(BBTreek3);//向左转一次，向右转一次BBTreeRL_DoubleRotate(BBTreek1);//向右转一次，向左转一次intmain(){ inti,n,chose,cnt=0; charc; ElemTypekeyword,e,delKey; StackS; QueueQ; BBTreeT=NULL; cout<<"PleaseinputthenumberofElements:"; cin>>n; cout<<"Now,pleaseinput"<<n<<"Elements:\n"; for(i=0;i<n;i++) { cin>>e; InsertBBT(T,e); } do { cout<<"\n**********************Pleasechooseonefromthese:**************************\n"; cout<<"*1.插入新结点*\n" <<"*2.前序、中序、后序遍历二叉树〔递归〕*\n" <<"*3.前序、中序、后序遍历的非递归算法*\n" <<"*4.层次遍历二叉树*\n" <<"*5.在二叉树中查找给定关键字*\n" <<"*6.交换各结点的左右子树*\n" <<"*7.求二叉树的深度*\n" <<"*8.叶子结点数*\n" <<"*9.删除某结点*\n" <<"*0.退出*\n" <<"******************************************************************************\n" <<"Yourchooseis:"; cin>>chose; switch(chose) { case1: cout<<"PleaseinputoneElementyouwanttoinsert:"; cin>>e; if(InsertBBT(T,e)==OK) cout<<"***TheElement"<<e<<"insertedsuccessfully!***\n"; else cout<<"***TheElement"<<e<<"failedtoinsert!***\n"; break; case2: //以下是递归遍历 cout<<"\nTherecursivetraversalarefollow:\n"; ViewAll(T); break; case3: //以下是非递归遍历 cout<<"\nThenon-recursivetraversalarefollow:\n"; NonViewAll(T,S); break; case4: //以下是层次遍历 cout<<"theLevelViewis:\n"; CreatQueue(Q); LevelView(T,Q); cout<<"\n"; break; case5: //在二叉树中查找给定关键字 cout<<"Pleaseinputthekeywordyouwanttofindinthetree:"; cin>>keyword; if(FindKeyword(T,keyword)==OK) cout<<"***Thekeyword"<<keyword<<"foundsuccessfully!***\n"; else cout<<"***Thekeyword"<<keyword<<"notfound!***\n"; break; case6: //交换各结点的左右子树 SwapSubtree(T); break; case7: //求二叉树的深度 cout<<"\nThedeepofthetreeis:"; cout<<DeepOfTree(T)<<endl; break; case8: //叶子结点数 cout<<"\nThenumberofleavesis:"; cout<<LeafNodeNumber(T)<<endl; cout<<"Andthetotalnumberofnodesis:"; cout<<TotalNodeNumber(T)<<endl; break; case9: //删除某结点 cout<<"PleaseinputtheElementyouwanttoDelete:"; cin>>delKey; if(DeleteBBT(T,delKey)==OK) { cout<<"***TheElement"<<delKey<<"Deletedsuccessfully!***\n"; } else { cout<<"***FailedtoDelete!Becausetheelementnotfound!***\n"; } break; case0:return0;break; default: cout<<"\a***CommandNotVilid!!!***\n"; break; } cout<<"\nContinue...?(pleaseansweryorn)." <<"ifyouanswery,\nthenwillcontinue,otherswillexit!\n" <<"Youransweris:"; cin>>c; }while(c=='y'); return0;}/*---------------------以下是InsertBBT和DeleteBBT所需函数-------------------------*/statusInsertBBT(BBTree&T,ElemTypee)//插入新结点{ if(T==NULL)//空树，建一个节点给树 { T=(BBTree)malloc(sizeof(BBTnode)); if(!T)returnERROR; T->data=e; T->lchild=T->rchild=NULL; T->height=0; } elseif(e<T->data)//向左插入 { InsertBBT(T->lchild,e); if(Height(T->lchild)-Height(T->rchild)==2)//出现不平衡了 { //如果用序列(5,2,1...)就可会出现LL型，用序列(5,2,3...)就可会出现LR型 if(e<T->lchild->data)//这样对应于LL型 T=LL_SingleRotate(T); else//这个对应于LR型 T=LR_DoubleRotate(T); } } elseif(e>T->data)//向右插入 { InsertBBT(T->rchild,e); if(Height(T->rchild)-Height(T->lchild)==2)//出现不平衡了 { //如果用序列(5,6,7...)就可会出现RR型，用序列(5,7,6...)就可会出现RL型 if(e>T->rchild->data)//这样对应于RR型 T=RR_SingleRotate(T); else//这样对应于RL型 T=RL_DoubleRotate(T); } } //如果e==T->data的话什么也不干，最后要记录T->height T->height=Max(Height(T->lchild),Height(T->rchild))+1; returnOK;}statusDeleteBBT(BBTree&T,ElemTypee)//删除某结点{ Positiontemp; if(T==NULL)returnERROR; elseif(e<T->data) returnDeleteBBT(T->lchild,e); elseif(e>T->data) returnDeleteBBT(T->rchild,e); else//即e==T->data的情况 { if(T->lchild!=NULL&&T->rchild!=NULL)//有两个孩子 { temp=FindMin(T->rchild);//在右子树中找到最小的节点 T->data=temp->data;//用找到的最小节点的data代替要删除节点的data DeleteBBT(T->rchild,T->data);//删除右边刚刚找出的最小的节点 } else//有一个或者没有孩子 { temp=T; if(T->lchild==NULL)//也处理了0个孩子的情况 T=T->rchild; elseif(T->rchild==NULL) T=T->lchild; free(temp); } returnOK; }}PositionFindMin(BBTreeT)//找最小的Element{ if(T==NULL)returnNULL; elseif(T->lchild==NULL)returnT; elsereturnFindMin(T->lchild);}intHeight(BBTreeT)//求树的高度{ if(T==NULL)return-1; elsereturnT->height;}intMax(intl,intr)//求较大的数{ returnl>r?l:r;}BBTreeLL_SingleRotate(BBTreek2)//向左旋转一次，抓住k1(小的)，让重力话事{ BBTreek1; k1=k2->lchild; k2->lchild=k1->rchild; k1->rchild=k2; k1->height=Max(Height(k1->lchild),k2->height)+1; k2->height=Max(Height(k2->lchild),Height(k2->rchild))+1; returnk1;//新的root}BBTreeRR_SingleRotate(BBTreek1)//向右旋转一次，抓住k2(大的)，让重力话事{ BBTreek2; k2=k1->rchild; k1->rchild=k2->lchild; k2->lchild=k1; k1->height=Max(Height(k1->lchild),Height(k1->rchild))+1; k2->height=Max(Height(k1->rchild),k1->height)+1; returnk2;//新的root}BBTreeLR_DoubleRotate(BBTreek3)//向左转一次，向右转一次{ k3->lchild=RR_SingleRotate(k3->lchild);//先逆时针转 returnLL_SingleRotate(k3);//再顺时针转}BBTreeRL_DoubleRotate(BBTreek1)//向右转一次，向左转一次{ k1->rchild=LL_SingleRotate(k1->rchild);//先顺时针转 returnRR_SingleRotate(k1);//再逆时针转}/*--------------------以上是InsertBBT和DeleteBBT所需函数-------------------------*/statusCreatStack(Stack&S)//建立栈{ S.base=(BBTree*)malloc(MAXSIZE*sizeof(BBTree)); if(!S.base)returnERROR; S.top=S.base; S.initsize=MAXSIZE; returnOK;}statusCreatQueue(Queue&Q)//建立队列{ Q.front=(BBTree*)malloc(MAXSIZE*sizeof(BBTree)); if(!Q.front)returnERROR; Q.rear=Q.front; Q.InitSize=MAXSIZE; returnOK;}statusFirstViewRoot(BBTreeT)//递归前序遍历{ if(T!=NULL) { cout<<T->data<<""; FirstViewRoot(T->lchild); FirstViewRoot(T->rchild); } returnOK;}statusMiddleViewRoot(BBTreeT)//递归中序遍历{ if(T!=NULL) { MiddleViewRoot(T->lchild); cout<<T->data<<""; MiddleViewRoot(T->rchild); } returnOK;}statusLastViewRoot(BBTreeT)//递归后序遍历{ if(T!=NULL) { LastViewRoot(T->lchild); LastViewRoot(T->rchild); cout<<T->data<<""; } returnOK;}statusViewAll(BBTreeT){ cout<<"theFirstViewRootis:\n"; FirstViewRoot(T); cout<<"\n"; cout<<"theMiddleViewRootis:\n"; MiddleViewRoot(T); cout<<"\n"; cout<<"theLastViewRootis:\n"; LastViewRoot(T); cout<<"\n"; returnOK;}statusNonFirstView(BBTreeT,StackS)//非递归前序遍历{ while(S.base!=S.top||T!=NULL) { while(T!=NULL)//向左走到最左 { cout<<T->data<<"";//输出元素 *S.top++=T; T=T->lchild; } T=*--S.top;//出栈 T=T->rchild;//转向右 } returnOK;}statusNonMiddleView(BBTreeT,StackS)//非递归中序遍历{ while(S.base!=S.top||T!=NULL) { while(T!=NULL)//向左走到最左 { *S.top++=T; T=T->lchild; } T=*--S.top;//出栈 cout<<T->data<<"";//输出元素 T=T->rchild;//转向右 } returnOK;}statusNonLastView(BBTreeT,StackS){ BBTreepre=NULL;//pre用来标记刚刚访问过的节点 while(S.base!=S.top||T!=NULL) { while(T!=NULL)//向左走到最左 { *S.t