樹的遍歷是指按照特定順序訪問樹中每個節(jié)點一次且僅一次。 1. 前序遍歷先訪問根節(jié)點再遍歷左右子樹；2. 中序遍歷先遍歷左子樹再訪問根節(jié)點後遍歷右子樹；3. 後序遍歷先遍歷左右子樹最後訪問根節(jié)點。在Java 中可通過遞歸或棧實現(xiàn)，其中遞歸方式邏輯清晰，而非遞歸實現(xiàn)需用棧模擬調(diào)用過程以避免棧溢出。應(yīng)用場景方面，前序用於復(fù)製或序列化樹，中序適用於二叉搜索樹的有序輸出，後序用於刪除樹或表達式求值。

在Java 中實現(xiàn)樹的遍歷（前序、中序、後序）是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)內(nèi)容之一。這三種遍歷方式都屬於深度優(yōu)先遍歷，它們的核心區(qū)別在於訪問根節(jié)點的時機不同。

什麼是樹的遍歷？

樹的遍歷指的是按照某種順序訪問樹中的每一個節(jié)點，確保每個節(jié)點都被訪問一次且僅一次。對於二叉樹來說，最常見的三種遍歷方式是：

• 前序遍歷（Pre-order） ：先訪問根節(jié)點，再遞歸地前序訪問左子樹，最後前序訪問右子樹。
• 中序遍歷（In-order） ：先遞歸地中序訪問左子樹，再訪問根節(jié)點，最後中序訪問右子樹。
• 後序遍歷（Post-order） ：先遞歸地後序訪問左子樹，再後序訪問右子樹，最後訪問根節(jié)點。

如何定義一個二叉樹節(jié)點？

在Java 中，我們通常會先定義一個表示二叉樹節(jié)點的類：

 class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

這個類非?；A(chǔ)，但足以支持後續(xù)的遍歷操作。

前序、中序、後序遍歷的遞歸寫法

遞歸是最直觀也最容易理解的方式。下面是每種遍歷方式的基本實現(xiàn)：

前序遍歷示例：

 void preOrder(TreeNode root) {
    if (root == null) return;
    System.out.print(root.val " "); // 訪問根節(jié)點preOrder(root.left); // 遍歷左子樹preOrder(root.right); // 遍歷右子樹}

中序遍歷示例：

 void inOrder(TreeNode root) {
    if (root == null) return;
    inOrder(root.left);
    System.out.print(root.val " ");
    inOrder(root.right);
}

後序遍歷示例：

 void postOrder(TreeNode root) {
    if (root == null) return;
    postOrder(root.left);
    postOrder(root.right);
    System.out.print(root.val " ");
}

這些方法邏輯清晰，代碼簡潔，適合初學(xué)者理解和使用。

非遞歸實現(xiàn)需要注意什麼？

雖然遞歸實現(xiàn)簡單，但在實際開發(fā)中有時需要避免使用遞歸，比如當棧深度過大時可能導(dǎo)致棧溢出。這時可以使用棧（Stack）來模擬遞歸過程。

以中序遍歷為例，非遞歸實現(xiàn)如下：

 void inOrderIterative(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode current = root;

    while (current != null || !stack.isEmpty()) {
        // 先把所有左節(jié)點壓入棧while (current != null) {
            stack.push(current);
            current = current.left;
        }

        current = stack.pop();
        System.out.print(current.val " ");
        current = current.right;
    }
}

這種方式的關(guān)鍵點在於：

• 使用while循環(huán)替代遞歸調(diào)用；
• 明確區(qū)分“訪問節(jié)點”和“處理節(jié)點”的時機；
• 注意空指針的判斷，防止運行時錯誤。

其他兩種遍歷也可以類似實現(xiàn)，但邏輯略複雜一些。

應(yīng)用場景有什麼不同？

這三種遍歷方式雖然結(jié)構(gòu)相似，但應(yīng)用場景略有不同：

• 前序遍歷：常用於復(fù)制樹結(jié)構(gòu)或序列化樹；
• 中序遍歷：如果是二叉搜索樹（BST），中序遍歷會輸出一個有序序列；
• 後序遍歷：適用於刪除整棵樹或表達式求值等場景。

比如，如果你有一個BST，想要按升序打印所有元素，那中序遍歷就是最合適的。

基本上就這些了。掌握這幾種遍歷方式，不僅對理解樹結(jié)構(gòu)有幫助，也是很多算法題目的基礎(chǔ)。

以上是java中的樹（按處階，預(yù)訂，後訂單）的詳細內(nèi)容。更多資訊請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！