二叉树基础及常见类型 摘要
raw/articles/2026/05/二叉树基础及常见类型
核心观点
-
二叉树是最重要的基础数据结构：多数高级数据结构（红黑树、多叉树、二叉堆、图、字典树、并查集、线段树等）均基于二叉树；同时二叉树是一种核心算法思维，回溯、BFS、动态规划等穷举算法本质是将问题抽象为树结构。
-
常见二叉树类型：
- 满二叉树（Perfect Binary Tree）：每层节点全满，总节点数=2^h -1（h为深度）。注意中英文术语差异：中文「满二叉树」对应英文 Perfect Binary Tree，英文 Full Binary Tree 指所有节点要么无子节点、要么有两个子节点。
- 完全二叉树（Complete Binary Tree）：节点紧凑靠左排列，除最后一层外每层全满。特点：可用数组存储，父子节点索引有规律；左右子树至少一棵是满二叉树。
- 二叉搜索树（BST）：左子树所有节点值<当前节点值<右子树所有节点值（左小右大）。优势：可快速查找、范围查询。
- 高度平衡二叉树：每个节点的左右子树高度差≤1，树高为O(logN)，增删查改效率高。
- 自平衡二叉树：增删节点时自动调整结构保持平衡，典型实现为红黑树（自平衡BST）。
-
二叉树实现方式：
- 链式存储：常见
TreeNode结构，含左右子节点指针。 - 数组存储：完全二叉树/二叉堆等场景使用，利用索引规律。
- 哈希表（邻接表）：用键值对表示父子关系，等价于图的邻接表表示。
- 递归树：基于函数调用栈生成的递归树结构。
- 链式存储：常见
关键术语对照
| 中文术语 | 英文术语 | 说明 |
|---|---|---|
| 满二叉树 | Perfect Binary Tree | 每层全满 |
| 完全二叉树 | Complete Binary Tree | 紧凑靠左排列 |
| 二叉搜索树 | Binary Search Tree (BST) | 左小右大 |
| 高度平衡二叉树 | Height-Balanced Binary Tree | 左右子树高度差≤1 |
| 自平衡二叉树 | Self-Balanced Binary Tree | 自动调整保持平衡 |
相关概念
插图
