递归和非递归遍历二叉树

《递归和非递归遍历二叉树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

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

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

5、的话将左孩子，将新结点入栈，然后再将指针指向当前结点的左子，直至左子为空，弹栈一个元素，作为当前结点，打印该栈顶元素，将指针指向当前结点右子，将右子作为新的结点，结点入栈，再次进行上面的判断，直至当前结点右子也为空，则再出栈一个元素作为当前结点，一直到结束，使得当前结点右子为空，且栈空，遍历结束。第-16-页共16页3.后续遍历：建立一个栈，然后定义一个tag，取值为0，1，0代表右子没有去过，1代表去过。①初始时指针指向根结点，将根结点压栈，指针指向左子，则将左子作为当前结点，继续判断直至左孩子为null，设q=n

6、ull，tag=1。然后取得栈顶元素，设为当前结点，判断当前结点的右孩子是否等于q，如果相等，则打印当前结点，然后弹出当前结点，并且令q=当前结点的值。然后继续判断，直至右孩子不等于q，则将指针指向右孩子，把右孩子设为当前结点，令tag=0，继续步骤①，直到全部元素弹栈，栈为空时，遍历结束。二、算法流程图开始判断结点是否为空null访问根结点结束先序方式遍历左子树先序方式遍历右子树是否图1.先序递归流程图第-16-页共16页开始判断结点是否空按中序方式遍历左子树结束访问根结点按中根遍历方式遍历右子树YN图2.中序递归

7、流程图第-16-页共16页开始判断结点是否空按后根遍历方式遍历左子树结束按后根遍历方式遍历右子树访问根结点YN图3.后序递归流程图第-16-页共16页开始申请一个栈stack判断结点是否空输出结点值，压栈，指针指向它的左孩子判断结点是否空弹出栈顶元素，指向结点的右孩子结束判断栈或结点是否空NYNYN图4.先序非递归流程图第-16-页共16页开始申请一个stack判断结点是否空把结点压栈，指针指向它的左孩子判断结点是否空弹栈，设为当前结点，打印结点值，指向右孩子结束判断栈或结点是否空NYYNN图1.流程图图2.流程图图

8、3..流程图图5.中序非递归流程图第-16-页共16页开始申请一个栈stack，用一个bool变量tag标记右孩子已被访问把当前结点压栈，p=p->lchildtop++判断标志tag是否为1输出结点值p=s.pop()p=p->rchild结束NYYNNYYN判断结点是否空判断栈或结点是否为空判断结点是否空图6.后序非递归流程图第-16-页共