数据结构实验

附件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）删除某结点以下几点是在程序中的规定：1）各个函数命名，包含的参数，返回值类型 要用到的结构体和typedef重命名类型平衡二叉排序树的结构typedef struct TnodeElemType data; struct Tnode *lchild,*rchild;int height;以该节点为根的子树的高度BBTnode,*BBTree;栈定义typedef structBBTree *base,*top;/ 栈指针成员int initsize;栈初始长度Stack;队列定义 typedef struct BBTree *front,*rear; / 队列指针成员int InitSize;/栈初始长度Queue;const int MAXSIZE = 100;/用 const 比用#define 宏定义要好const int OK = 1;/用 const 比用#define 宏定义要好const int ERROR = 0;用 const 比用#define 宏定义要好typedef int status;用status表示函数返回值状态typedef int ElemType; 用 ElemType表示元素类型 typedef BBTree Position; 表示节点在树中的位置要用到的函数如下status InsertBBT(BBTree &T,ElemType e); / 插入新结点建立栈建立队列/递归前序遍历/递归中序遍历/递归后序遍历/当经常要遍历时可以用来减少代码量status CreatStack(Stack & S); status CreatQueue(Queue & Q);status FirstViewRoot(BBTree T); status MiddleViewRoot(BBTree T); status LastViewRoot(BBTree T);status ViewAll(BBTree T);status NonFirstView(BBTree T,Stack S); status NonMiddleView(BBTree T,Stack S); status NonLastView(BBTree T,Stack S);status NonViewAll(BBTree T,Stack S); status LevelView(BBTree T,Queue Q);/非递归前序遍历/非递归中序遍历非递归后序遍历/当经常要遍历时可以用来减少代码量/层次遍历status FindKeyword(BBTree T,ElemType e);/在二叉树中查找给定关键字(函数返回值为 成功1,失败0)/交换各结点的左右子树求二叉树的深度总的结点数/叶子结点数/删除某结点status SwapSubtree(BBTree T);int DeepOfTree(BBTree T);int TotalNodeNumber(BBTree T);int LeafNodeNumber(BBTree T);status DeleteBBT(BBTree &T,ElemType e);以下函数是为了实现我的平衡树算法而设计Position FindMin(BBTree T);/找最小的 Elementint Height(BBTree T);/*求树的高度(以空树为-1,并定义树的高度为树的层次数减1,如只有一个节点的树的高度为0,两层的树高度为1)*/int Max(int l,int r);/ 求较大的数BBTree LL_SingleRotate(BBTree k2);/ 向左旋转一次BBTree RR_SingleRotate(BBTree k1);/ 向右旋转一次BBTree LR_DoubleRotate(BBTree k3);向左转一次，向右转一次BBTree RL_DoubleRotate(BBTree k1);向右转一次，向左转一次2）输入的形式和输入值的范围？答:输入形式：当树没创建时，先在第一行输入树的节点数目n，第二行再输入n整数, 以空格隔开。输入值的范围是int（32位）类型。并且所有的其他要求输入形式均在程序 中的每个输入过程都有设有相应的提示和输入值的范围提示。比如：Please input the nunber of Elements: 16 Now,please input 16 Elements:3 2 1 4 5 6 7 16 15 14 13 12 11 10 8 9C:u詔吋加Iminist陌todD出ktp儼据结构已通过的懸辭结构综台实捡侯现平衡二序树: 4HJ.UJ -J -eeS叉非字 th二的键E历历京 ro1定子 f 1 ne左度 o :叉查的探 se占疳二矍结ch新：遍叉各叉结某二换二子雷 as插前刖畧交求叶黒 11234567890图1：刚刚开始进入程序时，根据提示输入数据后的界面 9U较吸如mini阳todDktop谓牖结构已通过的鬆邀结构综台实蜀实现平衡二序树Lar :eesX非字 th二的键 m历历京 ro曙定子 f 1 ne左度 O :叉查的深 se4wt 二 - 结ch新：遍叉各叉结某二换二子営 as插前刖专交求叶黒 11234567890Vour choose is: 2The recursiue trauersal are follow：the FitstU iewRoot is :7 4 2 1 3 6 5 13 11 9 8 10 12 15 14 16 the MiddleUiewRoot is:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 the LastUieuRoot is:1 3 2 5 6 4 8 10 9 12 11 14 16 15 13 7Continue._?. if you answer y, then will continue,others will exit?Volip answer is:图2：三个递归遍历后的输出3）输出的形式？答：输出的形式根据功能不同而不同，在程序代码和运行文件中都有说明。比如:ar- 4HJ.5 _J _eeS叉非字 th二的键E历历京 ro1定子 f 1 ne左度 o :叉查的深 se占秦二结ch新：遍叉各叉结某二换二子矍 as插前刖畧交求叶黒 11234567890Volip choose is: 1Please input one Element you uant to insert: 20 * The Element 20 inserted successfully? *Continue ?plEaiJE answep y op n. if you answer y, then will continue,others will exit?Vour answer is: y图3：为插入新结点，然后输出是否插入成功”C:诃歸rAcIminist為rD二kt赢琳结罚已谨过的悪魏S结构综台实證翎1平衝三站E序树”,eesX非字 th二的键 m历历i ro曙定子 f 1 ne左度 o :叉查的深 se占韋二 - 结ch新：遍叉各叉结某二换二子営 as插前刖专交求叶黒 11234567890Vour choose is: 5Please input the keyword you uant to ind in the tree： 100 * The keyword 100 not found* *Continue ?p1ebjje an s we r y or n . if you answer y then will continue,others will exit?Volip answer is:图4：查找关键字，成功返回值为1,失败后返回值为04）程序所能达到的功能答：在程序中可以达到题目中所有的功能。即：1：插入新结点；2：前序、中序、后序 遍历二叉树(递归)；3：前序、中序、后序遍历的非递归算法；4：层次遍历二叉树； 5：在二叉树中查找给定关键字(函数返回值为成功1,失败0) ； 6：交换各结点的左右子 树；7：求二叉树的深度；8：叶子结点数；9：删除某结点。、解题思路对于要实现的各个操作，分别说明其应如何求解，用伪码形式描述其求解过程，求解过 程中用到的数据结构。答：在各个操作中，我觉得要数建立AVL树、删除结点、后序非递归遍历AVL树较为 复杂点。其余都可以比较快速实现。下面就来说说思路吧。 首先，给出所用到的数据结构如下：typedef struct Tnode平衡二叉排序树的数据结构ElemType data;struct Tnode *lchild,*rchild;int height;/以该节点为根的子树的高度BBTnode,*BBTree;typedef struct栈数据结构BBTree *base,*top;栈指针成员int initsize;栈初始长度Stack;typedef struct队列数据结构BBTree *front,*rear; 队列指针成员int InitSize;栈初始长度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时间复杂度为O(log n)。 当我们要插入元素时，如果所插入的节点破坏了树的平衡性，就要重新平衡，并更新树 的高度信息。算法实现如下：status InsertBBT(BBTree &T,ElemType e) 插入新结点if(T = NULL)/空树，建一个节点给树T = (BBTree)malloc(sizeof(BBTnode);if(!T) return ERROR;T-data = e;T-lchild = T-rchild = NULL;T-height = 0;else if(e data) 向左插入InsertBBT(T-lchild,e);if(Height(T-lchild) - Height(T-rchild) = 2) /出现不平衡了 如果用序列(5,2,1.)就可会出现LL型，用序列(5,2,3.)就可会出现LR型if(e lchild-data) 这样对应于 LL 型T = LL_SingleRotate(T);else这个对应于LR型T = LR_DoubleRotate(T);else if(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-heightT-height = Max(Height(T-lchild),Height(T-rchild) + 1;return OK;2、在删除节点时，如果删除的是叶子节点，则它可以直接被删除；如果要删除的节点 有一个孩子，那么只要更改其双亲节点指向其孩子节点即可，如图5如示，删除节点4。图5：删除有一个孩子的节点4之前和之后的图比较复杂的是删除有两个孩子的节点。我的做法是，在要删除的节点的右子树中找出最小的 key，然后用这个节点的key代替要删除的节点的key，然后（递归删除那个最小的节点）。 这样做可以的原因，是因为在右子树中最小的节点不可能有左孩子，第二个删除是非常容易 的。图6展示了一棵树删除前后的状态。被删除的节点是根节点的左孩子，其key为2。它 的key被它的右子树中最小的key所代替，即key为3的代替了它，然后对key为3的节点 再用上述的方法删除（在此例中，它属于有一个孩子的节点）。图6：删除节点2 （有两个孩子），左为删除前，右为删除后。算法实现如下：status DeleteBBT(BBTree &T,ElemType e)/ 删除某结点Position temp;if(T = NULL) return ERROR;else if(e data)return DeleteBBT(T-lchild,e);else if(e T-data)return DeleteBBT(T-rchild,e);else 即 e = T-data 的情况if(T-lchild != NULL & T-rchild !=NULL)/ 有两个孩子temp = FindMin(T-rchild);/在右子树中找到最小的节点T-data = temp-data;用找到的最小节点的key代替要删除节点的keyDeleteBBT(T-rchild,T-data); 删除右边刚刚找出的最小的节点else有一个或者没有孩子temp = T;if(T-lchild = NULL) 也处理了 0个孩子的情况T = T-rchild;else if(T-rchild = NULL)T = T-lchild;free(temp);return OK;Position FindMin(BBTree T)/找最小的 Elementif(T = NULL) return NULL;else if(T-lchild = NULL) return T;else return FindMin(T-lchild);3、后序非递归遍历AVL树时，因为右子树这边比较复杂，所以要设置一个辅助指针pre用 来标记刚刚已访问的节点。以下为算法实现：status NonLastView(BBTree T,Stack S)BBTree pre = NULL; /pre用来标记刚刚访问过的节点while(S.base != S.top II T != NULL)while(T != NULL)向左走到最左*S.top+ = T;T = T-lchild;T=*(S.top - 1);取栈顶节点if(T-rchild = NULL | T-rchild = pre) 如果T没有右孩子或者其右孩子刚刚被 访问过cout data rchild; / 转向右return OK;4、遍历的思路：非递归的遍历都用了栈作为辅助的结构，在树的结点中加入状态(status) 来记录当前结点的访问状态(函数是否成功等)。然后再做对应操作。以下为算法实现：status NonFirstView(BBTree T,Stack S)/ 非递归前序遍历while(S.base != S.top II T != NULL)while(T != NULL)向左走到最左 _cout data lchild;T=*-S.top;出栈T = T-rchild;转向右return OK;status NonMiddleView(BBTree T,Stack S)/ 非递归中序遍历while(S.base != S.top | T != NULL)while(T != NULL)向左走到最左*S.top+ = T;T = T-lchild;T=*-S.top;出栈cout data rchild;转向右return OK;status NonLastView(BBTree T,Stack S)BBTree pre = NULL;/pre用来标记刚刚访问过的节点while(S.base != S.top II T != NULL)while(T != NULL)向左走到最左*S.top+ = T;T = T-lchild;T=*(S.top - 1);取栈顶节点if(T-rchild = NULL | T-rchild = pre) 如果T没有右孩子或者其右孩子刚刚被 访问过 _cout data rchild;/ 转向右return OK;5、统计深度和叶节点数量的思路：都是用了递归的思想，统计深度是递归求左右子树的深 度，取较大值。统计叶节点则是递归求左右子树的叶节点，最后求和。以下为算法实现：int DeepOfTree(BBTree T)/ 求二叉树的深度int deep,ldeep = 0,rdeep = 0;if(T != NULL)ldeep = DeepOfTree(T-lchild);rdeep = DeepOfTree(T-rchild);deep = Max(ldeep,rdeep) + 1;else return 0;return deep;int TotalNodeNumber(BBTree T)总的结点数int sum = O,lsum = O,rsum = 0;if(T != NULL)lsum = TotalNodeNumber(T-lchild);rsum = TotalNodeNumber(T-rchild);sum = lsum + rsum + 1;return sum;else return 0;int LeafNodeNumber(BBTree T)/ 叶子结点数int cnt = 0,lcnt = 0,rcnt = 0;if(T != NULL)if(T-lchild = NULL & T-rchild = NULL) cnt=1;elselcnt = LeafNodeNumber(T-lchild);rcnt = LeafNodeNumber(T-rchild);cnt = lcnt + rcnt;else return 0;return cnt;三、调试分析1) 调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析！ 我采用的是每实现一个功能就进行测试，写完第一个功能(即新节点的插入)后， 我就开始对它测试和排错。一开始我只用了 5个元素(5, 3, 2，1, 4)来进行测试。 发现没有问题，后来在整个程序都写好了，再用另外一组数据测试，发现除了查找和删 除这两个功能之外其他各个功能都不能正经进行。于是我就把数据输入(10 5 9 11 8 6 3 2 7 1)，就用FindKeyword函数来一个一个查找刚刚输入的元素，结果发现除了元素 6之外，个个都可以找到。然后我就开始减少数据的数量，发现在10 5 9 11 8都能正常 插入，但是再插入多一个6之后，就出现问题了。然后我自己手动插入，发现出现问题 的是在 RL_DoubleRotate 函数里的一条语句：kl-rchild = LL_SingleRotate(kl-rchild)； (此为正确的)，但是当时却写成了： k1-lchild = LL_SingleRotate(kl-rchild)；注意到那 里只是k1左右子树那里写错了。但是算法我是很清楚的，所以我找到最终造成这个bug 的是编译器的“方便功能”也就是我写了 kl-之后，它就弹出了如图所示，当时就 是由于失误选到了 lchild,而自己却没有发现，所以导致了一个大大的bug。空-耳Hl ElernTjie TrLude : : dataTnode* Tnode: :lchildm Tnode* Tnode: :rchild m int Tno de : : he i ght2）使用的测试数据（要求多组）第一组：5 3 2 1 4第二组：10 5 9 11 8 6 3 2 7 1第三组：8 10 95 45 40 23 59 77 1 66第四组：3 2 1 4 5 6 7 16 15 14 13 12 11 10 8 93）算法的效率分析和改进设想答：插入和删除的算法均是用了二叉排序树的性质来进行，故算法的效率大概为 O（lgn）。而遍历的非递归算法均是以栈结构实现。故应该以O（n）的效率进行。由于算法 设计的不完善，删除和插入函数的旋转操作都可以进一步提升效率，判断情况也可以尽 量减少冗余。这样可以让时间复杂度前面的系数变小，从而提高算法整体效率。4）经验和体会答：通过这次AVL树的各种操作，让我更加深入理解了树的概念，及其优越的查找删 除效率。而且AVL的中序遍历还是一个排好序的序列，所以也是一个用于排序的好的 方法，可以尝试用算法实现。这次实验收获的一个经验就是，对于每个要求，可以一个 一个来实现。还有就是如果中途有需要中断程序的编写时，可以做个标记，方便下次可 以快速找到要编写的地方。四、附录以下为带注释的源程序。#includeviostream#includevcstdlibusing namespace std;const int MAXSIZE = 100;/用 const 比用#define 宏定义要好const int OK = 1;/用 const 比用#define 宏定义要好const int ERROR = 0;用 const 比用#define 宏定义要好typedef int status;typedef int ElemType;平衡二叉排序树的结构typedef struct TnodeElemType data;struct Tnode *lchild,*rchild;int height;以该节点为根的子树的高度BBTnode,*BBTree;typedef BBTree Position;栈定义typedef structBBTree *base,*top;/ 栈指针成员int initsize;栈初始长度Stack;队列定义typedef structBBTree *front,*rear; / 队列指针成员 int InitSize;/栈初始长度Queue;要用到的函数如下建立栈建立队列status InsertBBT(BBTree &T,ElemType e); / 插入新结点 status CreatStack(Stack & S);/递归前序遍历递归中序遍历/递归后序遍历/当经常要遍历时可以用来减少代码量status CreatQueue(Queue & Q);status FirstViewRoot(BBTree T); status MiddleViewRoot(BBTree T); status LastViewRoot(BBTree T); status ViewAll(BBTree T);status NonFirstView(BBTree T,Stack S); status NonMiddleView(BBTree T,Stack S); status NonLastView(BBTree T,Stack S);status NonViewAll(BBTree T,Stack S); status LevelView(BBTree T,Queue Q);/非递归前序遍历/非递归中序遍历非递归后序遍历/当经常要遍历时可以用来减少代码量/层次遍历/交换各结点的左右子树求二叉树的深度总的结点数/叶子结点数/删除某结点status FindKeyword(BBTree T,ElemType e);在二叉树中查找给定关键字(函数返回值为 成功1,失败0)status SwapSubtree(BBTree T);int DeepOfTree(BBTree T);int TotalNodeNumber(BBTree T);int LeafNodeNumber(BBTree T);status DeleteBBT(BBTree &T,ElemType e);以下函数是为了实现我的平衡树算法而设计Position FindMin(BBTree T);/找最小的 Elementint Height(BBTree T);/*求树的高度(以空树为-1,并定义树的高度为树的层次数减1,如只有一个节点的树的高度为0两层的树高度为1)*/int Max(int l,int r);/ 求较大的数BBTree LL_SingleRotate(BBTree k2);/ 向左旋转一次BBTree RR_SingleRotate(BBTree k1);/ 向右旋转一次BBTree LR_DoubleRotate(BBTree k3);向左转一次，向右转一次BBTree RL_DoubleRotate(BBTree k1);向右转一次，向左转一次int main()int i,n,chose,cnt=0;char c;ElemType keyword,e,delKey;Stack S;Queue Q;BBTree T = NULL;cout n;cout Now,please input n e;InsertBBT(T,e);docout * Please choose one from these:*n;cout *1.插入新结点*n *2.前序、中序、后序遍历一叉树(递归)*n *3.前序、中序、后序遍历的非递归算法*n *4.层次遍历二叉树*n *5.在二叉树中查找给定关键字*n *6.交换各结点的左右子树*n *7.求二叉树的深度*n *8叶子结点数*n *9.删除某结点*n *0.退出*n11 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1*1 1 Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx*n chose;switch(chose)case 1:cout e;if(InsertBBT(T,e) = OK)cout * The Element e inserted successfully! *n;elsecout * The Element e failed to insert! *n; break;case 2:以下是递归遍历cout nThe recursive traversal are follow:n;ViewAll(T);break;case 3:以下是非递归遍历cout nThe non-recursive traversal are follow:n;NonViewAll(T,S);break;case 4:以下是层次遍历cout the LevelView is:n;CreatQueue(Q);LevelView(T,Q);cout n;break;case 5:在二叉树中查找给定关键字cout keyword;if(FindKeyword(T,keyword) = OK)cout * The keyword keyword found successfully!* n；elsecout * The keyword keyword not found! *n; break;case 6:父换各结点的左右子树SwapSubtree(T);break;case 7:求二叉树的深度cout nThe deep of the tree is:;cout delKey;if(DeleteBBT(T,delKey) = OK)cout vv * The Element vv delKey vv Deleted successfully!* n；elsecout vv * Failed to Delete!Because the element not found! *n;break;case O:return O;break;default:cout a*Command Not Vilid!*n;break;cout nContinue.?(please answer y or n). if you answer y,nthen will continue,others will exit!n c;while(c = y);return 0;/*以下是InsertBBT和DeleteBBT所需函数*/status InsertBBT(BBTree &T,ElemType e) 插入新结点if(T = NULL)空树，建一个节点给树T = (BBTree)malloc(sizeof(BBTnode);if(!T) return ERROR;T-data = e;T-lchild = T-rchild = NULL;T-height = 0;else if(e data) 向左插入InsertBBT(T-lchild,e);if(Height(T-lchild) - Height(T-rchild) = 2) 出现不平衡了如果用序列(5,2,1.)就可会出现LL型，用序列(5,2,3.)就可会出现LR型if(e lchild-data) 这样对应于 LL 型T = LL_SingleRotate(T);else这个对应于LR型T = LR_DoubleRotate(T);else if(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-heightT-height = Max(Height(T-lchild),Height(T-rchild) + 1; return OK;status DeleteBBT(BBTree &T,ElemType e)/ 删除某结点Position temp;if(T = NULL) return ERROR;else if(e data)return DeleteBBT(T-lchild,e);else if(e T-data)return DeleteBBT(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;else if(T-rchild = NULL)T = T-lchild;free(temp);return OK;if(T = NULL) return NULL;else if(T-lchild = NULL) return T;else return FindMin(T-lchild);int Height(BBTree T)/ 求树的高度if(T = NULL) return -1;else return T-height;int Max(int l,int r)/ 求较大的数return lr?l:r;BBTree LL_SingleRotate(BBTree k2)/向左旋转一次，抓住kl(小的)，让重力话事BBTree k1;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;return k1;新的 rootBBTree RR_SingleRotate(BBTree k1)/向右旋转一次，抓住k2(大的)，让重力话事BBTree k2;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;return k2;新的 rootBBTree LR_DoubleRotate(BBTree k3)/ 向左转一次，向右转一次k3-lchild = RR_SingleRotate(k3-lchild); 先逆时针转再顺时针转return LL_SingleRotate(k3);BBTree RL_DoubleRotate(BBTree k1)/ 向右转一次，向左转一次kl-rchild = LL_SingleRotate(kl-rchild); / 先顺时针转return RR_SingleRotate(k1);/ 再逆时针转/*以上是InsertBBT和DeleteBBT所需函数*/status CreatStack(Stack &S)/ 建立栈S.base = (BBTree *)malloc(MAXSIZE * sizeof(BBTree);if(!S.base) return ERROR;S.top = S.base;S.initsize = MAXSIZE;return OK;status CreatQueue(Queue &Q)/ 建立队列Q.front = (BBTree *)malloc(MAXSIZE * sizeof(BBTree);if(!Q.front) return ERROR;Q.rear = Q.front;Q.InitSize = MAXSIZE;return OK;status FirstViewRoot(BBTree T)/ 递归前序遍历if(T != NULL)cout data lchild);FirstViewRoot(T-rchild);return OK;status MiddleViewRoot(BBTree T)/ 递归中序遍历if(T != NULL)MiddleViewRoot(T-lchild);cout data rchild);return OK;status LastViewRoot(BBTree T)/ 递归后序遍历if(T != NULL)LastViewRoot(T-lchild);LastViewRoot(T-rchild);cout data ;return OK;status ViewAll(BBTree T)cout the FirstViewRoot is:n;FirstViewRoot(T);cout n;cout the MiddleViewRoot is:n;MiddleViewRoot(T);cout n;cout the LastViewRoot is:n;LastViewRoot(T);cout n;return OK;status NonFirstView(BBTree T,Stack S)/ 非递归前序遍历while(S.base != S.top II T != NULL)while(T != NULL)向左走到最左 _cout data lchild;T=*-S.top;出栈T = T-rchild;/ 转向右return OK;status NonMiddleView(BBTree T,Stack S)/ 非递归中序遍历while(S.base != S.top II T != NULL)while(T != NULL)向左走到最左*S.top+ = T;T = T-lchild;T=*-S.top;出栈cout data rchild;