二叉樹的先序周遊、中序周遊、後序周遊：遞歸 & 循環 兩種實作

一、預備知識

首先你得了解 樹 的基本概念，二叉樹是每個結點至多隻有兩個子結點的樹，常稱之為左右結點。

二叉樹的周遊方式有 先序周遊(preorder traeversal)、中序周遊(inorder traversal)、後序周遊(postorder traversal) 三種，假設結點為 N，左子結點為 L，右子結點為 R。則：

• 先序周遊：NLR（N 在最前面）
• 中序周遊：LNR（N 在中間）
• 後序周遊：LRN（N 在最後面）

二、二叉樹舉例

針對以上這個二叉樹，3 種周遊結果為：

先序周遊：0 1 3 7 8 4 9 2 5 6

中序周遊：7 3 8 1 9 4 0 5 2 6

後序周遊：7 8 3 9 4 1 5 6 2 0

三、遞歸實作方式

使用遞歸是很容易實作二叉樹的周遊的。以下是代碼示例：

public class Main {

    public static void main(String[] args) {
        TreeNode root = getTestTree(); // 初始化一個二叉樹
        preorderTraversal(root); // 先序周遊
        System.out.println();
        inorderTraversal(root); // 中序周遊
        System.out.println();
        postorderTraversal(root); // 後序周遊
    }

    public static void preorderTraversal(TreeNode root) {
        if (root == null) return;
        System.out.print(root.getData() + " ");
        preorderTraversal(root.getLeft());
        preorderTraversal(root.getRight());
    }

    public static void inorderTraversal(TreeNode root) {
        if (root == null) return;
        inorderTraversal(root.getLeft());
        System.out.print(root.getData() + " ");
        inorderTraversal(root.getRight());
    }

    public static void postorderTraversal(TreeNode root) {
        if (root == null) return;
        postorderTraversal(root.getLeft());
        postorderTraversal(root.getRight());
        System.out.print(root.getData() + " ");
    }

    public static TreeNode getTestTree() {
        TreeNode[] nodes = new TreeNode[10];
        for (int i = 0; i < nodes.length; i++) {
            nodes[i] = new TreeNode(i);
        }
        nodes[0].setLeft(nodes[1]);
        nodes[0].setRight(nodes[2]);
        nodes[1].setLeft(nodes[3]);
        nodes[1].setRight(nodes[4]);
        nodes[2].setLeft(nodes[5]);
        nodes[2].setRight(nodes[6]);
        nodes[3].setLeft(nodes[7]);
        nodes[3].setRight(nodes[8]);
        nodes[4].setLeft(nodes[9]);
        return nodes[0];
    }
}
           

當然，還有一個很簡單的 TreeNode 類，如下：

public class TreeNode {
    
    private int data;
    private TreeNode left;
    private TreeNode right;
    
    public TreeNode(int data) {
        this.data = data;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public TreeNode getLeft() {
        return left;
    }

    public void setLeft(TreeNode left) {
        this.left = left;
    }

    public TreeNode getRight() {
        return right;
    }

    public void setRight(TreeNode right) {
        this.right = right;
    }
    
}
           

執行結果：

0 1 3 7 8 4 9 2 5 6 
7 3 8 1 9 4 0 5 2 6 
7 8 3 9 4 1 5 6 2 0 
           

四、循環實作方式

不使用遞歸，而使用循環的方式變量二叉樹，這是一個比較常見的面試題，實作起來也不會太難。

我們需要用到一個 棧 來幫助我們存儲一些結點資訊。以下是代碼示例：

import java.util.Stack;
 
public class Main {
 
    public static void main(String[] args) {
        TreeNode root = getTestTree(); // 初始化一個二叉樹
        preorderTraversal(root); // 先序周遊
        System.out.println();
        inorderTraversal(root); // 中序周遊
        System.out.println();
        postorderTraversal(root); // 後序周遊
    }
     
    public static void preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        while (current != null || !stack.isEmpty()) {
            if (current != null) {
                System.out.print(current.getData() + " ");
                stack.push(current);
                current = current.getLeft();
            } else {
                current = stack.pop().getRight();
            }
        }
    }
     
    public static void inorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        while (current != null || !stack.isEmpty()) {
            if (current != null) {
                stack.push(current);
                current = current.getLeft();
            } else {
                current = stack.pop();
                System.out.print(current.getData() + " ");
                current = current.getRight();
            }
        }
    }
     
    public static void postorderTraversal(TreeNode root) {
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        stack.push(current);
        stack.push(current); // 每個結點 push 兩次，這樣可以簡單的判斷出哪些結點是否處理過
        while (!stack.isEmpty()) {
            current = stack.pop();
            if (!stack.isEmpty() && current == stack.peek()) {
                if (current.getRight() != null) {
                    stack.push(current.getRight());
                    stack.push(current.getRight());
                }
                if (current.getLeft() != null) {
                    stack.push(current.getLeft());
                    stack.push(current.getLeft());
                }
            } else {
                System.out.print(current.getData() + " ");
            }
        }
    }
     
    public static TreeNode getTestTree() {
        TreeNode[] nodes = new TreeNode[10];
        for (int i = 0; i < nodes.length; i++) {
            nodes[i] = new TreeNode(i);
        }
        nodes[0].setLeft(nodes[1]);
        nodes[0].setRight(nodes[2]);
        nodes[1].setLeft(nodes[3]);
        nodes[1].setRight(nodes[4]);
        nodes[2].setLeft(nodes[5]);
        nodes[2].setRight(nodes[6]);
        nodes[3].setLeft(nodes[7]);
        nodes[3].setRight(nodes[8]);
        nodes[4].setLeft(nodes[9]);
        return nodes[0];
    }
}
           

TreeNode 類同上，不再重複貼出，執行結果：

0 1 3 7 8 4 9 2 5 6 
7 3 8 1 9 4 0 5 2 6 
7 8 3 9 4 1 5 6 2 0 
           

​