选数据结构的四个考虑#

1
① 要存什么
2
② 操作成本（尤其想压低「最坏」操作成本）
3
   例：频繁查找就把集合按有序形式存成数组，以便二分
4
③ 内存消耗
5
④ 易于实现（这一条未必是最佳取舍标准）

定义与应用#

定义：一组称为节点的实体相互连接，模拟层级关系。

最顶端节点 = 根。节点含数据（任意类型）+ 指向其他节点的链接/引用。

应用举例：公司组织层级（John CEO → 直接下属 Steve、Rama；Steve 管 Bob、Ella……）。

树要倒过来看才像树，根在顶部向下分支。

节点编号 1~10 只是为了方便指代，不表示任何顺序，根节点叫成 10 号节点也一样。

术语#

1
根节点          最顶端节点，唯一没有父节点
2
子节点/父节点    直接链接关系
3
兄弟节点        有同一个父节点
4
叶节点          没有子节点
5
内部节点        至少有一个子节点
6
祖父/孙子       父的父 / 子的子
7
祖先/后代       能沿链路从 A 走到 B，则 A 是祖先、B 是后代
8
堂兄弟姐妹（表亲）没有相同父节点但有相同祖父节点
9
叔伯            父的兄弟

链路是单向的：有 1→2 的链路，能从 1 到 2，不能从 2 回 1；遍历时只能沿一个方向走。

递归性质与边数#

树是递归的数据结构：一个特殊节点（根）+ 若干子树，根包含指向所有子树根的链接。

N 个节点的树恰好有 N−1 条边。理由：除根外每个节点恰好有一条入边。

深度 vs 高度#

树的高度 = 根节点的高度。

高度和深度是两个不同属性，一个节点的两者可能相同也可能不同，这里很容易混。

树的应用#

1
① 存储天然分层数据（文件系统的文件/文件夹层次）
2
② 整理数据以便快速搜索/插入/删除 —— 二叉查找树，搜索时间复杂度约为对数级
3
③ Trie 存词典，速度极快、效率高，用于动态拼写检查
4
④ 网络路由算法

基本约定#

• 每节点最多 2 个子节点
• 一个节点可能：有两个 / 只有左 / 只有右 / 都没有
• 只有一个子节点时，另一个引用/指针设为 NULL
• 叶节点：左、右引用均为空

二叉树的三种类型#

单节点树也算二叉树；唯一条件就是不能超过两个子节点。

层与每层最大节点数#

相同深度的节点处于同一层；根深度 0 → 第 0 层（L0），往下 L1、L2…

第 I 层最多 2^I 个节点。推导：某层有 X 个节点，则下一层最多 2X 个。

1
L0: 2^0 = 1
2
L1: 2^1 = 2
3
L2: 2^2 = 4
4
L3: 2×4 = 8

高度公式#

完美二叉树高度 H（层数 H+1）的节点总数：

1
N = 2^0 + 2^1 + … + 2^H = 2^(H+1) − 1

例：层数 4（L0~L3）→ 最大节点数 = 2^4 − 1 = 15。

反解：

1
N = 2^(H+1) − 1
2
→ H = log₂(N+1) − 1
3

4
例：N = 15 → H = log₂16 − 1 = 4 − 1 = 3

完全二叉树高度：

1
H = ⌊log₂ N⌋
2

3
例：N = 15 → log₂15 ≈ 3.906891 → 取整数部分 = 3

N 个节点的最小高度 = ⌊log₂ N⌋（完全/完美二叉树时达到）。

N 个节点的最大高度 = N − 1（树稀疏到近似链表时）。

为什么树的高度重要#

树上的操作开销取决于树的高度：BST 的查找/插入/删除与高度成正比。

1
时间复杂度写成 O(h)
2

3
完全/完美二叉树：h = log₂N  →  O(log N)（几乎是可能达到的最佳运行时间）
4
最坏（链表状）：  h = N−1    →  O(N)

直观对比：即便 N 高达 2^100，log₂N 也只是 100；而 O(N) 时若 N = 2^100，即使使用有史以来最强大的机器，几年都无法完成计算。

所以通常要使二叉树高度尽可能小，也就是保持二叉树「平衡」。

平衡二叉树#

定义：对每个节点，其左右子树高度差不超过某个数 K；大多数情况下 K = 1。

差值计算：|h_left − h_right|。

计算中子树为空时，其高度取 −1。

1
叶节点的左右子树均为空 → h_left = h_right = −1 → 差值为 0
2
满二叉树所有节点 DIF 都为 0
3
删掉一些节点后最大 DIF = 1，仍平衡
4
再删后某节点 DIF = 2（左子树高 1、右子树为空高 −1，|1−(−1)| = 2）→ 不再平衡

目的：保持紧凑、高度最小 → 依赖高度的操作成本最低。

高度的两种定义#

这里采用的定义：

1
高度 = 从根到叶的最长路径中的边数
2

3
由此：只有一个节点的树高度 = 0
4
      空树高度 = −1

另一种定义（不采用）是把最长路径上的节点数量当高度。

1
那样：最长路径 3 条边 → 高度会是 4
2
      单节点树高度 = 1
3
      空树高度 = 0

那种定义看起来非常直观，很多地方都这么写，但这里一律用「边数」定义，所以空树高度是 −1。

二叉树的两种内存存储方式#

1
指针/引用链接动态创建的节点 —— 最常见，节点随机分布在堆里
2
数组 —— 通常用于完全二叉树（后面堆也用它）

数组的编号方式：从根开始、自左向右按层编号，从 0 开始（0, 1, 2, 3, 4, 5, 6）。

1
索引为 I 的节点：
2
  左子节点索引 = 2I + 1
3
  右子节点索引 = 2I + 2

例：I = 0 → 左 1、右 2；I = 1 → 左 3、右 4；I = 2 → 左 5、右 6。

这个公式仅对完全二叉树成立。

这是 0-based 的公式。有些教材用 1-based（左 2i、右 2i+1），这里用 0-based。