二叉树

二叉树 (Binary Tree)

二叉树（Binary Tree）是一种基础且应用广泛的层次化数据结构，由节点（node）通过父子关系链接而成。每个节点至多拥有两个子节点，分别称为左子节点（left child）和右子节点（right child），左右次序严格区分、不可互换。二叉树是树结构中最核心的特例，为二叉搜索树、堆、哈夫曼树、平衡二叉树等众多衍生结构提供理论基础。其简洁的定义蕴含丰富的组合性质和算法潜力，在计算机科学的搜索、排序、表达式解析、数据压缩、网络路由、数据库索引以及计算几何等领域均扮演关键角色。

基本定义与术语

一棵非空二叉树由一个根节点（root）及其左右两棵互不相交的子树递归构成，子树本身也是二叉树。若某子树不存在，则称对应位置为空子树。相关术语体系包括：父节点（parent）与子节点（child）描述直接上下级关系；兄弟节点（sibling）共享同一父节点；叶节点（leaf）指无子节点的终端节点；内部节点（internal node）至少拥有一个子节点；节点的度（degree）为其子节点数目，二叉树中取值为 0、1 或 2；深度（depth）是从根到该节点的路径边数，根的深度为 0；高度（height）是从该节点到最深叶节点的路径边数，叶节点高度为 0；整棵树的高度等于根节点的高度。此外，祖先（ancestor）与后代（descendant）分别描述沿路径向上和向下的包含关系。

数学性质

二叉树具有一系列精确的数学性质，这些性质是分析算法复杂度的重要依据。第 $k$ 层（$k \geq 1$）最多包含 $2^{k-1}$ 个节点，当且仅当每一层均满时取等。高度为 $h$（根高度为 $h$，即拥有 $h+1$ 层）的二叉树最多拥有 $2^{h+1} - 1$ 个节点，此时称为完美二叉树（perfect binary tree）。对任意非空二叉树，若叶节点数为 $n_0$、度为 1 的节点数为 $n_1$、度为 2 的节点数为 $n_2$，总节点数 $n = n_0 + n_1 + n_2$，且满足 $n_0 = n_2 + 1$。该等式可通过对边数（$n-1$）与出度之和（$n_1 + 2n_2$）建立等量关系推导得出。具有 $n$ 个节点的二叉树，其高度最小为 $\lfloor \log_2 n \rfloor$（完全二叉树），最大为 $n-1$（退化为链表），这一差距决定了平衡性的至关重要。

遍历策略

二叉树的遍历是访问所有节点且每个节点仅访问一次的系统性方法，按照访问根节点相对于左右子树的顺序分为深度优先和广度优先两大类别。

深度优先遍历包含三种经典次序：前序遍历（preorder traversal）遵循「根→左子树→右子树」的递归顺序，适用于复制树结构或生成前缀表达式；中序遍历（inorder traversal）遵循「左子树→根→右子树」的顺序，在二叉搜索树上得到节点的升序排列，这也是其名称的由来；后序遍历（postorder traversal）遵循「左子树→右子树→根」的顺序，常用于先处理子节点再汇总的场景，如计算目录大小或释放树内存。三种遍历均可通过递归或显式栈实现，时间复杂度均为 $O(n)$，空间复杂度在最坏情况下为 $O(n)$（退化为链）、最优为 $O(\log n)$（平衡树）。

广度优先遍历即层序遍历（level-order traversal），借助队列自顶向下、自左向右逐层访问，时间复杂度同样为 $O(n)$。在表达式树中，前序、中序、后序遍历分别对应前缀表达式（波兰表示法）、中缀表达式和后缀表达式（逆波兰表示法），后者在编译器设计和计算器实现中具有直接应用。

特殊二叉树类型

根据结构约束和应用场景，二叉树衍生出多种重要变体。满二叉树（full binary tree）要求每个节点的度非 0 即 2，即不存在度为 1 的节点。完全二叉树（complete binary tree）要求除最后一层外所有层均满，且最后一层节点严格向左对齐，该结构保证数组顺序存储时无空隙，是二叉堆的实现基础。完美二叉树（perfect binary tree）所有内部节点度均为 2 且所有叶节点位于同一层，是最理想也最稀有的形态。

二叉搜索树（Binary Search Tree, BST）施加了序约束：对于任意节点，左子树中所有键值小于该节点，右子树中所有键值大于该节点。该性质使查找、插入和删除的平均时间复杂度为 $O(\log n)$，但最坏情况（插入序列已有序）退化为 $O(n)$。为解决退化问题，平衡二叉搜索树通过额外约束保证树高维持在 $O(\log n)$ 水平：AVL树要求任意节点左右子树高度差不超过 1，通过单旋或双旋操作恢复平衡；红黑树采用颜色标记和更宽松的平衡条件，插入删除的常数因子优于 AVL 树，广泛应用于标准库（如 C++ STL 的 \texttt{std::map} 和 Java 的 \texttt{TreeMap}）。

存储结构与经典应用

二叉树的物理存储分为链式存储和顺序存储两种。链式存储中每个节点包含数据域、左指针和右指针，额外可增设父节点指针以支持向上回溯。顺序存储将完全二叉树的节点按层序编号后直接存入数组：编号 $i$ 的节点，其左子节点位于 $2i+1$、右子节点位于 $2i+2$（或依 1-based 习惯为 $2i$ 与 $2i+1$），父节点位于 $\lfloor (i-1)/2 \rfloor$。顺序存储节省指针空间但对非完全二叉树浪费严重，链式存储灵活通用但指针带来额外开销。

在算法与应用层面，二叉树的派生结构覆盖了计算机科学的核心场景：哈夫曼树利用贪心策略构建带权路径长度最小的最优二叉树，实现无损数据压缩；二叉堆以完全二叉树为基础，支持 $O(\log n)$ 的插入和删除最值操作，是堆排序和优先队列的底层结构；决策树将特征空间递归二分，广泛用于机器学习的分类与回归任务；语法树（parse tree）和抽象语法树（AST）在编译器前端表示程序的语法结构，是词法分析和语法分析的核心数据结构。此外，线段树与树状数组（Fenwick Tree）以二叉树的分治思想高效支持区间查询与更新；并查集的路径压缩和按秩合并也蕴含树形结构的平衡哲学。二叉树的设计精髓——将线性搜索逐层转化为对数级的二分决策——深刻影响了算法设计的方法论，是以简单结构承载复杂计算的典范。