入门：树的术语、二叉树定义与存储
基于通用数据结构概念 · 核于 2026-07
速查
- 定义：二叉树是每个节点最多有两个子节点（左孩子、右孩子）的有根树，空树
∅也是合法二叉树，递归定义为「根 + 左子树 + 右子树」。 - 核心术语：根（唯一无父节点）、叶（无孩子的节点）、度（节点孩子数，二叉树中 ≤ 2）、深度（根到该节点的边数，根深度为 0）、高度（该节点到最远叶的边数，叶高度为 0）、树的深度/高度 = 根的深度 0 / 根到最远叶的边数。
- 三种特殊二叉树：满二叉树（每个节点要么 0 度要么 2 度）、完全二叉树（除最后一层外都填满，最后一层从左到右连续，堆就是它）、完美二叉树（每层都满，第 k 层恰有 2^k 个节点，共 2^(k+1)-1 个）。
- 链式存储：
{val, left, right}节点 + 左右指针，增删改 O(1) 改指针、访问需沿指针走；空间 O(n) 额外存两个指针——通用二叉树的标准存储。 - 数组存储：把节点按下标存数组，根在 0，节点
i的左孩子2i+1、右孩子2i+2、父(i-1)>>1——只适合完全/满二叉树（否则大量空洞浪费空间），堆、线段树、二叉树数组表示竞赛题用它。 - 递归思维：90% 的二叉树问题 =「处理根 + 递归左子树 + 递归右子树 + 合并结果」——求高度/深度、翻转、判断对称、最近公共祖先、子树判断都是这个套路。
- 遍历四件套：前序（根左右）、中序（左根右）、后序（左右根）是 DFS；层序（逐层从左到右）是 BFS——根的访问时机决定前/中/后。
- BST 的本质：左子树值 < 根 < 右子树值（且左右子树也各自是 BST）——中序遍历得升序序列，这是「一边增删一边有序」的结构。
- 复杂度依赖高度 h：查找/插入/删除 O(h)；平衡树 h = O(log n)，退化为链表 h = O(n)。
- 与链表/数组的差异：数组 O(1) 访问 O(n) 增删；链表 O(n) 访问 O(1) 增删（已知节点）；BST 介于两者之间，增删查都 O(h)，平衡时 O(log n)。
- 进阶顺序：遍历 → BST 与平衡树 → 参考。
一、树的核心术语
二叉树相关的术语必须先分清，尤其是深度与高度——它们常被混用，但严格定义不同。
1 ← 深度 0（根）
/ \
2 3 ← 深度 1
/ \ \
4 5 6 ← 深度 2（4、5、6 是叶子）| 术语 | 定义 | 例子（上图） |
|---|---|---|
| 根（root） | 唯一无父节点的节点 | 1 |
| 叶（leaf） | 无孩子的节点（度为 0） | 4、5、6 |
| 度（degree） | 节点的孩子数，二叉树中 ∈ | 节点 2 的度是 2，节点 3 的度是 1 |
| 深度（depth） | 从根到该节点的边数（根深度为 0） | 节点 4 深度 2 |
| 高度（height） | 从该节点到最远叶的边数（叶高度为 0） | 节点 2 高度 1，节点 1 高度 2 |
| 树的深度/高度 | 根的深度（0）/ 根到最远叶的边数 | 这棵树深度 0、高度 2 |
注意约定差异：有些教材把根深度记为 1（边数 +1）、叶高度记为 1，本站统一用「边数」约定（根深度 0、叶高度 0），树的深度和高度在数值上相等。刷题时看题意，深度「自顶向下」从根累加，高度「自底向上」从叶累加——这个方向性差异决定了递归写法（深度要传参往下带，高度要递归返回往上合）。
二、二叉树定义
二叉树是递归定义的——要么是空树 ∅，要么是「根 + 左子树 + 右子树」，其中左右子树本身也是二叉树。
js
class TreeNode {
constructor(val, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
// 一棵示例树： 1
// / \
// 2 3
const root = new TreeNode(1,
new TreeNode(2),
new TreeNode(3),
);每个节点只关心自己的 val 和 left/right 两个指针——这种「我只需知道自己和左右子树」的局部性，是递归算法能成立的根基。
三、三种特殊二叉树：满、完全、完美
这三个概念容易混淆，必须分清——它们对应不同的结构约束和应用场景。
| 类型 | 约束 | 节点数（高 h） | 典型应用 |
|---|---|---|---|
| 满二叉树（Full） | 每个节点要么 0 个孩子要么 2 个孩子（度为 0 或 2） | — | 表达式树、哈夫曼树 |
| 完全二叉树（Complete） | 除最后一层外全填满，最后一层从左到右连续无空缺 | 节点数 n 满足特定范围 | 堆（优先队列） |
| 完美二叉树（Perfect） | 每层都满，第 k 层恰 2^k 个节点 | 2^(h+1) − 1 | 理想平衡 BST、教学举例 |
满二叉树 完全二叉树 完美二叉树
1 1 1
/ \ / \ / \
2 3 2 3 2 3
/ / \
4 4 5- 满强调「非叶节点必有两子」——叶子可以只在一层或多层。
- 完全强调「层序遍历紧凑无空缺」——最后一层可以不满，但必须左对齐，中间不能跳。堆用数组存完全二叉树正是利用这种紧凑性：下标
2i+1/2i+2找孩子不会有空洞。 - 完美最严格——所有层都满，节点数固定
2^(h+1)-1。常说的「理想平衡 BST」就是完美二叉树，高度h = log2(n+1) - 1。
四、链式存储 vs 数组存储
二叉树有两种存储方式，适用场景截然不同。
链式存储（通用）
每个节点是一个对象，存值和左右孩子指针——这是通用二叉树的标准存储，几乎所有 BST、表达式树、决策树都用它。
js
class TreeNode {
constructor(val, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}- 优点：支持任意形状的二叉树；增删只需改指针 O(1)（找到节点后）；结构清晰。
- 缺点：每个节点多存两个指针（64 位系统 16 字节），空间开销大；节点分散在堆上，遍历缓存不友好。
数组存储（完全/满二叉树专用）
把节点按层序存进数组，靠下标算父子关系——只适合完全/满二叉树，否则大量空洞浪费空间。
完全二叉树: 数组（下标 → 节点）:
0 [0] = 根
/ \
1 2 [1][2] = 第 1 层
/ \ [3][4] = 第 2 层（连续左对齐）
3 4父子下标映射（根在下标 0）：
| 关系 | 公式 |
|---|---|
节点 i 的左孩子 | 2i + 1 |
节点 i 的右孩子 | 2i + 2 |
节点 i 的父节点 | (i - 1) >> 1（整除 2） |
- 优点：零指针开销，内存紧凑；下标算父子 O(1)，缓存友好——堆、线段树、树状数组全靠它。
- 缺点：只适合完全/满二叉树；普通二叉树用数组会有大量
null空洞（最坏退化成单链表时要 2^h 大小的数组）。
五、递归思维：左右子树
二叉树的递归定义决定了绝大多数操作都用**「处理根 + 递归左 + 递归右 + 合并」**的范式。下面用两个高频题演示。
求树的高度
js
function maxDepth(root) {
if (root === null) return 0; // 空树高度 0
const leftH = maxDepth(root.left); // 递归左子树
const rightH = maxDepth(root.right); // 递归右子树
return Math.max(leftH, rightH) + 1; // 合并：取大者 +1（根这层）
}高度是「自底向上」的量——叶返回 0，每层 +1 往上合。
翻转二叉树（LeetCode 226）
js
function invertTree(root) {
if (root === null) return null;
const left = invertTree(root.left); // 递归翻转左子树
const right = invertTree(root.right); // 递归翻转右子树
root.left = right; // 合并：交换根的左右孩子
root.right = left;
return root;
}核心套路：只要操作是「对每个节点都做相同的事，再递归处理子树」，就能套这个范式——求深度、翻转、判断对称、最近公共祖先、路径和、子树判断无一例外。
下一步
理解了树的术语、存储和递归思维后，下一步是二叉树最基础也最高频的操作——遍历：前序/中序/后序（DFS）与层序（BFS），以及它们如何从「递归」改写成「迭代」，见遍历：前序、中序、后序与层序。