2022年递归和非递归遍历二叉树 .pdf

《2022年递归和非递归遍历二叉树 .pdf》由会员分享，可在线阅读，更多相关《2022年递归和非递归遍历二叉树 .pdf（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构（双语）项目文档报告递归、非递归两种算法遍历二叉树专业：计算机科学与技术班级：指导教师：苏亚光姓名：学号：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 16 页 - - - - - - - - - 第 - 2 - 页 共 16 页目录一、设计思想.3 页二、算法流程图4.页三、源代码 10 页四、运行结果. 15 页五、遇到的问题及解决15页六、心得体会16 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - -

2、- - - 名师精心整理 - - - - - - - 第 2 页，共 16 页 - - - - - - - - - 第 - 3 - 页 共 16 页一、设计思想1.递归遍历二叉树算法思想: 1先序遍历：首先判断根结点是否为空，为空则停止遍历，不为空则将左子作为新的根结点重新进行上述判断，左子遍历结束后，再将右子作为根结点判断，直至结束。 到达每一个结点时，打印该结点数据，即得先序遍历结果。若二叉树非空，则依次进行如下操作：（1）访问跟结点；（2）前序遍历左子树；（3）前序遍历右子树。2. 中序遍历：首先判断该结点是否为空，为空则结束，不为空则将左子作为根结点再进行判断， 打印左子， 然后打印二

3、叉树的根结点，最后再将右子作为参数进行判断，打印右子，直至结束。若二叉树非空，则依次进行如下操作：（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。3. 后续遍历：指针到达一个结点时，判断该结点是否为空，为空则停止遍历，不为空则将左子作为新的结点参数进行判断，打印左子。 左子判断完成后，将右子作为结点参数传入判断，打印右子。左右子判断完成后打印根结点。若二叉树非空，则依次进行如下操作：（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。2. 非递归遍历二叉树算法思想: 1. 先序遍历：建立一个栈， 当指针到达根结点时，打印根结点， 判断根结点是否有左子和右子。有左子和右子

4、的话就打印左子同时将右子入栈，将左子作为新的根结点进行判断，方法同上。 若当前结点没有左子，则直接将右子打印，同时将右子作为新的根结点判断。若当前结点没有右子，则打印左子，同时将左子作为新的根结点判断。若当前结点既没有左子也没有右子，则当前结点为叶子结点，此时将从栈中出栈一个元素，作为当前的根结点，打印结点元素，同时将当前结点同样按上述方法判断，依次进行。 直至当前结点的左右子都为空，且栈为空时，遍历结束。2. 中序遍历：建立一个栈， 当指针到达根结点时，把根结点压栈， 判断根结点是否有左孩子。有左孩子的话将左孩子，将新结点入栈， 然后再将指针指向当前结点的左子，直至左子为空，弹栈一个元素，

5、作为当前结点， 打印该栈顶元素，将指针指向当前结点右子，将右子作为新的结点，结点入栈， 再次进行上面的判断，直至当前结点右子也为空，则再出栈一个元素作为当前结点，一直到结束，使得当前结点右子为空，且栈空，遍历结束。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 16 页 - - - - - - - - - 第 - 4 - 页 共 16 页3. 后续遍历：建立一个栈，然后定义一个tag ，取值为0，1，0 代表右子没有去过，1代表去过。 初始时指针指向根结点，将根结点压栈，

6、 指针指向左子，则将左子作为当前结点，继续判断直至左孩子为null ，设 q=null ，tag=1 。然后取得栈顶元素，设为当前结点，判断当前结点的右孩子是否等于q，如果相等，则打印当前结点，然后弹出当前结点，并且令 q=当前结点的值。然后继续判断，直至右孩子不等于q，则将指针指向右孩子，把右孩子设为当前结点，令tag=0 ，继续步骤，直到全部元素弹栈，栈为空时，遍历结束。二、 算法流程图图 1.先序递归流程图开始判断结点是否为空访问根结点结束先序方式遍历左子树先序方式遍历右子树是否名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - -

7、- 名师精心整理 - - - - - - - 第 4 页，共 16 页 - - - - - - - - - 第 - 5 - 页 共 16 页图 2. 中序递归流程图开始判断结点是否空按中序方式遍历左子树结束访问根结点按中根遍历方式遍历右子树Y N 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 16 页 - - - - - - - - - 第 - 6 - 页 共 16 页图 3 .后序递归流程图开始判断结点是否空按后根遍历方式遍历左子树结束按后根遍历方式遍历右子树访问根结

8、点Y N 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 16 页 - - - - - - - - - 第 - 7 - 页 共 16 页图 4 . 先序非递归流程图开始申请一个栈stack 判断结点是否空输出结点值，压栈，指针指向它的左孩子判断结点是否空弹出栈顶元素，指向结点的右孩子结束判断栈或结点是否空N Y N Y N 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - -

