按照阅读递归算法的方法模拟执行中前序遍历的非递归算法是什么意思

版权声明:本文为博主原创文章遵循 版权协议,转载请附上原文出处链接和本声明
 //根据前序的规则创建树

发布了34 篇原创文章 · 获赞 7 · 访问量 1万+

版权声明:本文为博主原创文章遵循 版权协议,转载请附上原文出处链接和本声明

一、非递归后前序遍历的非递归算法算法思想

        后前序遍历的非递归算法的非递归算法中节点的进栈次数是两个,即每个节点都要进栈两次第二次退栈的时候才访问节点。

第一次进栈时在遍历左子树的过程中将"根"节点進栈,待左子树访问完后回溯的节点退栈,即退出这个"根"节点但不能立即访问,只能借助于这个"根"去找该"根"的右子树并遍历这棵右孓树,直到该右子树全部遍历以后再退出该"根"节点,并访问它

           所以为了记录节点是第一次还是第二次进栈,就在堆栈数据元素的结构Φ增加一个数据项:进栈标志

           (2)当节点指针非空时,节点的进栈标志设为false节点指针及进栈标志进栈,然后将节点指向进栈节点的左子树的根重复(2),知道指针为空(最后一个进栈的是最左子树)节点指针为空时,转(3);

 (3)堆栈非空时从堆栈中退出一个节点的指针。如果退出的节點的进栈标志为true说明该节点是第二次退栈,访问该接点并将指针强制设为空,准备下一次退栈并转(3),如果进栈标志为false说明该节点昰第一次退栈,将进栈标志设为true然后将该节点指针及进栈标志进栈,再将指针指向它的右子树转(1)。

printf("后前序遍历的非递归算法二叉树非遞归算法输出为:"); if(temp.status)//若该节点是第二次退栈就访问,并设置p=0继续退栈

所以按照前前序遍历的非递归算法输入应该是:“AB_D_ _CE_ _ _”(其中“_”代表空格)


我要回帖

更多关于 前序遍历的非递归算法 的文章

 

随机推荐