当前位置 博文首页 > kbtx的博客：王道课后练习之二叉树的非递归后序遍历
首先毫无疑问，非递归的后续遍历必定要借助栈来实现，我们先用祖传的二叉树做个开头
根据页面提示，我们知道它的后序遍历结果为
7 -> 3 -> 4 -> 1 -> 5 -> 6 -> 2 -> 0
点击此处可以访问这个在线生成二叉树的页面
现在用Java实现代码，我们对节点Node及相关操作定义如下：
class Node{
int data;
Node left_child,right_child;
Node parent;
public Node(int data) {
this.data = data;
}
public void visit(){
System.out.print(String.format("%d -> ",data));
}
public void setLeft_child(Node left_child) {
this.left_child = left_child;
left_child.parent = this;
}
public Node setLeft_child(int left_child) {
this.left_child = new Node(left_child);
this.left_child.parent = this;
return this.left_child;
}
public void setRight_child(Node right_child) {
this.right_child = right_child;
right_child.parent = this;
}
public Node setRight_child(int right_child) {
this.right_child = new Node(right_child);
this.right_child.parent = this;
return this.right_child;
}
public Node getLeft_child() {
return left_child;
}
public Node getRight_child() {
return right_child;
}
public void postOrder_r(){
if(this.getLeft_child()!=null) {
this.getLeft_child().postOrder_r();
}
if(this.getRight_child()!=null) {
this.getRight_child().postOrder_r();
}
this.visit();
}
public void postOrder(){}
}
其中postOrder_r是常用的递归后序遍历，很容易验证其正确性；postOrder是非递归实现的，目前为空
我们编写了如下的测试代码，如果两行输出内容一样就能证明算法是正确的
public static void main(String[] args) {
Node root = new Node(0);
root.setLeft_child(1).setLeft_child(3).setLeft_child(7);
root.getLeft_child().setRight_child(4);
root.setRight_child(2).setRight_child(6);
root.getRight_child().setLeft_child(5);
root.postOrder_r();
System.out.println();
root.postOrder();
}
下面要设法实现非递归后序遍历
如何实现？
首先考虑只有三个节点的情况：
后序遍历的结果必然是 左右根 也就是 1->2->0
因此，在一般情况下当我们处理一个给定的节点的时候，要按照相反的顺序将其自身、右、左子树入栈（栈顶为左子树），这样才能保证左子树早于右子树，右子树早于自身的出栈顺序。将自身入栈的操作只需要进行一次，而将左右子树入栈的代码则处在循环中，因为自身入栈可以认为是一种初始化操作
Stack<Node> stack = new Stack<>();
//将自身入栈，此操作只需要执行一次
stack.push(this);
while(true){
Node top = stack.peek();
if(top.right_child != null){
stack.push(top.right_child);
}
if(top.left_child!=null){
stack.push(top.left_child);
}
}
目前，代码将在正确将所有节点入栈后陷入死循环。
下面观察一下出栈节点需要满足的条件：
第一个出栈的节点为 7 ，首先它是整个子树里最靠左的节点（简称极左节点），其次，它还是个叶子节点，所以我们很自然的想到如果我们栈顶出现了一个叶子节点，应该将其出栈并访问，也就是：
if(top.left_child==null&&top.right_child==null){
stack.pop().visit();
}else{...}
可是这样又会导致另一个问题，当7出栈，3到达栈顶的时候，程序会转而执行else的部分，而不是将3出栈，这样就会把7再次请进来从而造成死循环。
所幸，这样的死循环只是出现在父子节点之间，因此我们增加一个prev表示最后一个出栈的节点，判断当前栈顶节点是不是最后出栈的节点的父节点，如果是则继续执行出栈逻辑，如果为否才入栈子节点。
为了省去判空逻辑，我们可以将prev初始化为 this。
到此我们也清楚循环的终止条件了，栈空。
Node top = stack.peek();
Node prev = this;
while(!stack.isEmpty()){
if((top.left_child==null&&top.right_child==null) ||(prev.parent==top)){
prev = stack.pop();
prev.visit();
}else{...}
}
总结整个代码的逻辑，只考虑入栈部分，就是 将根节点 的 自身、右子树、左子树 入栈，非根节点则将其 右子树、左子树 入栈；考虑出栈时，当栈顶为叶子节点时将其出栈，同时记录这个节点，如果栈顶为非叶子节点，则检查栈顶节点是不是记录的节点的父节点，如果是则出栈，不是则将其 右子树、左子树 入栈，直到栈空为止。
import java.util.Stack;
class Node{
int data;
Node left_child,right_child;
Node parent;
public Node(int data) {
this.data = data;
}
public void visit(){
System.out.print(String.format("%d -> ",data));
}
public void setLeft_child(Node left_child) {
this.left_child = left_child;
left_child.parent = this;
}
public Node setLeft_child(int left_child) {
this.left_child = new Node(left_child);
this.left_child.parent = this;
return this.left_child;
}
public void setRight_child(Node right_child) {
this.right_child = right_child;
right_child.parent = this;
}
public Node setRight_child(int right_child) {
this.right_child = new Node(right_child);
this.right_child.parent = this;
return this.right_child;
}
public Node getLeft_child() {
return left_child;
}
public Node getRight_child() {
return right_child;
}
public void postOrder_r(){
if(this.getLeft_child()!=null) {
this.getLeft_child().postOrder_r();
}
if(this.getRight_child()!=null) {
this.getRight_child().postOrder_r();
}
this.visit();
}
public void postOrder(){
Stack<Node> stack = new Stack<>();
stack.push(this);
Node prev = this;