9、 - 第 7 页，共 16 页 - - - - - - - - - 第 - 8 - 页 共 16 页图 1. 流程图图 2. 流程图图 3. 流程图图 5. 中序非递归流程图开始申请一个stack 判断结点是否空把结点压栈，指针指向它的左孩子判断结点是否空弹栈，设为当前结点，打印结点值，指向右孩子结束判断栈或结点是否空N Y Y N N 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 16 页 - - - - - - - - - 第 - 9 - 页 共 16 页图 6.

10、后序非递归流程图开始申请一个栈stack，用一个 bool 变量 tag标记右孩子已被访问把当前结点压栈，p=p-lchild 判断标志 tag 是否为1 输出结点值p = s.pop() p= p-rchild 结束N Y Y N N Y Y N 判断结点是否空判断栈或结点是否为空判断结点是否空名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 16 页 - - - - - - - - - 第 - 10 - 页 共 16 页三 、源代码下面给出的是实现递归和非递归遍历二叉树

11、的算法程序的源代码（合并在一起）：#include #include #define MAX 100 /定义堆栈最大容量enum BOOLFalse,True; enum RVISITRchildnovisit,Rchildvisit; /在后序遍历二叉树时用来指示是否已访问过右子树typedef struct BiTNode /定义二叉树节点结构char data; / 数据域struct BiTNode *lchild,*rchild; /左右孩子指针域BiTNode,*BiTree; typedef struct /定义堆栈结构BiTree elemMAX; /栈区int top; /栈

12、顶指针BiTreeStack; void Initial(BiTreeStack &); /初始化一个堆栈BOOL Push(BiTreeStack &,BiTree); / 将一个元素入栈BOOL Pop(BiTreeStack&,BiTree &); / 将一个元素出栈BOOL Gettop(BiTreeStack ,BiTree &); / 取得堆栈栈顶元素BOOL StackEmpty(BiTreeStack); /判断堆栈是否已空void CreateBiTree(BiTree &); /生成一个二叉树void PreOrder(BiTree); /先序非递归遍历二叉树void In

13、Order(BiTree); /中序非递归遍历二叉树void PostOrder(BiTree); /后序非递归遍历二叉树void PreTravel(BiTree ); /先序递归遍历二叉树void MidTravel(BiTree ); /中序递归遍历二叉树void PostTravel(BiTree ); /后序递归遍历二叉树int main() BiTree T; int flag=1; /标记BOOL temp; printf( 二叉树的递归和非递归遍历n); CreateBiTree(T); /生成一棵二叉树printf (n); 名师资料总结 - - -精品资料欢迎下载 - -

14、- - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 16 页 - - - - - - - - - 第 - 11 - 页 共 16 页printf( 递归先序遍历二叉树: ); PreTravel(T); printf(n); printf (n); printf( 递归中序遍历二叉树: ); MidTravel(T); printf(n); printf (n); printf( 递归后序遍历二叉树: ); PostTravel(T); printf(nnn); if(T) printf (nn); printf( 非递归

15、先序遍历二叉树: ); PreOrder(T); printf(n); else printf( 二叉树为空 n); if(T) printf( 非递归中序遍历二叉树: ); InOrder(T); printf(n); else printf( 二叉树为空 n); if(T) printf( 非递归后序遍历二叉树: ); PostOrder(T); printf(nnn); else printf( 二叉树为空 n); void Initial(BiTreeStack &S) S.top=-1; /栈顶指针初始化为-1 BOOL Push(BiTreeStack &S,BiTree ch)

16、/将元素ch 入栈，成功返回True,失败返回False if(S.top=MAX-1) return False; /判断是否栈满else S.top+; /栈顶指针top加一名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 16 页 - - - - - - - - - 第 - 12 - 页 共 16 页S.elemS.top=ch; /入栈return True; BOOL Pop(BiTreeStack &S,BiTree &ch) /将栈顶元素出栈,成功返回Tru

17、e，并用 ch返回该元素值，失败返回False if(S.top=-1) return False; /判断是否栈空else S.top-; /栈顶指针减一ch=S.elemS.top+1; return True; BOOL Gettop(BiTreeStack S,BiTree &ch) /取得栈顶元素，成功返回True，并用 ch返回该元素值，失败返回False if(S.top=-1) return False; else ch=S.elemS.top; /显示栈顶元素return True; BOOL StackEmpty(BiTreeStack S) /判断堆栈是否已空，若空返回T

