Question

二叉树非递归后序遍历的思路是什么

Answer 1

前序：根-左-右；
中序：左-根-右；
后序：左-右-根。

遍历的思路有3个重点：
1）利用堆栈实现递归
2）树中结点要有指向父结点的指针 //后序遍历用不上这一条

3）树中结点要有标志记录是否已被访问过

上述3点其实就是自己来完成原来递归实现中系统帮你做的事
还有一点要注意，是“左-右-根”， 压栈就要先右后左

Class B-Tree{
B-Tree left;
B-Tree right;
B-Tree father;
Boolean visited = false; //初始值设为false

<Type> value; //树中存的值，可以是任何类型

}

Stack s<B-Tree>;
B-Tree t; //要遍历的树

s.push(t)
while (!s.empty()){
Boolean hasChildren = false; //hasChildren是有子结点需要处理的意思

t = s.top();
if(t.right <> null && ! t.right.visited) {
s.push(t.right);
hasChildren = true;

}
if (t.left <>null ! t.left.visited){
s.push(t.left);
hasChildren = true;
}
if (! hasChildren) {
out.print(t.value); // 输出结点
t.visited = true;
s.pop();

}
}