特殊二叉树：斜树 / 满二叉树 / 完全二叉树

1. 斜树（Skewed Tree）

  • 定义：所有结点都只有左孩子（左斜树）或只有右孩子（右斜树）。
  • 特点：退化为线性结构，树的高度等于结点数。
  • 性能：查找、插入、删除退化为 O(n)O(n)，失去了二叉树的优势。

2. 满二叉树（Full Binary Tree / Perfect Binary Tree）

  • 定义：所有分支结点都有左孩子和右孩子，且所有叶子都在同一层。
  • 性质（高度为 hh，根为第 1 层）：
    • 第 ii 层结点数：2i−12^{i-1}
    • 总结点数：2h−12^h - 1
    • 叶子数：2h−12^{h-1}
  • 特点：形态完美，所有叶子深度相同。

3. 完全二叉树（Complete Binary Tree）

  • 定义：对高度为 hh、有 nn 个结点的二叉树，当且仅当其每个结点都与高度为 hh 的满二叉树中编号 1 到 nn 的结点一一对应时，称为完全二叉树。
  • 通俗理解：除最后一层外，其余层结点数达到最大；最后一层结点向左靠拢。
  • 性质：
    • 叶子结点只可能在最后两层出现。
    • 如果有度为 1 的结点，则只可能有一个，且该结点只有左孩子。
    • 按层序编号后，可方便地用数组存储（下标关系见 [[二叉树的存储]]）。

对比表

类型 形态 叶子位置 适用存储 高度 h 的结点数
满二叉树 完美 同一层 数组 2h−12^h - 1
完全二叉树 缺右边 最后两层 数组 [2h−1,2h−1][2^{h-1}, 2^h - 1]
斜树 一条线 末端 链表 hh

判断方法（完全二叉树）

  • 按层序编号，若出现空位后仍有非空结点，则不是完全二叉树。
  • 更简单的算法：层序遍历，遇到第一个 NULL 后，检查后面是否还有非 NULL 结点。

应用

  • 满二叉树：常用于理论分析。
  • 完全二叉树：堆的底层存储（利用数组高效实现）。