形式陈述

二叉树是每个节点至多有一个左孩子和一个右孩子的有根有序树；左右位置不同，即使只有一个孩子也需区分。深度是根到节点的边数，高度是节点到叶的最长边数。含 $n$ 个节点的二叉树有 $n-1$ 条父子边；高度可从 $\lfloor {\log }_{2}n\rfloor$ 到 $n-1$。满二叉树每个内部节点恰有两个孩子，完全二叉树则除最后一层外全满且最后一层从左填充。

直觉

二叉树把问题递归分成左右两个子问题；结构是否平衡决定递归路径长度，也决定搜索、堆和表达式求值的效率。

例子与边界

表达式 $(a+b)c$ 可用乘法为根、左子树为加法表示。按根深度为 $0$ 的约定，高度为 $h$ 的二叉树节点数至多 $2^{h+1}-1$；等价地，含 $L$ 层时至多有 $2^L-1$ 个节点。二叉树不等于二叉搜索树：前者没有键序条件；也不等于堆，后者还要求形状和优先级不变量。把无序树的孩子任意分成左右会引入额外顺序信息。树的递归定义允许空树，这可简化算法基例。

推论与应用

二叉树支撑搜索树、堆、语法树、Huffman 树和分治结构；遍历顺序则连接递归控制流与线性序列。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Parts I–VI。
• Robert Sedgewick and Kevin Wayne, Algorithms, 4th ed., Addison-Wesley, 2011，Chs. 1–6。