树的基础概念与性质

• 2026年 8月 29日
• OI,
• 编程

树

定义

• 由 n (n >= 0) 个结点组成的有限集合。
• n = 0：空树。
• n > 0：存在一个根结点（唯一），根只有直接后继，没有直接前驱。其余结点划分成 m (m >= 0) 个互不相交的有限集合 T0, T1, …, Tm-1，每个集合都是一棵树，称为根的子树。

本质是递归——一棵树 = 一个根 + 多棵互不相交的子树。

相关概念

树的 3 条性质

1. 除根结点外，每个结点有且仅有一个父结点。
2. n 个结点的树有且仅有 n - 1 条边。
3. 任意两个结点之间有且仅有一条简单路径（无自环、无重边）。

二叉树

定义

每个结点最多两个子树（子树有左右之分，分别叫左孩子 / 右孩子、左子树 / 右子树）。

4 种遍历

• 先序（前序）：根 → 左 → 右
• 中序：左 → 根 → 右
• 后序：左 → 右 → 根
• 层次：按层从左到右

由先序 + 中序或中序 + 后序可以唯一确定一棵二叉树。先序 + 后序不行。

满二叉树 vs 完全二叉树

• 满二叉树：深度 k，恰好 2^k - 1 个结点（每层都满）。
• 完全二叉树：深度 k，共 n 个结点，并且这 n 个结点位置和深度为 k 的满二叉树中编号 1..n 的结点一一对应。简言之：把一棵满二叉树从右往左、从下往上砍掉若干个结点，剩下的就是完全二叉树。

完全二叉树的特征：叶结点只可能出现在最下面两层。

二叉树的 6 条性质

下面 k = 树深度（根为第 1 层），n = 结点总数，n0 / n1 / n2 = 度为 0 / 1 / 2 的结点数，i = 结点编号。

性质 1

二叉树第 i 层最多 2^(i-1) 个结点（i >= 1）。

证明：归纳。

• 基础：i = 1 时只有根，最多 1 = 2^0 个。
• 归纳：假设第 i - 1 层最多 2^(i-2) 个。又每个结点的度 ≤ 2，所以第 i 层最多 = 第 i - 1 层的 2 倍 = 2 * 2^(i-2) = 2^(i-1)。

性质 2

深度为 k 的二叉树最多 2^k - 1 个结点（k >= 1）。

证明：每层取性质 1 的上界相加：

1 + 2 + 4 + ... + 2^(k-1) = 2^k - 1

性质 3

对任意二叉树，叶结点数 n0 = 度为 2 的结点数 n2 + 1，即 n0 = n2 + 1。

证明：

• 总结点数：n = n0 + n1 + n2 ……（式 1）
• 每个度为 1 的结点贡献 1 个孩子，每个度为 2 的结点贡献 2 个孩子：孩子总数 = n1 + 2 * n2。
• 树中除了根，每个结点都恰好是某个结点的孩子：孩子总数 = n - 1。

于是 n - 1 = n1 + 2 * n2，即

n = n1 + 2 * n2 + 1    ……（式 2）

（式 1）-（式 2）：

n0 + n1 + n2 - (n1 + 2*n2 + 1) = 0
=>  n0 = n2 + 1

性质 4

n 个结点的完全二叉树深度 = floor(log2(n)) + 1。

证明：设深度为 k。按完全二叉树的定义：

• 前 k - 1 层是满的（每层 2^(i-1) 个），所以前 k - 1 层有 2^(k-1) - 1 个结点；第 k 层至少 1 个、最多 2^(k-1) 个。
• 因此 n > 2^(k-1) - 1（前 k-1 层还没装满）。
• 同时 n <= 2^k - 1（深度为 k 的满二叉树）。

联立：2^(k-1) - 1 < n <= 2^k - 1，加上 1 后等价于：

2^(k-1) <= n < 2^k

两边取 log2：k - 1 <= log2(n) < k。

k 是整数，所以 k = floor(log2(n)) + 1。

性质 5

n 个结点的二叉树，深度至少为 log2(n + 1)（即 floor(log2(n)) + 1，由 ceiling(log2(n+1)) = floor(log2(n)) + 1）。

证明：性质 2 的逆命题。

性质 2 给出上界：深度 = k ⇒ n <= 2^k - 1 ⇒ 2^k >= n + 1 ⇒ k >= log2(n + 1)。

深度是整数，所以 深度 >= ceiling(log2(n + 1))，而 ceiling(log2(n + 1)) = floor(log2(n)) + 1。

性质 6

n 个结点的完全二叉树，任一编号为 i 的结点：

1. 父结点：若 i = 1 则为根，无父结点；否则父结点编号为 i / 2（整除）。
2. 左孩子：若 2 * i > n 则无左孩子；否则左孩子编号为 2 * i。
3. 右孩子：若 2 * i + 1 > n 则无右孩子；否则右孩子编号为 2 * i + 1。

证明：完全二叉树的编号规则是"自上而下、从左到右"。

• 同一层：结点 i 和 i + 1 都在同一层。i 的两个孩子占编号 2i、2i+1；i+1 的两个孩子占 2(i+1) = 2i+2、2(i+1)+1 = 2i+3。2i+1 < 2i+2，编号不冲突。i/2（整除）正好是 i 的父——因为 i 的左孩子是 2i、右孩子是 2i+1，它们整除 2 都回到 i。✓
• 跨层：结点 i 是某层最后一个，下一层的第一个孩子是 i + 1（不是 2i+1）。i 的父是 i/2，但 i+1 的父不再是 i+1 / 2，而是同一个父 i/2 的右孩子——因为从这一层跨到下一层时，编号是连续而非翻倍，规则 parent = i / 2 依然成立。✓

速查公式表

• ← 上一篇
  线性 DP 入门
• 下一篇 →
  J1 批改结果归档