Java樹的前序遍歷方法是什么

# Java樹的前序遍歷方法是什么

樹的前序遍歷（Preorder Traversal）是二叉樹遍歷的一種常見方式，其訪問順序遵循**根節點→左子樹→右子樹**的規則。在Java中，可以通過遞歸和迭代兩種方式實現前序遍歷。本文將詳細介紹這兩種方法的實現代碼及其原理。

---

## 一、前序遍歷的定義
前序遍歷的訪問順序為：
1. 訪問當前節點（根節點）
2. 遞歸遍歷左子樹
3. 遞歸遍歷右子樹

例如，對于以下二叉樹：

  A
 / \
B   C

/ \
D E F

前序遍歷結果為：`A → B → D → E → C → F`。

---

## 二、遞歸實現
遞歸是描述樹遍歷最直觀的方式，代碼簡潔但可能存在棧溢出風險。

```java
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

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

時間復雜度

• O(n)，每個節點被訪問一次。

三、迭代實現（使用棧）

通過顯式棧模擬遞歸過程，避免遞歸的棧開銷。

import java.util.Stack;

public void preorderTraversalIterative(TreeNode root) {
    if (root == null) return;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        System.out.print(node.val + " "); // 訪問節點
        
        // 右子節點先入棧（保證左子節點先出棧）
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
}

關鍵點

1. 棧的后進先出特性確保左子樹優先處理。
2. 右子節點先入棧，左子節點后入棧。

四、應用場景

前序遍歷常用于： 1. 樹的復制：先復制根節點再處理子樹。 2. 表達式樹求值：前綴表達式（如 + A B）即前序遍歷結果。 3. 目錄結構打印：先打印當前目錄再遍歷子目錄。

五、總結

根據實際需求選擇合適的方法，遞歸適合小規模數據，迭代更適合深度未知的樹結構。 “`

這篇文章以Markdown格式編寫，涵蓋了前序遍歷的定義、遞歸與迭代實現代碼、時間復雜度分析以及應用場景，并通過表格對比了兩種方法的優缺點。