完全二叉树 (Complete Binary Tree)

定义：

• 完全二叉树要求 除了最后一层，其他层的节点必须全部填满，并且最后一层的节点从左到右连续排列。
• 如果一棵树的深度为 h ，则前 h-1 层的节点数为 2 ^h-1 – 1 ，最后一层的节点数为 [1, 2 ^h-1] 。

特点：

• 节点在树中的排列是连续的，不允许空缺。例如，如果某层有缺失的节点，缺失的只能是右侧的节点。
• 用数组表示时（堆的常见实现），如果父节点在索 i 处，则左子节点在 2i+1 ，右子节点在 2i+2 ，父节点在 ⌊(i-1)/2⌋ 。

可视化示例：

       1
      / \
     2   3
    / \  /
   4  5 6

• 节点 7 缺失，但仍满足完全二叉树的性质。
• 节点从左到右依次排列，最后一层从左开始填充。

---

满二叉树 (Full Binary Tree)

定义：

• 满二叉树的特点是每个节点要么有两个子节点，要么没有子节点（即为叶子节点）。
• 并且所有叶子节点都必须在树的同一层。

特点：

• 满二叉树的节点数量为 2 ^h – 1 ，其中 h 是树的高度（深度）。
• 它的每一层都是完全填满的，节点数符合最大值。

可视化示例：

       1
      / \
     2   3
    / \ / \
   4  5 6  7

• 每个非叶子节点都有两个子节点。
• 所有叶子节点（4, 5, 6, 7）都在同一层。

---

二叉搜索树 (Binary Search Tree, BST)

定义：

• 二叉搜索树是一种特殊的二叉树，满足以下性质：

1. 对于任意一个节点，其左子树中所有节点的值 小于当前节点的值。
2. 右子树中所有节点的值 大于当前节点的值。

• 通常用于高效查找和排序，查找、插入、删除的时间复杂度在平均情况下为 O(log n) 。

特点：

• 树的中序遍历结果是一个 升序排列。
• 不要求是满二叉树或完全二叉树。

可视化示例：

       5
      / \
     3   7
    / \  / \
   2  4 6   8

• 节点 3 的左子树节点 2 小于 3，右子树节点 4 大于 3。
• 整棵树中序遍历的结果为：2, 3, 4, 5, 6, 7, 8。

---

对比总结

特性	完全二叉树	满二叉树	二叉搜索树
定义	除了最后一层，其他层节点必须填满，最后一层从左到右连续排列	每个节点有 0 或 2 个子节点，所有叶子节点位于同一层	左子树 < 当前节点 < 右子树
节点排列要求	节点从左到右连续排列	每层节点必须全部填满	无严格要求
层次结构是否一致	只有最后一层不一定满	所有层次都完全填满	不要求一致
高度	和满二叉树一样深，最后一层可能不满	最小高度（节点数量固定时最矮）	不一定，可能较高
主要应用场景	常用于堆结构，队列	完全平衡的场景	查找、排序、动态插入和删除等场景