本題來自左神《程序員代碼面試指南》“分別用遞歸和非遞歸方式實現二叉樹先序、中序和后序遍歷”題目。

題目

用遞歸和非遞歸方式，分別按照二叉樹先序、中序和后序打印所有的節點。

我們約定：

• 先序遍歷順序為根、左、右；
• 中序遍歷順序為左、根、右；
• 后序遍歷順序為左、右、根。

二叉樹節點定義如下：

public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value = data;} }

題解

1、用遞歸方式

用遞歸方式實現三種遍歷是教材上的基礎內容，本文不再詳述，直接給出代碼實現。

// 前序遍歷 public static void preOrderRecur(Node head) {if (head == null) {return;}System.out.print(head.value + " ");preOrderRecur(head.left);preOrderRecur(head.right); }// 中序遍歷 public static void inOrderRecur(Node head) {if (head == null) {return;}inOrderRecur(head.left);System.out.print(head.value + " ");inOrderRecur(head.right); }// 后序遍歷 public static void posOrderRecur(Node head) {if (head == null) {return;}posOrderRecur(head.left);posOrderRecur(head.right);System.out.print(head.value + " "); }

2、用非遞歸方式

（1）前序遍歷

用遞歸方法解決的問題都能用非遞歸的方法實現。這是因為遞歸方法無非就是利用函數棧來保存信息，如果用自己申請的數據結構來代替函數棧，也可以實現相同的功能。用非遞歸的方式實現二叉樹的先序遍歷，具體過程如下：

1．申請一個新的棧，記為stack。然后將頭節點head 壓入stack 中。
2．從 stack 中彈出棧頂節點，記為 cur，然后打印 cur 節點的值，再將節點cur 的右孩子節點（不為空的話）先壓入stack 中，最后將cur 的左孩子節點（不為空的話）壓入stack 中。
3．不斷重復步驟2，直到 stack 為空，全部過程結束。

下面舉例說明整個過程，一棵二叉樹如圖 3-1 所示：

節點 1 先入棧，然后彈出并打印。接下來先把節點3 壓入stack，再把節點2 壓入，stack從棧頂到棧底依次為 2，3。
節點 2 彈出并打印，把節點5 壓入stack，再把節點4 壓入，stack 從棧頂到棧底為 4，5，3。
節點 4 彈出并打印，節點4 沒有孩子節點壓入stack，stack 從棧頂到棧底依次為 5，3。
節點 5 彈出并打印，節點5 沒有孩子節點壓入stack，stack 從棧頂到棧底依次為 3。
節點 3 彈出并打印，把節點7 壓入stack，再把節點6 壓入，stack 從棧頂到棧底為 6，7。
節點 6 彈出并打印，節點6 沒有孩子節點壓入stack，stack 目前從棧頂到棧底為 7。
節點 7 彈出并打印，節點7 沒有孩子節點壓入stack，stack 已經為空，過程停止。

整個過程請參看如下代碼中的 preOrderUnRecur 方法。

