Computing · Data Structures
Binary Trees
二叉树
~ 16 min · v19
二叉树
cs-ds/binary-tree · COMP2521
0 / 5
1 一句话定义
二叉树（binary tree）就是每个节点最多有两个孩子（左孩子、右孩子）的树形结构。
把它想成一张组织架构图：每个人（节点）最多直接管两个下属（一左一右），只能往下连、不能横跨。最上面没有上司的是根，最底层没有下属的是叶子。从老板走到某个员工经过几层，就是这个员工的"深度"。
2 模型 · 自己动手建一棵树
动手之前先想一个问题：上面那张图，用代码到底怎么写出来？ 很多人卡在这——会画树，却不知道树在 C 里长什么样。先看下面这段，再去玩交互区。
这棵树用代码怎么写出来？
三步：① 定义"节点"长什么样 → ② 写个函数造一个节点 → ③ 把节点一个个连起来。下面这段造出来的，正好就是交互区里那棵示例树。
// ① 定义"节点"：装一个值 + 两根指向左右孩子的指针（这就是"二叉树节点"） struct node { int value; struct node *left, *right; // 没有孩子时它们是 NULL }; // ② 造一个新节点：在堆上申请一块、填上值、左右孩子先置空 struct node *newNode(int v) { struct node *n = malloc(sizeof(struct node)); n->value = v; n->left = n->right = NULL; return n; } // ③ 把节点连起来 —— 连出来的正是下面交互区的示例树（注意 70 只有右孩子） struct node *root = newNode(50); root->left = newNode(30); root->right = newNode(70); root->left->left = newNode(20); root->left->right = newNode(40); root->right->right = newNode(80); // 70 没有左孩子，所以不写 root->right->left
对照着看：newNode(50) 就是图里最上面的根；root->left->left = newNode(20) 就是"根的左孩子的左孩子 = 20"；而 70 只写了 right、没写 left，所以它只有一个右孩子 80。看懂"怎么连"之后，就去下面点 ＋ 自己加节点、点 ▶ 看高度怎么算。
二叉树结构编辑器
递归代码 ·
int height(node *t) 递归调用栈（栈顶 = 此刻正在算的那一层）
点 ▶ 演示算高度后，这里会逐层压入 / 弹出。
提示
点节点旁的 ＋ 加孩子；点任意节点看它的深度与子树高度；点 ▶ 演示求树高，看递归从叶子往上汇报。
0
节点数
0
树高
0
叶子数
3 核心要点 · 4 句人话看懂二叉树
每张卡片先用一句大白话说清"它到底在讲什么"，再配最小例子。深度 / 高度那条，记得回到上面点节点看实时数值。
① 根 / 叶 / 内部节点 / 边
一句话：树就是一家人——最上面那位长辈叫"根"，最底下没孩子的叫"叶子"，中间还带着孩子的叫"内部节点"，每根连线就是一条"边"。
根 root：唯一没有父节点的节点（最上面）。叶子 leaf：左右孩子都没有的节点。边 edge：父子之间的连线。规律：n 个节点的树恰好有 n−1 条边——因为除了根，每个节点头上都正好挂着一条边。
根 50
/ \
30 70 ← 内部节点
/ \ \
20 40 80 ← 这行都是叶子
② 深度 vs 高度（最易混！）
一句话：深度往上数到根，高度往下数到叶。两个都数"边"，方向相反——这是考试最爱挖的坑。
深度 depth：从根走到"我"经过几条边（根的深度 = 0，越往下越大）。高度 height：从"我"走到最深的叶子经过几条边（叶子高度 = 0，空子树 = −1）。提示：回到上面点任意节点，深度和高度会实时显示。
深度：自上而下数（根 = 0）↓
高度：自下而上数（叶 = 0）↑
空子树高度 = -1 ← 递归基准，别忘
③ 满 / 完全 / 平衡
一句话：这三个词都在描述树"长得齐不齐"。越齐，查找/插入越接近 O(log n)；长歪成一条链，就退化成 O(n)。
满 full：每个节点要么 0 个孩子、要么 2 个，绝不只生一个。完全 complete：除最后一层外都填满，最后一层还得靠左排。平衡 balanced：每个节点的左右子树高度差 ≤ 1。
满: 完全: 退化(不平衡):
o o o
/ \ / \ \
o o o o o
/ \
o o
④ 二叉树的递归本质
一句话：一棵树 = 根 + 左子树 + 右子树，而左右子树本身又是树。所以处理树几乎都靠递归——"先让孩子算好，我再合并"。
这种"自己套自己"的结构，让求高度的代码短到 5 行：先递归问左右子树的高度，谁高就 +1。空子树返回 −1 是递归基准，让叶子自然得到 0。
struct node { int value; struct node *left, *right; };
int height(struct node *t) {
if (t == NULL) return -1; // 基准：空子树
int l = height(t->left);
int r = height(t->right);
return 1 + (l > r ? l : r);
}
4 错误实验室 · 点一下亲眼看 bug
下面 4 个是初学者写树递归最常翻车的坑——前两个都和"空子树基准"有关，后两个是"递归怎么合并"的经典误解。点击卡片，控制台会模拟真实的段错误 / 错误结果。
① 漏写空子树基准
没有 if(t==NULL) → 解引用空指针，直接段错误
② 基准返回 0 而非 −1
空树写成 return 0 → 整棵树高度多算 1（off-by-one）
③ 用加法代替取最大
写成 1 + height(L) + height(R) → 把"高度"算成了别的东西
④ 只看左孩子判叶子
只查 left==NULL → 漏掉"只有右孩子"的节点（如 70）
// 点击上方任一卡片，查看错误代码与运行效果
$ ./a.out
（等待运行...）
5 即时小测 · 5 题 + 动手例题
这 5 题都卡在初学者最常错的点上——基准值 −1、高度按边数算、深度↔高度搞反、叶子判定漏看右孩子、"满"≠"完全"。每个错误选项都对应一个真实的误解，点错也别灰心，提示会告诉你错在哪。最后再到练习系统亲手写一遍递归求树高。
去做例题：二叉树 · 求树高
去做例题