三、二叉树的定义和基本术语

1. 二叉树的基本概念

二叉树是 n（n≥0） 个结点的有限集合：

• 空二叉树（n=0）；
• 非空二叉树：根结点 + 两个互不相交的左子树和右子树（均为二叉树）。
• 特点：每个结点至多2棵子树，左右子树不可颠倒（有序树）。

2. 二叉树的五种状态

空二叉树、只有根节点、只有左子树、只有右子树、左右子树都有。

3. 特殊的二叉树

（1）满二叉树

• 定义：高度为h，含 2^h - 1 个结点的二叉树；
• 特点：仅最后一层有叶子结点，无度为1的结点；按层序编号时，结点i的左孩子为 2i，右孩子为 2i+1，父节点为 ⌊i/2⌋。

（2）完全二叉树

• 定义：每个结点与高度为h的满二叉树中编号1~n的结点一一对应；
• 特点：仅最后两层可能有叶子结点，最多1个度为1的结点；编号规则同满二叉树，i > ⌊n/2⌋ 为叶子结点。

（3）二叉排序树

• 性质：左子树所有结点关键字 < 根结点关键字，右子树所有结点关键字 > 根结点关键字（左右子树也为二叉排序树）；
• 用途：元素排序与搜索。

（4）平衡二叉树

• 性质：任一结点的左、右子树深度之差不超过1；
• 优势：更高的搜索效率。