public static void preOrderUnRecur(Node head) {System.out.print("pre-order: ");if (head != null) {Stack<Node> stack = new Stack<Node>();stack.add(head);while (!stack.isEmpty()) {head = stack.pop(); // 彈出棧頂元素System.out.print(head.value + " ");if (head.right != null) { // 左子樹進棧stack.push(head.right);}if (head.left != null) { // 右子樹進棧stack.push(head.left);}}}System.out.println(); }

（2）中序遍歷

用非遞歸的方式實現二叉樹的中序遍歷，具體過程如下：

1．申請一個新的棧，記為 stack。初始時，令變量 cur=head。
2．先把 cur 節點壓入棧中，對以 cur 節點為頭節點的整棵子樹來說，依次把左邊界壓入棧中，即不停地令 cur=cur.left，然后重復步驟 2。
3．不斷重復步驟2，直到發現 cur 為空，此時從 stack 中彈出一個節點，記為 node。打印 node 的值，并且讓 cur=node.right，然后繼續重復步驟 2。
4．當 stack 為空且 cur 為空時，整個過程停止。

還是用圖 3-1 的例子來說明整個過程。

初始時 cur 為節點1，將節點1 壓入stack，令cur=cur.left，即cur 變為節點2。（步驟1+步驟2）
cur 為節點2，將節點2 壓入stack，令cur=cur.left，即cur 變為節點4。（步驟2）
cur 為節點4，將節點4 壓入stack，令cur=cur.left，即cur 變為null，此時stack 從棧頂到棧底為4，2，1。（步驟2）
cur 為null，從stack 彈出節點4（node）并打印，令cur=node.right，即cur 為null，此時stack 從棧頂到棧底為2，1。（步驟3）
cur 為null，從stack 彈出節點2（node）并打印，令cur=node.right，即cur 變為節點5，此時stack 從棧頂到棧底為1。（步驟3）
cur 為節點5，將節點5 壓入stack，令cur=cur.left，即cur 變為null，此時stack 從棧頂到棧底為5，1。（步驟2）
cur 為null，從stack 彈出節點5（node）并打印，令cur=node.right，即cur 仍為null，此時stack 從棧頂到棧底為1。（步驟3）
cur 為null，從stack 彈出節點1（node）并打印，令cur=node.right，即cur 變為節點3，此時stack 為空。（步驟3）
cur 為節點3，將節點3 壓入stack，令cur=cur.left，即cur 變為節點6，此時stack 從棧頂到棧底為3。（步驟2）
cur 為節點6，將節點6 壓入stack，令cur=cur.left，即cur 變為null，此時stack 從棧頂到棧底為6，3。（步驟2）
cur 為null，從stack 彈出節點6（node）并打印，令cur=node.right，即cur 仍為null，此時stack 從棧頂到棧底為3。（步驟3）
cur 為null，從stack 彈出節點3（node）并打印，令cur=node.right，即cur 變為節點7，此時stack 為空。（步驟3）
cur 為節點7，將節點7 壓入stack，令cur=cur.left，即cur 變為null，此時stack 從棧頂到棧底為7。（步驟2）
cur 為null，從stack 彈出節點7（node）并打印，令cur=node.right，即cur 仍為null，此時stack 為空。（步驟3）
cur 為null，stack 也為空，整個過程停止。（步驟4）

通過與例子結合的方式我們發現，步驟1 到步驟4 就是依次先打印左子樹，然后打印每棵子樹的頭節點，最后打印右子樹。
全部過程請參看如下代碼中的 inOrderUnRecur 方法。

public static void inOrderUnRecur(Node head) {System.out.print("in-order: ");if (head != null) {Stack<Node> stack = new Stack<Node>();while (!stack.isEmpty() || head != null) {if (head != null) { // 如果向左沒走到頭，則不斷向左走，并將遍歷過的元素入棧stack.push(head);head = head.left;} else { // 如果向左走到頭了，則出棧一個元素，然后將其右孩子入棧head = stack.pop();System.out.print(head.value + " ");head = head.right;}}}System.out.println(); }

（3）后序遍歷

用非遞歸的方式實現二叉樹的后序遍歷有點麻煩，本書介紹以下兩種方法供讀者參考。

先介紹用 兩個棧 實現后序遍歷的過程，具體過程如下：

1．申請一個棧，記為 s1，然后將頭節點 head 壓入s1 中。
2．從 s1 中彈出的節點記為 cur，然后依次將 cur 的 左孩子節點 和 右孩子節點 壓入 s1 中。
3．在整個過程中，每一個從 s1 中彈出的節點都放進 s2 中。
4．不斷重復 步驟2 和 步驟3，直到 s1 為空，過程停止。
5．從 s2 中依次彈出節點并打印，打印的順序就是后序遍歷的順序。

還是用 圖3-1 的例子來說明整個過程。

節點 1 放入 s1 中。
從 s1 中彈出節點1，節點1 放入s2，然后將節點2 和節點3 依次放入s1，此時s1 從棧頂到棧底為3，2；s2 從棧頂到棧底為1。
從 s1 中彈出節點3，節點3 放入s2，然后將節點6 和節點7 依次放入s1，此時s1 從棧頂到棧底為7，6，2；s2 從棧頂到棧底為3，1。
從 s1 中彈出節點7，節點7 放入s2，節點7 無孩子節點，此時s1 從棧頂到棧底為6，2；s2 從棧頂到棧底為7，3，1。
從 s1 中彈出節點6，節點6 放入s2，節點6 無孩子節點，此時s1 從棧頂到棧底為2；s2從棧頂到棧底為6，7，3，1。
從 s1 中彈出節點2，節點2 放入s2，然后將節點4 和節點5 依次放入s1，此時s1 從棧頂到棧底為5，4；s2 從棧頂到棧底為2，6，7，3，1。
從 s1 中彈出節點5，節點5 放入s2，節點5 無孩子節點，此時s1 從棧頂到棧底為4；s2從棧頂到棧底為5，2，6，7，3，1。
從 s1 中彈出節點4，節點4 放入s2，節點4 無孩子節點，此時s1 為空；s2 從棧頂到棧底為4，5，2，6，7，3，1。

過程結束，此時只要依次彈出s2 中的節點并打印即可，順序為4，5，2，6，7，3，1。
通過如上過程我們知道，每棵子樹的頭節點都最先從 s1 中彈出，然后把該節點的孩子節點按照先左再右的順序壓入 s1，那么從 s1 彈出的順序就是先右再左，所以從 s1 中彈出的順序就是中、右、左。然后，s2 重新收集的過程就是把 s1 的彈出順序逆序，所以 s2 從棧頂到棧底的順序就變成了左、右、中。

使用兩個棧實現后序遍歷的全部過程請參看如下代碼中的 posOrderUnRecur1 方法。

public static void posOrderUnRecur1(Node head) {System.out.print("pos-order: ");if (head != null) {Stack<Node> s1 = new Stack<Node>();Stack<Node> s2 = new Stack<Node>();s1.push(head);while (!s1.isEmpty()) {head = s1.pop();s2.push(head); // 每一個從 s1 中彈出的節點都放進 s2 中if (head.left != null) {s1.push(head.left); // 將 cur 的左孩子節點壓入 s1 中}if (head.right != null) {s1.push(head.right); // 將 cur 的右孩子節點壓入 s1 中}}while (!s2.isEmpty()) { // 從 s2 中依次彈出節點并打印System.out.print(s2.pop().value + " ");}}System.out.println(); }

最后介紹只用一個棧實現后序遍歷的過程，具體過程如下。

1．申請一個棧，記為 stack，將頭節點壓入 stack，同時設置兩個變量 h 和 c。在整個流程中，h 代表最近一次彈出并打印的節點，c 代表 stack 的棧頂節點，初始時 h 為頭節點，c 為 null。

2．每次令 c 等于當前 stack 的棧頂節點，但是不從 stack 中彈出，此時分以下三種情況。

• ① 如果 c 的左孩子節點不為null，并且 h 不等于 c 的左孩子節點，也不等于 c 的右孩子節點，則把 c 的左孩子節點壓入 stack 中。
  （具體解釋一下這么做的原因。首先 h 的意義是最近一次彈出并打印的節點，且后續遍歷的打印順序是“左-中-右”，所以，如果 h 等于 c 的左孩子節點，說明 c 的左子樹已經打印完畢；如果 h 等于 c 的右孩子節點，說明 c 的左子樹與右子樹都已經打印完畢。所以無論 h 等于 c 的左孩子節點還是右孩子節點，此時都不應該再將 c 的左孩子節點放入 stack 中。否則，說明左子樹還沒處理過，那么將 c 的左孩子節點壓入 stack 中。）
• ② 如果條件①不成立，并且 c 的右孩子節點不為 null，h 不等于 c 的右孩子節點，則把 c 的右孩子節點壓入 stack 中。
  （具體解釋一下這么做的原因。如果 h 等于 c 的右孩子節點，說明 c 的右子樹已經打印完畢，此時不應該再將 c 的右孩子節點放入 stack 中。否則，說明右子樹還沒處理過，此時將 c 的右孩子節點壓入 stack 中。）
• ③ 如果條件①和條件②都不成立，說明 c 的左子樹和右子樹都已經打印完畢，那么從 stack 中彈出 c 并打印，然后令 h=c。

3．一直重復步驟2，直到 stack 為空，過程停止。

依然用圖 3-1 的例子來說明整個過程。

節點 1 壓入stack，初始時h 為節點1，c 為null，stack 從棧頂到棧底為1。
令c 等于stack 的棧頂節點——節點1，此時步驟2 的條件①命中，將節點2 壓入stack，h為節點1，stack 從棧頂到棧底為2，1。
令c 等于stack 的棧頂節點——節點2，此時步驟2 的條件①命中，將節點4 壓入stack，h為節點1，stack 從棧頂到棧底為4，2，1。
令c 等于stack 的棧頂節點——節點4，此時步驟2 的條件③命中，將節點4 從stack 中彈出并打印，h 變為節點4，stack 從棧頂到棧底為2，1。
令c 等于stack 的棧頂節點——節點2，此時步驟2 的條件②命中，將節點5 壓入stack，h為節點4，stack 從棧頂到棧底為5，2，1。
令c 等于stack 的棧頂節點——節點5，此時步驟2 的條件③命中，將節點5 從stack 中彈出并打印，h 變為節點5，stack 從棧頂到棧底為2，1。
令c 等于stack 的棧頂節點——節點2，此時步驟2 的條件③命中，將節點2 從stack 中彈出并打印，h 變為節點2，stack 從棧頂到棧底為1。
令c 等于stack 的棧頂節點——節點1，此時步驟2 的條件②命中，將節點3 壓入stack，h為節點2，stack 從棧頂到棧底為3，1。
令c 等于stack 的棧頂節點——節點3，此時步驟2 的條件①命中，將節點6 壓入stack，h為節點2，stack 從棧頂到棧底為6，3，1。
令c 等于stack 的棧頂節點——節點6，此時步驟2 的條件③命中，將節點6 從stack 中彈出并打印，h 變為節點6，stack 從棧頂到棧底為3，1。
令c 等于stack 的棧頂節點——節點3，此時步驟2 的條件②命中，將節點7 壓入stack，h為節點6，stack 從棧頂到棧底為7，3，1。
令c 等于stack 的棧頂節點——節點7，此時步驟2 的條件③命中，將節點7 從stack 中彈出并打印，h 變為節點7，stack 從棧頂到棧底為3，1。
令c 等于stack 的棧頂節點——節點3，此時步驟2 的條件③命中，將節點3 從stack 中彈出并打印，h 變為節點3，stack 從棧頂到棧底為1。
令c 等于stack 的棧頂節點——節點1，此時步驟2 的條件③命中，將節點1 從stack 中彈出并打印，h 變為節點1，stack 為空。過程結束。

只用一個棧實現后序遍歷的全部過程請參看如下代碼中的 posOrderUnRecur2 方法。

public static void posOrderUnRecur2(Node h) {System.out.print("pos-order: ");if (h != null) { // h 代表最近一次彈出并打印的節點Stack<Node> stack = new Stack<Node>();stack.push(h);Node c = null; // c 代表 stack 的棧頂節點while (!stack.isEmpty()) {c = stack.peek();if (c.left != null && h != c.left && h != c.right) { // 說明 c 的左子樹還沒處理過stack.push(c.left);} else if (c.right != null && h != c.right) { // 說明 c 的右子樹還沒處理過stack.push(c.right);} else { // 說明 c 的左子樹和右子樹都已經打印完畢System.out.print(stack.pop().value + " ");h = c;}}}System.out.println(); }

附：完整代碼（含測試用例）

package chapter_3_binarytreeproblem;import java.util.Stack;public class Problem_01_PreInPosTraversal {public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value = data;}}public static void preOrderRecur(Node head) {if (head == null) {return;}System.out.print(head.value + " ");preOrderRecur(head.left);preOrderRecur(head.right);}public static void inOrderRecur(Node head) {if (head == null) {return;}inOrderRecur(head.left);System.out.print(head.value + " ");inOrderRecur(head.right);}public static void posOrderRecur(Node head) {if (head == null) {return;}posOrderRecur(head.left);posOrderRecur(head.right);System.out.print(head.value + " ");}public static void preOrderUnRecur(Node head) {System.out.print("pre-order: ");if (head != null) {Stack<Node> stack = new Stack<Node>();stack.add(head);while (!stack.isEmpty()) {head = stack.pop(); // 彈出棧頂元素System.out.print(head.value + " ");if (head.right != null) { // 左子樹進棧stack.push(head.right);}if (head.left != null) { // 右子樹進棧stack.push(head.left);}}}System.out.println();}public static void inOrderUnRecur(Node head) {System.out.print("in-order: ");if (head != null) {Stack<Node> stack = new Stack<Node>();while (!stack.isEmpty() || head != null) {if (head != null) { // 如果向左沒走到頭，則不斷向左走，并將遍歷過的元素入棧stack.push(head);head = head.left;} else { // 如果向左走到頭了，則出棧一個元素，然后將其右孩子入棧head = stack.pop();System.out.print(head.value + " ");head = head.right;}}}System.out.println();}public static void posOrderUnRecur1(Node head) {System.out.print("pos-order: ");if (head != null) {Stack<Node> s1 = new Stack<Node>();Stack<Node> s2 = new Stack<Node>();s1.push(head);while (!s1.isEmpty()) {head = s1.pop();s2.push(head); // 每一個從 s1 中彈出的節點都放進 s2 中if (head.left != null) {s1.push(head.left); // 將 cur 的左孩子節點壓入 s1 中}if (head.right != null) {s1.push(head.right); // 將 cur 的右孩子節點壓入 s1 中}}while (!s2.isEmpty()) { // 從 s2 中依次彈出節點并打印System.out.print(s2.pop().value + " ");}}System.out.println();}public static void posOrderUnRecur2(Node h) {System.out.print("pos-order: ");if (h != null) { // h 代表最近一次彈出并打印的節點Stack<Node> stack = new Stack<Node>();stack.push(h);Node c = null; // c 代表 stack 的棧頂節點while (!stack.isEmpty()) {c = stack.peek();if (c.left != null && h != c.left && h != c.right) { // 說明 c 的左子樹還沒處理過stack.push(c.left);} else if (c.right != null && h != c.right) { // 說明 c 的右子樹還沒處理過stack.push(c.right);} else { // 說明 c 的左子樹和右子樹都已經打印完畢System.out.print(stack.pop().value + " ");h = c;}}}System.out.println();}public static void main(String[] args) {Node head = new Node(5);head.left = new Node(3);head.right = new Node(8);head.left.left = new Node(2);head.left.right = new Node(4);head.left.left.left = new Node(1);head.right.left = new Node(7);head.right.left.left = new Node(6);head.right.right = new Node(10);head.right.right.left = new Node(9);head.right.right.right = new Node(11);// recursiveSystem.out.println("==============recursive==============");System.out.print("pre-order: ");preOrderRecur(head);System.out.println();System.out.print("in-order: ");inOrderRecur(head);System.out.println();System.out.print("pos-order: ");posOrderRecur(head);System.out.println();// unrecursiveSystem.out.println("============unrecursive=============");preOrderUnRecur(head);inOrderUnRecur(head);posOrderUnRecur1(head);posOrderUnRecur2(head);} }

運行結果：

==============recursive============== pre-order: 5 3 2 1 4 8 7 6 10 9 11 in-order: 1 2 3 4 5 6 7 8 9 10 11 pos-order: 1 2 4 3 6 7 9 11 10 8 5 ============unrecursive============= pre-order: 5 3 2 1 4 8 7 6 10 9 11 in-order: 1 2 3 4 5 6 7 8 9 10 11 pos-order: 1 2 4 3 6 7 9 11 10 8 5 pos-order: 1 2 4 3 6 7 9 11 10 8 5

總結

以上是生活随笔為你收集整理的左神算法：分别用递归和非递归方式实现二叉树先序、中序和后序遍历（Java版）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。