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格式编写，涵盖了前序遍历的定义、递归与迭代实现代码、时间复杂度分析以及应用场景，并通过表格对比了两种方法的优缺点。