Skip to content

IMPLEMENTATION_DETAILS.md

Latest commit

 

History

History
214 lines (150 loc) · 3.82 KB

IMPLEMENTATION_DETAILS.md

File metadata and controls

214 lines (150 loc) · 3.82 KB

二叉树构建和遍历实现细节

1. 节点结构

二叉树的每个节点最多有两个孩子：

struct Node {
    int value;
    Node* left;
    Node* right;
};
  • value：节点值。
  • left：左孩子。
  • right：右孩子。

当前实现使用裸指针管理节点，由 BinaryTree 析构时统一释放整棵树。

2. 层序数组构建二叉树

层序构建使用 std::optional<int> 表示空节点。

例如：

BinaryTree tree({
    1,
    2,
    3,
    4,
    5,
    std::nullopt,
    6,
});

表示：

        1
      /   \
     2     3
    / \     \
   4   5     6

构建过程：

  1. 第一个元素作为根节点。
  2. 使用队列保存等待挂孩子的节点。
  3. 每次弹出一个节点。
  4. 从数组中读取它的左孩子和右孩子。
  5. 非空孩子创建节点并入队。

这种方式和层序遍历天然对应。

3. 前序 + 中序构建二叉树

前序遍历顺序：

根 -> 左 -> 右

中序遍历顺序：

左 -> 根 -> 右

所以前序数组的第一个元素一定是当前子树的根。

例如：

preorder = 1 2 4 5 3 6
inorder  = 4 2 5 1 3 6

前序第一个元素 1 是根。

在中序中找到 1：

4 2 5 | 1 | 3 6

左边 4 2 5 是左子树，右边 3 6 是右子树。

左子树大小是 3，因此前序也可以切分：

1 | 2 4 5 | 3 6

递归处理左右子树即可。

4. 前序遍历

顺序：

根 -> 左 -> 右

代码逻辑：

out.push_back(node->value);
preorder(node->left, out);
preorder(node->right, out);

前序适合复制树、序列化树结构、表达父节点先于子节点的场景。

5. 中序遍历

顺序：

左 -> 根 -> 右

代码逻辑：

inorder(node->left, out);
out.push_back(node->value);
inorder(node->right, out);

对于二叉搜索树，中序遍历结果是有序数组。

6. 后序遍历

顺序：

左 -> 右 -> 根

代码逻辑：

postorder(node->left, out);
postorder(node->right, out);
out.push_back(node->value);

后序适合释放树、计算子树信息等“先处理孩子，再处理父节点”的场景。

当前实现释放节点 destroy 也使用后序思想：

destroy(node->left);
destroy(node->right);
delete node;

7. 层序遍历

层序遍历使用队列：

  1. 根节点入队。
  2. 队列不为空时，弹出队首节点。
  3. 访问当前节点。
  4. 左孩子非空则入队。
  5. 右孩子非空则入队。

层序遍历顺序是从上到下、从左到右。

8. 边界情况

实现和测试重点覆盖：

  • 空树。
  • 层序数组为空。
  • 层序数组第一个元素为空。
  • 只有一个节点。
  • 有空孩子的非完全二叉树。
  • 前序和中序长度不一致。
  • 前序和中序内容不匹配。
  • 构建后执行四种遍历。
  • 调用 clear() 后再次遍历。

9. 复杂度

设节点数为 n。

操作 时间复杂度 空间复杂度
层序建树 O(n) O(n)
前序 + 中序建树 O(n^2) O(h)
前序遍历 O(n) O(h)
中序遍历 O(n) O(h)
后序遍历 O(n) O(h)
层序遍历 O(n) O(n)

其中 h 是树高。

当前前序 + 中序建树为了代码直观，每次在中序区间里线性查找根节点，因此最坏是 O(n^2)。如果要优化，可以提前建立 value -> index 哈希表，把建树优化到 O(n)。

10. 面试讲解顺序

推荐这样讲：

  1. 先说明节点结构：值、左孩子、右孩子。
  2. 讲四种遍历顺序：前中后层。
  3. 讲递归遍历的终止条件：节点为空直接返回。
  4. 讲层序遍历为什么用队列。
  5. 讲前序 + 中序建树：前序定根，中序切左右子树。
  6. 最后补充内存释放使用后序思想。