目录

  1. 深度优先遍历的基本概念
  2. 深度优先遍历的三种方式
  3. 时间复杂度分析
  4. 代码示例（伪代码）
  5. 参考资料

1. 深度优先遍历的基本概念

深度优先遍历（Depth-First Traversal, DFT）是一种树遍历方法，沿着树的深度方向优先探索每个分支，直到到达叶子节点后再回溯。在二分搜索树中，DFT 常用于访问所有节点或执行特定操作（如查找路径、计算高度）。它有三种主要形式：前序、中序和后序遍历。

2. 深度优先遍历的三种方式

BST 的深度优先遍历根据访问根节点的顺序分为以下三种：

  1. 前序遍历（Pre-order）：
  • 访问顺序：根节点 → 左子树 → 右子树。
  • 特点：先处理当前节点，常用于复制树或序列化。
  • 示例（树：5-3-7-1-4）：
    • 输出：5, 3, 1, 4, 7。
  1. 中序遍历（In-order）：
  • 访问顺序：左子树 → 根节点 → 右子树。
  • 特点：对于 BST，结果是升序序列，常用于排序输出。
  • 示例（树：5-3-7-1-4）：
    • 输出：1, 3, 4, 5, 7。
  1. 后序遍历（Post-order）：
  • 访问顺序：左子树 → 右子树 → 根节点。
  • 特点：最后处理当前节点，常用于删除树或计算依赖子节点的操作。
  • 示例（树：5-3-7-1-4）：
    • 输出：1, 4, 3, 7, 5。

示例树

    5
   / \
  3   7
 / \
1   4

3. 时间复杂度分析

  • 时间复杂度：O(n)
  • 无论前序、中序还是后序，每个节点恰好被访问一次，n 为节点数。
  • 空间复杂度：
  • 递归实现：O(h)，h 为树高，平均 O(log n)，最差 O(n)。
  • 迭代实现（使用栈）：O(h)，最差 O(n)。

4. 代码示例（伪代码）

class Node:
    value         // 节点值
    left          // 左子节点
    right         // 右子节点

class BST:
    root          // 根节点

    // 前序遍历（递归）
    function preOrder():
        preOrderRec(root)

    function preOrderRec(node):
        if node is not null:
            print(node.value)
            preOrderRec(node.left)
            preOrderRec(node.right)

    // 中序遍历（递归）
    function inOrder():
        inOrderRec(root)

    function inOrderRec(node):
        if node is not null:
            inOrderRec(node.left)
            print(node.value)
            inOrderRec(node.right)

    // 后序遍历（递归）
    function postOrder():
        postOrderRec(root)

    function postOrderRec(node):
        if node is not null:
            postOrderRec(node.left)
            postOrderRec(node.right)
            print(node.value)

5. 参考资料

如果你需要特定语言的实现代码（如 Python、Java）或对某种遍历方式有进一步疑问，请告诉我！