二叉树的定义与特点

二叉树的定义

二叉树（Binary Tree） 是 $n$（$n \ge 0$）个结点的有限集合。当 $n = 0$ 时为空二叉树。当 $n > 0$ 时：

• 有且仅有一个根结点。
• 其余结点分为两个互不相交的子集 $T_L$ 和 $T_R$，分别称为左子树和右子树，且它们本身也是二叉树。

与一般树的区别

特性	一般树	二叉树
最大度数	无限制	2
子树顺序	无顺序（无序树）	严格区分左、右子树
空树	允许	允许
子树数量	任意	0, 1, 2

二叉树的特点

1. 每个结点最多有两棵子树（度 ≤ 2）。
2. 左右子树有序，交换后成为不同的二叉树（除非是空树或单结点）。
3. 递归定义：二叉树本身是由根和左右子树递归构成。
4. 二叉树可以是空树。
5. 二叉树有五种基本形态：
   • 空二叉树
   • 只有根结点
   • 只有左子树
   • 只有右子树
   • 左、右子树均非空

重要性质

详见 [[二叉树的五条核心性质]]。

应用场景

• 表达式树（编译器）
• 哈夫曼树（数据压缩）
• 二叉搜索树（高效查找）
• 堆（优先队列）