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

附件附件 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 structBBTree*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);/找最小的 Element int 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 位)类型。并且所有的其他要求输入形式均在程序中的每个输入过程都有设有相应的提示和输入值的范围提示。比如：图 1：刚刚开始进入程序时，根据提示输入数据后的界面图 2：三个递归遍历后的输出3）输出的形式？答：输出的形式根据功能不同而不同，在程序代码和运行文件中都有说明。比如：图 3：为插入新结点，然后输出是否插入成功图 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 层的高度为 n1)。时间复杂度为 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-height T-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)/找最小的 Element if(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|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|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|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=0,lsum=0,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 函数里的一条语句：k1-rchild=LL_SingleRotate(k1-rchild)；(此为正确的)，但是当时却写成了：k1-lchild=LL_SingleRotate(k1-rchild)；注意到那里只是 k1 左右子树那里写错了。但是算法我是很清楚的，所以我找到最终造成这个 bug 的是编译器的“方便功能”，也就是我写了 k1-之后，它就弹出了如图所示，当时就是由于失误选到了 lchild，而自己却没有发现，所以导致了一个大大的bug。2）使用的测试数据（要求多组）第一组：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 的中序遍历还是一个排好序的序列，所以也是一个用于排序的好的方法，可以尝试用算法实现。这次实验收获的一个经验就是，对于每个要求，可以一个一个来实现。还有就是如果中途有需要中断程序的编写时，可以做个标记，方便下次可以快速找到要编写的地方。四、附录/以下为带注释的源程序。#include#includeusing 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);/找最小的 Element int 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 Elements:n;for(i=0;i e;InsertBBT(T,e);docout n*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.退出 *n *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 DeepOfTree(T)endl;break;case 8:/叶子结点数 cout nThe number of leaves is:;cout LeafNodeNumber(T)endl;cout And the total number of nodes is:;cout TotalNodeNumber(T)endl;break;case 9:/删除某结点 cout delKey;if(DeleteBBT(T,delKey)=OK)cout *The Element delKey Deleted successfully!*n;elsecout *Failed to Delete!Because the element not found!*n;break;case 0:return 0;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-height T-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 代替要删除节点的dataDeleteBBT(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)/找最小的 Element 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)/向左旋转一次，抓住 k1(小的)，让重力话事 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;/新的 root BBTree 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;/新的 root BBTree LR_DoubleRotate(BBTree k3)/向左转一次，向右转一次 k3-lchild=RR_SingleRotate(k3-lchild);/先逆时针转 return LL_SingleRotate(k3);/再顺时针转 BBTree RL_DoubleRotate(BBTree k1)/向右转一次，向左转一次 k1-rchild=LL_SingleRotate(k1-rchild);/先顺时针转 return RR_SingleRotate(k1);/再逆时针转/*-以上是 InsertBBT 和 DeleteBBT 所需函数-*/status CreatStack(Stack&S)/建立栈 S.base=(BBTree*)malloc(MAXSIZE*sizeof(BBTree);ifS.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|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|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;status NonViewAll(BBTree T,Stack S)cout the FirstViewRoot is:n;CreatStack(S);NonFirstView(T,S);cout n;cout the MiddleViewRoot is:n;CreatStack(S);NonMiddleView(T,S);cout n;cout the LastViewRoot is:n;CreatStack(S);NonLastView(T,S);cout lchild!=NULL)*Q.rear+=T-lchild;/左子树进队 if(T-rchild!=NULL)*Q.rear+=T-rchild;/右子树进队 T=*Q.front+;/出队 cout data data)return OK;else if(e data)return FindKeyword(T-lchild,e);else return FindKeyword(T-rchild,e);else return ERROR;status SwapSubtree(BBTree T)/交换各结点的左右子树 BBTree tmpNode;if(T