后序遍歷按照“左孩子-右孩子-根結點”的順序進行訪問嫂粟。
1.遞歸實現
/**
* 后序遍歷
* @param node
*/
public static void postOrderTraverse(Node node) {
if (node == null) return;
postOrderTraverse(node.leftNode);
postOrderTraverse(node.rightNode);
System.out.print(node.data + "\t");
}
2.非遞歸實現
后序遍歷的非遞歸實現是三種遍歷方式中最難的一種。因為在后序遍歷中椰于，要保證左孩子和右孩子都已被訪問并且左孩子在右孩子前訪問才能訪問根結點淘菩，這就為流程的控制帶來了難題。
對于任一結點P霜幼，將其入棧嫩码，然后沿其左子樹一直往下搜索，直到搜索到沒有左孩子的結點罪既，此時該結點出現在棧頂铸题，但是此時不能將其出棧并訪問， 因此其右孩子還為被訪問琢感。所以接下來按照相同的規(guī)則對其右子樹進行相同的處理丢间，當訪問完其右孩子時，該結點又出現在棧頂驹针，此時可以將其出棧并訪問烘挫。這樣就 保證了正確的訪問順序〖砩可以看出饮六，在這個過程中其垄，每個結點都兩次出現在棧頂，只有在第二次出現在棧頂時卤橄，才能訪問它绿满。因此需要多設置一個變量標識該結點是 否是第一次出現在棧頂。
/**
* 后序遍歷 非遞歸
* 雙棧法
* @param root
*/
public static void postOrder2(Node root) {
Stack<Node> stack = new Stack<Node>();
Stack<Node> output = new Stack<Node>();
Node node = root;
while (node != null || !stack.isEmpty()) {
if (node != null) {
stack.push(node);
output.push(node);
node = node.rightNode;
} else {
node = stack.pop();
node = node.leftNode;
}
}
while (output.size() > 0) {
Node n = output.pop();
System.out.print(n.data + "\t");
}
}
