求二叉树的前序遍历和后序遍历的算法（非递归）

用c语言写

高考大战 · 2018-4-30 01:56:30

百度一下就可以知道答案了。直接搜”二叉树的前序遍历和后序遍历的算法“
第一条就是：
http://blog.csdn.net/sky04/article/details/4510266
我只解释一下先序遍历非递归算法，其他的自学一下吧！：
//先序遍历非递归算法
void聽PreOrderUnrec(Bitree聽*t)
{
聽聽聽聽Stack聽s;聽聽聽聽聽聽
聽聽聽聽StackInit(s);聽聽聽聽//初始化
聽聽聽聽Bitree聽*p=t;聽聽聽聽聽//聽二叉树根节点
聽聽聽聽
聽聽聽聽while聽(p!=NULL聽||聽!StackEmpty(s))
聽聽聽聽{
聽聽聽聽聽聽聽聽while聽(p!=NULL)聽聽聽聽聽聽聽聽聽聽聽聽聽//遍历左子树
聽聽聽聽聽聽聽聽{
聽聽聽聽聽聽聽聽聽聽聽聽visite(p->data);
聽聽聽聽聽聽聽聽聽聽聽聽push(s,p);
聽聽聽聽聽聽聽聽聽聽聽聽p=p->lchild;聽聽聽聽聽聽//lchild聽左子树
聽聽聽聽聽聽聽聽}
聽聽聽聽聽聽聽聽
聽聽聽聽聽聽聽聽if聽(!StackEmpty(s))聽聽聽聽聽聽聽聽聽//通过下一次循环中的内嵌while实现右子树遍历
聽聽聽聽聽聽聽聽{
聽聽聽聽聽聽聽聽聽聽聽聽p=pop(s);
聽聽聽聽聽聽聽聽聽聽聽聽p=p->rchild;聽聽聽聽聽//rchild聽右子树聽聽聽
聽聽聽聽聽聽聽聽}//endif
聽聽聽聽聽聽聽聽
聽聽聽聽}//endwhile聽
}

/*聽聽Stack聽s聽；创建堆栈。这也是堆栈的一个应用。既然你已经学到了二叉树，就应该知道堆栈，可以把以前编写的堆栈程序拿来用。
POP，PUSH聽堆栈的弹出，压栈。
按照该程序步骤，来演示聽s聽和指针聽p聽的内容：（完全二叉树为例）
前序遍历次序为：ABCDEFG
1.第一次执行聽while语句后聽
栈聽s[底部，ABC]聽聽聽p=NULL聽聽访问了聽：ABC节点
2.第一次执行聽if
栈聽s[底部，AB]聽聽聽p=NULL聽聽访问了聽：ABC节点聽由于c的右子树为空，所以p=NULL
3.第二次跳过了聽while
4.第二次执行聽if
栈聽s[底部，A]聽聽聽p指向了D聽聽访问了：ABC节点
5.第三次执行聽while语句后聽
栈聽s[底部，AD]聽聽聽p=NULL聽聽聽访问了：ABCD节点，本次while循环，只访问了D
。
。
。
聽剩下步骤的自己来吧!
聽实际上，递归也是在操作堆栈。
聽一般的书上应该有这么类似的话：
聽“利用一个辅助堆栈，可以将递归算法转化为等价的分递归算法”
聽
*/

求二叉树的前序遍历和后序遍历的算法（非递归）

1 个回复