常见二叉树
📊 常见二叉树对比
| 树类型 | 定义 | 特点 | 举例 | 口诀 | |
|---|---|---|---|---|---|
| 平衡二叉树 (AVL树) | 任意结点左右子树高度差 ≤ 1 | 查找效率接近对数 O(log n)，用于二分查找判定树 | 高度差很小，但不一定“满” | 平衡≠完全 | |
| 完全二叉树 | 只有最底层可以不满，且最底层结点必须从左到右连续 | 节点编号连续，适合用数组存储 | 二叉堆就是完全二叉树 | 完全=从左排队 | |
| 满二叉树 | 所有非叶子结点都有左右孩子，且所有叶子都在同一层 | 结点数 = 2^h - 1 | 高度=3时，结点数=7 | 满=整齐对称 | |
| 最优二叉树 (哈夫曼树) | 带权路径最短的二叉树 | 权重大的叶子离根更近，用于编码压缩 | 哈夫曼编码 | 最优=权重近根 | |
| 二叉搜索树（BST, Binary Search Tree） | BST 的规则 1. 左子树所有结点 < 根结点 2. 右子树所有结点 > 根结点 3. 左右子树本身也都是 BST |
📖 举例
1️⃣ 平衡二叉树
4
/ \
2 6
/ \ /
1 3 5
左子树高度=2，右子树高度=2，差 ≤ 1 ✅
但不是完全二叉树（最底层右边缺 7）。
2️⃣ 完全二叉树
- 从上到下，从左到右排满。
1
/ \
2 3
/ \ /
4 5 6
1
/ \
2 3
/
4
3️⃣ 满二叉树
所有叶子都在同一层，且每个非叶子都有两个孩子。
节点数n = 2^h^-1
1
/ \
2 3
/ \ / \
4 5 6 7