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

武汉工程大学计算机科学与工程学院《数据结构》实验报告专业班级实验地点学生学号指导教师学生姓名实验时间实验项目数的应用实验类别操作性（）验证性（）设计性（）综合性（Y）其它（）实验目的及要求（1）针对问题的实际要求，正确应用树形结构组织和存储数据；（2）掌握二叉树的存储方法。（3）掌握二叉树的各种遍历方法。成绩评定表类别评分标准分值得分合计上机表现积极出勤、遵守纪律认真完成实验任务30分报告质量程序代码规范、功能正确填写内容完整、体现收获70分说明：评阅教师：日期：年月日计算机科学与工程学院《数据结构》实验报告21.实验内容:二叉树后序遍历的非递归算法。实验说明：二叉树后序遍历的非递归算法：结点要入两次栈，出两次栈；为了区别同一个结点的两次出栈，设置标志flag，当结点进、出栈时，其标志flag也同时进、出栈。设根指针为root，则可能有以下两种情况：⑵若root!=NULL，则root及标志flag（置为1）入栈，遍历其左子树；⑵若root=NULL，此时若栈空，则整个遍历结束；若栈不空，则表明栈顶结点的左子树或右子树已遍历完毕。若栈顶结点的标志flag=1，则表明栈顶结点的左子树已遍历完毕，将flag修改为2，并遍历栈顶结点的右子树；若栈顶结点的标志flag=2，则表明栈顶结点的右子树也遍历完毕，输出栈顶结点。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，准备遍历栈顶结点的右子树；在这次试验当中有两个比较重要的地方一个是怎样讲一个二叉树输入到计算机中，另外，怎样用非递归的方法将这个二叉树遍历，所以经过思考后发小了解决的一些方法，像输入二叉树的时候就要应用到递归思想而二叉树的遍历的时候就要用到栈的应用3.源程序代码：#includeiostreamusingnamespacestd;#defineMAX100#defineMaxNode100typedefchardatatype;typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;bitree*root;intn;1第一次出栈，只遍历完左子树，该结点不能访问2第二次出栈，遍历完右子树，该结点可以访问flag＝计算机科学与工程学院《数据结构》实验报告3charc;bitree*creattree(){bitree*t;datatypex;cout\n请按照二叉树的规律依次输入各结点，以0作为每个节点的结束标志:;cinx;while((c=getchar())!='\n'&&c!=EOF);//清除缓冲区的方法if(x=='0')t=NULL;else{t=(structnode*)malloc(sizeof(bitree));t-data=x;t-lchild=creattree();t-rchild=creattree();}return(t);}voidpostorder(bitree*t)//后序遍历的非递归算法{bitree*p=t,*stack[MaxNode];//p表示当前结点，栈stack[]用来存储结点inttag[MAX];inttop=-1;do{while(p!=NULL)//先处理结点的左孩子结点，把所有左孩子依次入栈{stack[++top]=p;tag[top]=0;p=p-lchild;}if(top=0)//所有左孩子处理完毕后{if(!tag[top])//如果当前结点的右孩子还没被访问{p=stack[top];//输出栈顶结点，但不退栈，因为要先输出其孩子结点p=p-rchild;//处理其右孩子结点tag[top]=1;//表示栈中top位置存储的结点的右孩子被访问过了，下次轮到它退栈时可直接输出}else//如果该结点的左右孩子都被访问过了{coutstack[top--]-data;计算机科学与工程学院《数据结构》实验报告4}}}while((p!=NULL)||(top=0));}voidmain(){bitree*bintree=creattree();cout\n后根非递归遍历序列如下：\n\n;postorder(bintree);n=0;cout\nendl;}4.测试用例：1.当测试用例为如下所示的二叉树时，程序运行的结果如下：图表1计算机科学与工程学院《数据结构》实验报告52.当测试用例为如下所示的二叉树时，程序运行的结果如下：图表2计算机科学与工程学院《数据结构》实验报告6实验内容计算机科学与工程学院《数据结构》实验报告7实验总结本次试验发现了很多问题，开始的时候对着课本上的算法只有发呆，虽然课本上以及老师对于后序遍历非递归的算法讲得比较详细，但是我还是不知从何入手，在本次试验当中，关键是如何将二叉树输入计算机，以及二叉树的输出，后来通过大量的实践以及资料的查阅，慢慢的掌握了这次试验的编写.