二叉树 | Codeboy's Blog

形式陈述

二叉树是一种递归结构：它可以为空，也可以由一个根节点、一个左子树和一个右子树组成，两棵子树仍是二叉树。若节点保存类型 $A$ 的载荷，可写成

T::=\operatorname{Empty}\mid\operatorname{Node}(a,L,R),\qquad a\in A.

本条目只讨论有限、无共享、无环的二叉树；不同节点可以保存相同载荷。左右是两个有名字的槽位，因此

\operatorname{Node}(a,T,\operatorname{Empty}) \ne\operatorname{Node}(a,\operatorname{Empty},T) \quad(T\ne\operatorname{Empty}).

“每个节点至多有两个孩子”还不够完整：即使只有一个孩子，也必须说明它在左边还是右边。普通有序根树若只有一个孩子，仅给孩子排序并不能记录这一区别。

非空二叉树忽略根和左右槽位后，底层无向图是一棵树。图论中的树在本条目所链接的约定下要求非空；这里允许空树，是为了让左右子树的递归定义统一成立。

根的深度为 $0$ ，节点深度为从根到它经过的边数。非空树的高度 $h$ 是最大深度；为使递推 $h(T)=1+\max\{h(L),h(R)\}$ 对叶子也成立，本条目约定 $h(\operatorname{Empty})=-1$ 。

直觉

二叉树把一个问题拆成“当前节点、左边的问题、右边的问题”。表达式 $(a+b)\times c$ 可以让乘法成为根、左子树表示 $a+b$ 、右子树表示 $c$ 。结构本身记录运算的嵌套，不再需要依靠书写括号猜测先后。

左右子树都为空的节点称为叶子。对二叉树做递归时，空树提供终止条件，非空树提供分解步骤。节点数就可以写成

n(\operatorname{Empty})=0,\qquad n(\operatorname{Node}(a,L,R))=1+n(L)+n(R).

这里分开的左右子树没有共享节点，否则将两边计数相加可能重复计算；带共享的 DAG 应使用另一套定义和遍历约定。结构归纳也沿着同一个分解工作：先证明空树满足性质，再假定左右子树分别满足性质，证明加上一个根后仍成立。有限性保证这种向更小子树的递归最终会遇到空树，不能把同样的终止论证直接搬到带环指针结构上。

二叉树只规定形状，并不规定载荷之间的大小。二叉搜索树另加键的有序性，二叉堆另加堆序和形状限制。不能因为画出了二叉树，就直接获得对数查找时间。

例子与边界

三种容易混淆的形状

中文“满二叉树”的用法并不完全统一，因此这里同时给出英文术语与精确定义。

术语	本条目采用的条件	条件关注什么
full / proper（二分支树）	每个非叶节点恰有两个非空子树	不允许只有一个孩子
perfect（完美二叉树）	每个非叶节点有两个孩子，且全部叶子同深度	每层都填满
complete（完全二叉树）	除最底层外各层填满，最底层从左到右连续填入	按层存储时没有空洞

完美树同时满足另外两种条件，但反向不成立。根有左叶子和右内部节点、右内部节点再有两个叶子的五节点树是 full，却不是 complete；一个根只有左孩子的两节点树是 complete，却不是 full。平衡则讨论子树高度或其他规模差异，需要另行给出具体约束。

高度与节点数

第 $d$ 层至多有 $2^d$ 个节点，因此非空树满足

n\le1+2+\cdots+2^h=2^{h+1}-1, \qquad \lceil\log_2(n+1)\rceil-1\le h\le n-1.

左端对应尽量把层填满；右端由一条单分支链达到。因此“二叉”只限制分支数，并不阻止树退化成线性高度。沿根到叶的搜索通常花费 $O(h+1)$ 时间，是否为 $O(\log n)$ 还要看形状保证。

设 $n_0,n_1,n_2$ 分别为有 $0,1,2$ 个非空孩子的节点数。非空树每个非根节点恰好被一条父边指向，故

n-1=n_1+2n_2, \qquad n=n_0+n_1+n_2,

相减得到 $n_0=n_2+1$ 。这个等式允许存在单孩子节点，并不限于 full 树。另从 $2n$ 个左右槽位中减去 $n-1$ 条真实父子边，可知空槽位恰有 $n+1$ 个。

遍历序列不一定保存完整结构

前序、中序、后序分别按“根—左—右”“左—根—右”“左—右—根”访问非空节点。对 $(a+b)\times c$ 的表达式树，前序为 * + a b c，后序为 a b + c *；后序适合先算子表达式再执行运算。

只有前序载荷序列一般不能恢复树。根为 a、唯一孩子为 b 的两棵树，无论 b 在左还是右，前序都为 a b。若连空槽位也用 # 记录，则两者分别为 a b # # # 与 a # b # #，结构就被区分开。

这个带空标记的编码还有直接的合法性检查。开始有一个待填的根槽位；读到 # 消耗一个槽位，读到载荷则消耗一个槽位并产生左右两个槽位，净增一个。每次读取前必须还有槽位，且输入结束时恰好归零。例如 a b # # # 的剩余槽位依次为 $2,3,2,1,0$ 。提前归零后还有输入，表示后面多了一棵树；结束时仍为正，表示遗漏了子树。真正重建时再用栈保存这些槽位所属的父节点与左右方向。

节点标签互异时，前序加中序可以唯一重建：前序首项给出根，中序中的根把左右节点集合分开，再递归处理。标签重复时，这个分割未必唯一。只为普通根树记录进入与退出的括号，也可能漏掉单孩子所在的左右槽位；二叉树编码必须保留相应空位信息。

推论与应用

形状决定适合的表示

完全二叉树可以紧密存入数组。使用从 $0$ 开始的下标时，节点 $i$ 的左右孩子下标分别为 $2i+1$ 、 $2i+2$ ，超出数组长度的下标表示不存在。这个布局利用的是 complete 条件；对高度很大的稀疏树，照搬同一位置编码可能留下大量空洞。显式左右指针则适用于任意形状，但要承担指针和节点分配成本。

递归遍历通常用调用栈保存尚未完成的分支，额外空间为 $O(h+1)$ ；对退化树可能达到 $O(n)$ 。使用显式栈改变的是实现形式，不会自动改变最坏树高。

递归结构还能用于计数

忽略节点载荷，设 $C_n$ 为有 $n$ 个节点的二叉树形状数。空树给出 $C_0=1$ ；对非空树，根占去一个节点，左子树可以有 $i$ 个节点，右边便有 $n-1-i$ 个，因此

C_n=\sum_{i=0}^{n-1}C_iC_{n-1-i}.

例如 $C_1=1,C_2=2,C_3=5$ 。乘法来自左右形状的独立选择，求和来自左侧规模的不同可能。这正是 Catalan 数递推；它计数的是具有左右空位约定的树形，不是任意带标签树的数量。

参考资料

Thomas H. Cormen 等，Introduction to Algorithms，第 4 版，MIT Press，2022，附录 B 与第 10、12 章：树的基本约定、表示及二叉搜索树。
Robert Sedgewick、Kevin Wayne，Algorithms，第 4 版，Addison-Wesley，2011，§3.2 Binary Search Trees：用递归二叉结构组织查找，及树形对成本的影响。
Donald E. Knuth，The Art of Computer Programming, Vol. 1，第 3 版，Addison-Wesley，1997，§2.3：二叉树、遍历、表示与计数。

形式陈述 ​

三种容易混淆的形状 ​

高度与节点数 ​

遍历序列不一定保存完整结构 ​

形状决定适合的表示 ​