18、rue,不空返回False if(S.topdata=ch; CreateBiTree(T-lchild); /生成左子树CreateBiTree(T-rchild); /生成右子树 void PreTravel(BiTree T) /先序遍历if(T) printf(%c,T-data); PreTravel(T-lchild); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 16 页 - - - - - - - - - 第 - 13 - 页 共 16 页PreTr

19、avel(T-rchild); void MidTravel(BiTree T) /中序遍历if(T) MidTravel(T-lchild); printf(%c,T-data); MidTravel(T-rchild); void PostTravel(BiTree T) /后序遍历if(T) PostTravel(T-lchild); PostTravel(T-rchild); printf(%c,T-data); void PreOrder(BiTree T) /先序非递归遍历以T 为根结点的二叉树BiTreeStack S; BiTree p; Initial(S); p=T; wh

20、ile(p|!StackEmpty(S) if(p) printf(%c,p-data); Push(S,p); p=p-lchild; else Pop(S,p); p=p-rchild; printf(n); void InOrder(BiTree T) /中序非递归遍历以T 为根结点的二叉树BiTreeStack S; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 16 页 - - - - - - - - - 第 - 14 - 页 共 16 页BiTree p;

21、 Initial(S); p=T; while(p|!StackEmpty(S) if(p) Push(S,p); p=p-lchild; else Pop(S,p); printf(%c,p-data); p=p-rchild; printf(n); void PostOrder(BiTree T) /后序非递归遍历以T 为根结点的二叉树BiTreeStack S; BiTree p,q; RVISIT tag; Initial(S); p=T; do while(p) Push(S,p); p=p-lchild; q=NULL; tag=Rchildvisit; while(!StackE

22、mpty(S)&tag) Gettop(S,p); if(p-rchild=q) printf(%c,p-data); Pop(S,p); q=p; else p=p-rchild; tag=Rchildnovisit; while(!StackEmpty(S); printf(n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 16 页 - - - - - - - - - 第 - 15 - 页 共 16 页四 、运算结果例：输入： 12 空格空格34 空格空格空格

23、即：12 34 图 7. 递归和非递归遍历二叉树结果图五、遇到的问题及解决这部分我主要遇到了如下两个问题，其内容与解决方法如下所列：问题 1 描述：初步完成编程的工作时，在输入二叉树的发现只能输入一个字符，而且程序不再进行，最后是自己的不小心将语句char a; scanf(%c,&a);中的 %c写为 %d导致的。问题 1 解决方法：将%d 改为%c 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 16 页 - - - - - - - - - 第 - 16 - 页 共

24、 16 页问题 2 描述：在构建二叉树的过程中，我最初用一重指针作为void Create() 的形参，导致创建的二叉树一直为空。后来经过深入思考，用二重指针实现了二叉树的构建。还有在编写主函数 void main( ) 时，最初没有没有在函数体最后加上”getchar();”存储回车， 导致调用创建函数构造二叉树时陷入莫名其妙的死循环。后来通过上网查阅资料，终于认识到错误所在。问题 2 解决方法：用二重指针实现了二叉树的构建，在函数体最后加上”getchar();”存储回车。六 、心得体会课程设计期间， 遇见一些问题， 一个就是怎样后序非递归遍历二叉树，经过分析和斟酌，终于得到比较满意的程序

25、，使得这个程序变得有一点意义。这一次的课程设计给我们提供了一个既能动手又动脑，独立实践的机会， 应该紧紧抓住这个机会把所学的专业课程进一步的巩固和加深， 进一步培养我们的综合能力。灵活运用各种数据类型组成一个具有系统性的程序。在这之中， 虽然每个人的思路不一样，但是拿一颗真诚热心去探讨问题就能更好的解决问题。 我们应该更能了解我们自己，自己还是太嫩， 需要我们学习的还有很多很多，成功是百分之九十九的汗水加上百分之一的灵感，所以我们的路还很长很长，或许是万里长城，或许还要翻山越岭，但是我们都应该永不放弃，不断提高， 更好地运用课堂学习的知识。通过这次作业我学到了很多东西，将以前学过的C+知识与现

26、在的课堂知识进行结合应用。重要的是使我知道了自学知识和合作的重要性，提高了自己动手能力和沟通能力，学到了许多解决实际问题的宝贵经验同时也挖掘出了我们潜在的能力，使我们对编程更有兴趣。我相信，只要努力、勤奋、坚持不懈，就没有什么做不到的事，不能还没开始就退缩，要勇于拼搏，敢于创新。 总之， 在通过又一次的真正动手之后，我在 C+设计方面获益匪浅，我会更加努力的学习编程方面的更多知识，提高自己的能力。然后一点一点的摸索，遇到了错误和同学一起讨论， 有问题自己想办法解决，最后程序调试出来的时候，会觉得真的很高兴。我知道，我们现在的水平还很差，要想学习好这门课，在以后就要多动手操作，书上的例题或算法，最好都自己编写程序实现，那样可以加深对算法的理解，也可以提高我们编程的水平。同时，很多的东西，理解了，可是在实现的时候还是有很多的错误发生，在以后的练习和实践中，应该多动手， 遇到问题多思考，即使方案不是最优的也要想办法自己解决，然后和好的方案进行比较。最后感谢苏老师在这次遍历二叉树课程设计上的悉心指导，祝老师身体健康，工作顺心，合家欢乐。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 16 页 - - - - - - - - -