二叉树

二叉树是“二路递归分解”的形状：每个节点代表一次一分为二的决策或一个二元运算，整棵树是分解过程的完整记录。左右有别不是形式主义，两个方向通常承载不对称的语义——小与大、then 与 else、比特 $0$ 与 $1$；抹掉左右之分就丢掉了这层信息。结构的平衡程度决定递归的深度：同样 $n$ 个节点，均衡分裂给出对数高度，偏向一侧则退化为线性，搜索、堆与分治的效率差异几乎都能追溯到这一形状参数。空树作为合法基例并非多余：它让递归定义与递归算法的边界情形统一而简洁。

表达式 $(a+b)\cdot c$ 的语法树以 $\cdot$ 为根，左子树是以 $+$ 为根、叶为 $a,b$ 的子树，右子树是叶 $c$；后序遍历输出 $ab+c\cdot$，恰为逆波兰记法，中序遍历配合括号还原中缀式。计数方面，$3$ 个节点的二叉树形状恰有 $5$ 种（四种链形加一种平衡形），一般地 $n$ 个节点的形状数是 Catalan 数公理库Catalan 数Catalan number计数正确括号串、凸多边形三角剖分等结构的一族整数。 $C_n=(\genfrac{}{}{0ex}{}{2n}{n})/(n+1)$。

边界处的区分最易出错。二叉树不是二叉搜索树公理库二叉搜索树Binary search tree · BST每个结点左子树键小于、右子树键大于该结点键的二叉树。：后者还要求键满足子树范围约束；也不是堆：堆另加形状与堆序不变量。“每个节点至多两个孩子的无序树”同样不是二叉树——根下只挂一个孩子时，“左独子”与“右独子”是两棵不同的二叉树，作为无序树却是同一棵；反过来，把无序树的孩子随手排成左右，会引入原本不存在的顺序信息。约定也需留意：本页取根深度为 $0$、单节点树高度为 $0$，而不同教材对空树高度取 $-1$ 或不定义，跨文献比较公式前应先对齐约定。

形状与键值也必须分层理解：同一组键可以放进许多不同二叉树形状，只有搜索树、堆等额外不变量才会排除其中一部分。满二叉树要求内部节点都有两个孩子，完全二叉树则只约束逐层填充次序；前者不必完全，后者的末层也可以尚未填满。固定高度 $h$ 时，链形只需 $h+1$ 个节点，而节点数上限为 $2^{h+1}-1$，这正是同一高度下两种极端形状。

二叉树是一族核心结构的公共骨架：加上键序约束得到搜索树，加上形状与堆序约束得到二叉堆公理库二叉堆Binary heap以近完全二叉树表示并满足父子堆序的优先队列结构。，按频率自底向上合并得到 Huffman 编码公理库Huffman 编码Huffman coding反复合并最低概率符号构造期望码长最小前缀码的算法。树，其中叶表示符号、根叶路径给出前缀码。Cartesian Tree公理库笛卡尔树Cartesian tree同时满足下标中序与数组值堆序的唯一二叉树。同时固定数组的中序下标与堆序优先级，把区间最小值和树祖先结构接起来；它不是“任意二叉树再放一组键”，而是由两条序共同确定的专门表示。

遍历序还能把指针树翻译成序列：前序、中序和后序改变递归访问次序，广度优先搜索公理库广度优先搜索Breadth-first search · BFS按无权距离分层访问可达顶点的图遍历算法。则给出层序；它们分别服务序列化、表达式求值与由遍历序重建树。平衡括号树表示公理库平衡括号树表示balanced-parentheses tree representation · BP tree encoding用 DFS 的进入/退出括号串以 2n 位编码有序根树，并把父子、兄弟和子树查询化为 matching 与 excess 搜索。按 DFS 进入/退出写下一对括号，并用括号匹配恢复父子与子树边界；简洁有序树公理库简洁有序树succinct ordered tree · 简洁序树以接近有序树信息下界的位数编码树形，并通过括号原语完成父子、深度与子树导航。在接近信息论下界的 bit 空间中为这些导航操作建立 rank/select 支持。这里改变的是表示与空间模型，不是二叉树的递归定义。编译器的抽象语法树公理库抽象语法树Abstract syntax tree · AST把抽象语法构造表示为有根有序树的常见编译器数据结构。、分治公理库分治法Divide and conquer把问题分成较小同类子问题，递归求解后合并结果的算法设计范式。递归树和比较决策树则继续使用同一形状承载不同语义；最后一种还把比较次数化为根叶路径长度，支撑比较排序下界。