1. 引言
本文将介绍二叉树这一重要的数据结构及其基本特性。接着会介绍六种不同类型的二叉树，并配以图示帮助理解。最后，我们还会讨论二叉树在实际开发中的常见应用场景。
如果你是 Java 开发者，应该对树形结构并不陌生。在实现如二叉搜索树、堆、红黑树等复杂结构时，二叉树都是其基础。掌握其基本概念和分类，有助于你更好地理解这些高级结构。
2. 定义
✅ 二叉树（Binary Tree） 是一种层次结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。
在链式存储结构中，一个二叉树节点通常包含以下三个部分：
- 指向左子节点的引用
- 存储数据的字段
- 指向右子节点的引用
下面是一个二叉树的示意图：
3. 基本性质
了解二叉树的几个基本性质有助于我们在实际使用中进行性能分析和空间评估：
- 如果根节点的层级为 0，那么第
l层最多有2^l个节点。 - 当每个节点都有 0 或 2 个子节点时，叶子节点的数量比有两个子节点的节点多 1。
- 如果树的高度为
h（叶子节点高度为 1），则最多有2^h - 1个节点。 - 若叶子节点数为
L，则树至少有⌈log₂L⌉层，最多有L+1层。 - 有
n个节点的二叉树最少有⌈log₂(n+1)⌉层。 - 有
n个节点的二叉树最小高度为⌈log₂n⌉，最大高度为n。 - 有
n个节点的二叉树共有n+1个空引用（null references）。
这些性质在分析树的结构和性能时非常有用，尤其在判断是否为平衡树时经常用到。
4. 二叉树的类型
接下来我们介绍六种常见的二叉树类型，并配以图示帮助理解。
4.1 全二叉树（Full Binary Tree）
全二叉树是指每个非叶子节点都恰好有两个子节点的二叉树。
4.2 完美二叉树（Perfect Binary Tree）
完美二叉树是所有叶子节点都在同一层，且每个非叶子节点都有两个子节点的二叉树。
4.3 完全二叉树（Complete Binary Tree）
完全二叉树是指除最后一层外，其余层都被节点填满，且最后一层的节点尽可能靠左排列。
这种结构是实现堆（heap）的基础。
4.4 退化树（Degenerate / Pathological Tree）
退化树是一种每个节点只有一个子节点的二叉树，其性能退化为链表级别（O(n)）。
4.5 偏斜树（Skewed Binary Tree）
偏斜树是退化树的一种特例，分为左偏斜（所有节点只有左子节点）和右偏斜（所有节点只有右子节点）两种。
4.6 平衡二叉树（Balanced Binary Tree）
平衡二叉树是指每个节点的左右子树高度差不超过 1 的二叉树。常见的实现包括 AVL 树 和 红黑树。
这类结构在搜索、插入、删除等操作中具有良好的性能保障。
5. 应用场景
二叉树作为基础结构，在许多高级数据结构中都有广泛应用，例如：
- 二叉搜索树（Binary Search Tree）
- 语法树（Syntax Tree）
- 堆（Heap）
- 哈夫曼树（Huffman Tree）
- 红黑树（Red-Black Tree）
- AVL 树
- Trie 树（Binary Trie）
- GGM 树、T 树、Treap
在实际应用中，二叉树也广泛用于：
- 空间划分（Binary Space Partition）
- 堆排序（Heap Sort）
- 霍夫曼编码（Huffman Coding）
- 虚拟内存管理
- 数据库索引结构
⚠️ 踩坑提醒：不要把“平衡二叉树”和“完全二叉树”混为一谈。前者强调左右子树高度差不超过 1，后者强调结构的填充顺序和左对齐。
6. 总结
本文介绍了二叉树的基本概念、性质及其六种常见类型，并结合图示帮助理解。最后我们还列举了其在实际开发中的应用。
掌握这些基础知识，对于理解更复杂的树结构（如 AVL 树、红黑树）和实现高效的查找、插入、删除操作至关重要。建议读者结合实际项目多加练习，以加深理解。