二叉树后序遍历的非递归算法

1、武 汉 工 程 大 学计算机科学与工程学院数据结构实验报告专业班级 实验地点 学生学号 指导教师 学生姓名 实验时间实验项目数的应用实验类别操作性（）验证性（ ）设计性（ ）综合性（Y ）其它（ ）实验目的及要求（1）针对问题的实际要求，正确应用树形结构组织和存储数据；（2）掌握二叉树的存储方法。（3）掌握二叉树的各种遍历方法。成 绩 评 定 表类 别评 分 标 准分值得分合 计上机表现积极出勤、遵守纪律认真完成实验任务30分报告质量程序代码规范、功能正确填写内容完整、体现收获70分说明： 评阅教师： 日 期： 年 月 日1.实验内容:二叉树后序遍历的非递归算法。 实验说明：二叉树后序遍历的非

2、递归算法：结点要入两次栈，出两次栈；为了区别同一个结点的两次出栈，设置标志flag，当结点进、出栈时，其标志flag也同时进、出栈。1 第一次出栈，只遍历完左子树，该结点不能访问2 第二次出栈，遍历完右子树，该结点可以访问flag 设根指针为root，则可能有以下两种情况：2 若root!=NULL，则root及标志flag（置为1）入栈，遍历其左子树； 若root=NULL，此时若栈空，则整个遍历结束；若栈不空，则表明栈顶结点的左子树或右子树已遍历完毕。若栈顶结点的标志flag=1，则表明栈顶结点的左子树已遍历完毕，将flag修改为2，并遍历栈顶结点的右子树；若栈顶结点的标志flag=2，则

3、表明栈顶结点的右子树也遍历完毕，输出栈顶结点。2.实验分析：二叉树后序遍历的非递归算法伪代码如下：1. 栈s初始化； 2. 循环直到root为空且栈s为空 2.1 当root非空时循环 2.1.1将root连同标志flag=1入栈； 2.1.2 继续遍历root的左子树；2.2 当栈s非空且栈顶元素的标志为2时，出栈并输出栈顶结点;2.3 若栈非空，将栈顶元素的标志改为2，准备遍历栈顶结点的右子树；在这次试验当中有两个比较重要的地方一个是怎样讲一个二叉树输入到计算机中，另外，怎样用非递归的方法将这个二叉树遍历，所以经过思考后发小了解决的一些方法，像输入二叉树的时候就要应用到递归思想而二叉树的遍

4、历的时候就要用到栈的应用3.源程序代码：#include<iostream>using namespace std;#define MAX 100#define MaxNode 100typedef char datatype;typedef struct nodedatatype data;struct node *lchild,*rchild;bitree;bitree *root;int n;char c;bitree *creattree()bitree *t;datatype x;cout<<"n请按照二叉树的规律依次输入各结点，以0作为每个节点的结

5、束标志:"cin>>x;while(c=getchar()!='n'&&c!=EOF); /清除缓冲区的方法if(x='0')t=NULL;elset=(struct node *)malloc(sizeof(bitree);t->data=x;t->lchild=creattree();t->rchild=creattree();return(t);void postorder(bitree *t)/后序遍历的非递归算法 bitree *p=t, *stackMaxNode;/p表示当前结点，栈stack

6、用来存储结点 int tagMAX; int top=-1; do while(p != NULL)/先处理结点的左孩子结点，把所有左孩子依次入栈 stack+top = p; tagtop = 0; p = p->lchild; if(top >= 0) /所有左孩子处理完毕后 if(!tagtop) /如果当前结点的右孩子还没被访问 p = stacktop;/输出栈顶结点 ，但不退栈 ，因为要先输出其孩子结点 p = p->rchild; /处理其右孩子结点 tagtop = 1; /表示栈中top位置存储的结点的右孩子被访问过了，下次轮到它退栈时可直接输出 else

7、/如果该结点的左右孩子都被访问过了 cout<<stacktop->data<<" " while(p != NULL)|(top >= 0); void main()bitree *bintree=creattree();cout<<"n后根非递归遍历序列如下：nn"postorder(bintree);n=0;cout<<"n"<<endl; 4.测试用例：1.当测试用例为如下所示的二叉树时，程序运行的结果如下：图表 12.当测试用例为如下所示的二叉树时，程序运行的结果如下：图表 2实 验 内 容实 验 总 结本次试验发现了很多问题，开始的时候对着课本