编辑“︁二叉树的遍历”︁

{{DISPLAYTITLE:二叉树的遍历}}

'''二叉树的遍历'''是指按照某种顺序访问树中的所有节点，且每个节点仅访问一次的过程。遍历是二叉树的基础操作之一，广泛应用于数据检索、表达式求值、文件系统管理等场景。根据访问节点的顺序不同，主要分为'''深度优先遍历'''（DFS）和'''广度优先遍历'''（BFS）两大类。

== 深度优先遍历（DFS） ==
深度优先遍历沿着树的深度遍历节点，尽可能深地搜索树的分支，直到无法继续为止，再回溯到上一层节点。根据访问根节点的时机，分为以下三种方式：

=== 前序遍历（Preorder Traversal） ===
访问顺序：'''根节点 → 左子树 → 右子树'''  
常用于复制树结构或生成前缀表达式（如波兰表达式）。

<syntaxhighlight lang="python">
# Python 前序遍历递归实现
def preorder(root):
    if root:
        print(root.val, end=" ")  # 访问根节点
        preorder(root.left)       # 遍历左子树
        preorder(root.right)      # 遍历右子树

# 示例输入与输出
# 二叉树结构：
#      1
#     / \
#    2   3
#   / \
#  4   5
# 输出：1 2 4 5 3
</syntaxhighlight>

=== 中序遍历（Inorder Traversal） ===
访问顺序：'''左子树 → 根节点 → 右子树'''  
对'''二叉搜索树'''（BST）使用时，会按升序输出节点值。

<syntaxhighlight lang="java">
// Java 中序遍历递归实现
void inorder(TreeNode root) {
    if (root != null) {
        inorder(root.left);       // 遍历左子树
        System.out.print(root.val + " ");  // 访问根节点
        inorder(root.right);      // 遍历右子树
    }
}

// 示例输入与输出（同上二叉树）
// 输出：4 2 5 1 3
</syntaxhighlight>

=== 后序遍历（Postorder Traversal） ===
访问顺序：'''左子树 → 右子树 → 根节点'''  
常用于删除树或生成后缀表达式（如逆波兰表达式）。

<syntaxhighlight lang="cpp">
// C++ 后序遍历递归实现
void postorder(Node* root) {
    if (root) {
        postorder(root->left);    // 遍历左子树
        postorder(root->right);   // 遍历右子树
        cout << root->data << " "; // 访问根节点
    }
}

// 示例输入与输出（同上二叉树）
// 输出：4 5 2 3 1
</syntaxhighlight>

=== 可视化示例 ===
<mermaid>
graph TD
    A((1)) --> B((2))
    A --> C((3))
    B --> D((4))
    B --> E((5))
</mermaid>

== 广度优先遍历（BFS） ==
广度优先遍历按层次从上到下、从左到右访问节点，通常借助'''队列'''实现。

=== 层序遍历（Level Order Traversal） ===
<syntaxhighlight lang="python">
from collections import deque

def level_order(root):
    if not root:
        return
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.val, end=" ")
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

# 示例输入与输出（同上二叉树）
# 输出：1 2 3 4 5
</syntaxhighlight>

== 非递归实现 ==
递归方法可能引发栈溢出，以下是使用'''栈'''的迭代实现：

<syntaxhighlight lang="python">
# Python 前序遍历迭代实现
def preorder_iterative(root):
    stack = [root]
    while stack:
        node = stack.pop()
        if node:
            print(node.val, end=" ")
            stack.append(node.right)  # 右子节点先入栈
            stack.append(node.left)   # 左子节点后入栈
</syntaxhighlight>

== 实际应用案例 ==
1. '''文件系统遍历'''：目录树本质是N叉树，前序遍历可用于统计文件数量。  
2. '''表达式求值'''：中序遍历生成中缀表达式，后序遍历适合计算器实现。  
3. '''DOM树渲染'''：浏览器使用深度优先遍历渲染HTML节点。

== 时间复杂度分析 ==
设树有<math>n</math>个节点：
* 所有遍历方式的时间复杂度均为<math>O(n)</math>  
* 空间复杂度：
  * 递归：<math>O(h)</math>（<math>h</math>为树高，最坏情况<math>O(n)</math>）
  * 迭代：<math>O(n)</math>

== 扩展：Morris遍历 ==
一种空间复杂度为<math>O(1)</math>的遍历算法，通过临时修改树结构实现（适合内存受限场景）。

{{Note|提示|遍历选择建议：  
* 需要父节点信息时选择前序/后序  
* 需要有序数据时选择中序  
* 需要层次信息时选择层序}}

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:非线性数据结构]]