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

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

什麼是樹的遍歷？

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

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

如何定義一個(gè)二叉樹節(jié)點(diǎn)？

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

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

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

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

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

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

前序遍歷示例：

 void preOrder(TreeNode root) {
    if (root == null) return;
    System.out.print(root.val " "); // 訪問根節(jié)點(diǎn)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 " ");
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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