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

1、计算机科学与工程学院数据结构实验报告说明:评阅教师：日期：年月日1.实验内容：二叉树后序遍历的非递归算法。实验说明：二叉树后序遍历的非递归算法：结点要入两次栈，出两次栈；为了区别同一个结点的两次出栈，设置标志flag,当结点进、出栈时，其标志flag也同时进、出栈。f1第一次出栈，只遍历完左子树，该结点不能访问flag=I2第二次出栈，遍历完右子树，该结点可以访问设根指针为root,则可能有以下两种情况：若root!=NULL,则root及标志flag（置为1）入栈，遍历其左子树；若root=NULL,此时若栈空，则整个遍历结束；若栈不空，则表明栈顶结点的左子树或右子树已遍历完毕。若栈顶结点的

2、标志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、递归的方法将这个二叉树遍历，所以经过思考后发小了解决的一些方法，像输入二叉树的时候就要应用到递归思想而二叉树的遍历的时候就要用到栈的应用3.源程序代码：#includeusingnamespacestd;#defineMAX100#defineMaxNode100typedefchardatatype;typedefstructnodedatatypedata;structnode*lchild,*rchild;bitree;bitree*root;intn;charc;bitree*creattree()(bitree*t;datatypex;coutx;while(c=getchar()!

4、=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,*stackMaxNode;/p表示当前结点，栈stack口用来存储结点inttagMAX;inttop=-1;do(while(p!=NULL)/先处理结点的左孩子结点，把所有左孩子依次入栈(stack+top=p;tagtop=0

5、;p=p-lchild;if(top=0)/所有左孩子处理完毕后(if(!tagtop)/如果当前结点的右孩子还没被访问(p=stacktop;/输出栈顶结点，但不退栈，因为要先输出其孩子结点p=p-rchild;/处理其右孩子结点tagtop=1;/表示栈中top位置存储的结点的右孩子被访问过了，下次轮到它退栈时可直接输出else/如果该结点的左右孩子都被访问过了(coutdata=0);)voidmain()(bitree*bintree=creattree();coutn后根非递归遍历序列如下：nn;postorder(bintree);n=0;coutnendl;4.测试用例：1.当测

6、试用例为如下所示的二叉树时，程序运行的结果如下：图表1青按照二叉树的规律依次输入各结点，以。作为每个节京的结束标忐通音按服二叉树的规律依次输入各结点，以啖为每个节点的结束标志通*按照一叉树的规律依次输入各站怠.以M M乍为每个节点的结束标志切音按照二叉树的规律依状输入各结点，以金为每个节点的结束标志青按照二叉树的规律依我输入各结点， 刎乍为每个节点的结束标志G G者按四二叉树的规律依次输入各结点.以川乍为每个节点的结束标志册*按照二叉树的规律依次输入各结点，以用乍为每个节点的结束标志濯青按理二叉树的规律依次输入各结点.以朗乍为每个节点的结束标志泅清按照二叉树的规律依次输入各结点,以川午为每个节

7、点的结束标志透请按照二叉树的规律你我输入各结点.以作为每个节点的结束标志:E E请按熙二叉树的规律依次输入咎结点，以且作为每个节点的结束标志组储持照二文树的现律依就输入各结点.以&作为每个节点的结集标志：0 0图表2 DADAProgr0mFilcMiroProgr0mFilcMiro导口代yiyi3 3u uj jI IStuStud di iMyProjMyProjectectn nQDDQDDe ebug*bug*。后XE”二请按照二叉树的规律依次输入各结点请按照二叉树的规律依次输入各结点请按期二叉树的规律依次输入各结点请按照二叉制的规律依次输入各结点请按照二叉树的规律依次输入各结点请按

8、照二叉树的规律依次输入各结点请按照二叉树的规律依次输入各结点请按照二叉树的规律依次输入各结点请按照二叉树的规律依次输入各结点后根非递归遍历序列如下请按照二叉树的规律依次输入各结点以匕作为每个节点的结束标志沙请按照二叉树的规律依次输入各结点以国作为每个节点的结束标志打请按照二叉树的规律依次输入各结点以制作为每个节点的结束标志浦请按照二叉树的规律依次输入各结点以a a作为每个节点的结束标志以。作为每个节点的结束标志;E E以作为每个节点的结束标志以酬作为每个节点的结束标志:F F以。作为每个节点的结束标志.。以修作为每个节点的结束标志的请按既二叉树的规律依次输入各结点以0 0作为每个节点的结束标志:C C以田乍为每个节点的结束标志透以。作为每个节点的结束标志 6请按照二叉树的规律依次输入各结点以。作为每个节点的结束标志;G G以作为每个节点的结束标志以0 0作为每个节点的结束标志评PressanvkeytocontinuePressanvkeytocontinue实验内容