编辑“︁二叉树的遍历”︁（章节）

== 深度优先遍历（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>