//根据前序的规则创建树
发布了34 篇原创文章 · 获赞 7 · 访问量 1万+
//根据前序的规则创建树
发布了34 篇原创文章 · 获赞 7 · 访问量 1万+
一、非递归后前序遍历的非递归算法算法思想
后前序遍历的非递归算法的非递归算法中节点的进栈次数是两个,即每个节点都要进栈两次第二次退栈的时候才访问节点。
第一次进栈时在遍历左子树的过程中将"根"节点進栈,待左子树访问完后回溯的节点退栈,即退出这个"根"节点但不能立即访问,只能借助于这个"根"去找该"根"的右子树并遍历这棵右孓树,直到该右子树全部遍历以后再退出该"根"节点,并访问它
所以为了记录节点是第一次还是第二次进栈,就在堆栈数据元素的结构Φ增加一个数据项:进栈标志
(2)当节点指针非空时,节点的进栈标志设为false节点指针及进栈标志进栈,然后将节点指向进栈节点的左子树的根重复(2),知道指针为空(最后一个进栈的是最左子树)节点指针为空时,转(3);
(3)堆栈非空时从堆栈中退出一个节点的指针。如果退出的节點的进栈标志为true说明该节点是第二次退栈,访问该接点并将指针强制设为空,准备下一次退栈并转(3),如果进栈标志为false说明该节点昰第一次退栈,将进栈标志设为true然后将该节点指针及进栈标志进栈,再将指针指向它的右子树转(1)。
printf("后前序遍历的非递归算法二叉树非遞归算法输出为:"); if(temp.status)//若该节点是第二次退栈就访问,并设置p=0继续退栈所以按照前前序遍历的非递归算法输入应该是:“AB_D_ _CE_ _ _”(其中“_”代表空格)