树与二叉树入门
树就像一份家谱:最上面一个根,下面一层层分叉。这一章只学五件事: 树和二叉树长什么样、二叉树怎么存、五条常用结论、四种遍历, 最后用并查集把结点分成组。
7.1 树是什么
7.1.1 用「家谱」理解树
树由结点和连接结点的边组成。它有一个最上面的结点,叫根; 除根以外,每个结点都只有一个双亲,但可以有多个孩子。 像下面这样:
A
/ \
B C
/ \ \
D E F
/
G
- 根:A,它没有双亲。
- 双亲 / 孩子:B 的双亲是 A,A 的孩子是 B、C;E 的双亲是 B,E 的孩子是 G。
- 兄弟:D 和 E 有同一个双亲 B,所以是兄弟。
- 叶子:没有孩子的结点,图里是 D、G、F。
- 度:一个结点有几个孩子。A 的度是 2,E 的度是 1,D 的度是 0。
- 层次 / 深度:根在第 1 层,往下每走一层加 1;这棵树的深度是 4。
7.1.2 两个最基本的事实
- 一棵有
n个结点的树,一定有n−1条边。 - 除根以外,每个结点到根都只有一条路;沿着双亲一直往上走,一定能走到根。
这两句话不用背证明,画一棵树数一数就能明白。
7.2 二叉树
7.2.1 二叉树是什么
二叉树是每个结点最多有两个孩子的树,而且这两个孩子分左孩子和右孩子, 不能随便交换。
它只有五种基本形态:
- 空树;
- 只有根;
- 只有左子树;
- 只有右子树;
- 左右子树都有。
特别注意:只有左孩子和只有右孩子是两种不同的二叉树,不能当成同一棵树。
7.2.2 满二叉树与完全二叉树
满二叉树:每一层都排满,没有空位。深度为 k 的满二叉树有
2k−1 个结点。
完全二叉树:除了最后一层,上面每一层都排满;最后一层的结点必须从左往右连续排列, 中间不能空一个再放一个。
满二叉树(深度 3) 完全二叉树(6 个结点)
A A
/ \ / \
B C B C
/ \ / \ / \ /
D E F G D E F
判断完全二叉树时记住一句话:一个结点如果只有右孩子、没有左孩子,它一定不是完全二叉树。
7.2.3 二叉树怎么存
最直观的存法是二叉链表:每个结点存三样东西——自己的值、左孩子指针、右孩子指针。 没有孩子时,指针为空。
struct Node { char val; Node *left, *right; };
例如上面那棵树,A 的 left 指向 B,right 指向 C;
D 的 left 和 right 都是空指针。大多数树形算法都采用这种存法。
7.3 二叉树的五条常用性质(只记结论)
这五条性质不需要背证明,会拿来算数量、判断完全二叉树就够了。
7.3.1 第 i 层最多有 2i−1 个结点
根在第 1 层,只有 1 个;第 2 层最多 2 个;第 3 层最多 4 个……
例:第 5 层最多有 24 = 16 个结点。
7.3.2 深度为 k 的二叉树最多有 2k−1 个结点
把每一层的最大值加起来:1 + 2 + 4 + … + 2k−1 = 2k−1。
满二叉树正好取到这个最大值。
7.3.3 叶子数 = 度为 2 的结点数 + 1
对任何一棵非空二叉树,设叶子数为 n0,度为 2 的结点数为
n2,则 n0 = n2 + 1。
例:一棵树有 5 个叶子,那么度为 2 的结点就有 4 个。
7.3.4 n 个结点的完全二叉树深度
深度 = ⌊log2 n⌋ + 1。
例:1000 个结点,29 = 512 ≤ 1000 < 1024 = 210,
所以深度是 9 + 1 = 10。
7.3.5 完全二叉树的下标关系(从 1 开始编号)
结点 i(i>1)的双亲是 ⌊i/2⌋,左孩子是 2i,
右孩子是 2i+1。如果 2i 超过结点总数,就没有左孩子;
如果 2i+1 超过,就没有右孩子。
例:6 个结点的完全二叉树,结点 3 的左孩子是 6,右孩子 7 不存在; 结点 6 的双亲是 3。
7.4 四种遍历
7.4.1 遍历是什么
遍历就是按某种规则,把树上的每个结点都访问一次,而且只访问一次。 常用的有四种顺序:
- 先序:根 → 左子树 → 右子树;
- 中序:左子树 → 根 → 右子树;
- 后序:左子树 → 右子树 → 根;
- 层序:从根开始,一层一层、从左到右访问。
7.4.2 手工走一遍
用 7.1.1 的那棵树练习:
A
/ \
B C
/ \ \
D E F
/
G
- 先序:先 A,再走完 B 的子树,最后走 C 的子树 →
ABDEGCF。 - 中序:先走 B 的左边 D,再回到 B,再走 B 的右边 E(E 先走 G),然后 A,最后 C、F →
DBGEACF。 - 后序:先走完 D、G、E、B,再走 F、C,最后 A →
DGEBFCA。 - 层序:一层一层读,正好是
ABCDEFG。
两个小规律:先序的第一个一定是根;后序的最后一个一定是根; 中序里根左边的结点都在左子树,右边的都在右子树。
7.4.3 看动画
下面四个动画分别演示四种遍历,注意绿色是已经访问过的结点:
7.4.4 递归代码
三种深度优先遍历的代码几乎一样,区别只在「什么时候访问根」这一行:
#include <iostream>
using namespace std;
struct Node {
char val;
Node *left, *right;
explicit Node(char v) : val(v), left(nullptr), right(nullptr) {}
};
void preOrder(Node* p) {
if (!p) return;
cout << p->val; // 先访问根
preOrder(p->left);
preOrder(p->right);
}
void inOrder(Node* p) {
if (!p) return;
inOrder(p->left);
cout << p->val; // 中间访问根
inOrder(p->right);
}
void postOrder(Node* p) {
if (!p) return;
postOrder(p->left);
postOrder(p->right);
cout << p->val; // 最后访问根
}
int main() {
/* 手工建出 7.1.1 的那棵树 */
Node* A = new Node('A');
Node* B = new Node('B');
Node* C = new Node('C');
Node* D = new Node('D');
Node* E = new Node('E');
Node* F = new Node('F');
Node* G = new Node('G');
A->left = B; A->right = C;
B->left = D; B->right = E;
E->left = G;
C->right = F;
cout << "先序: "; preOrder(A); cout << "\n"; // ABDEGCF
cout << "中序: "; inOrder(A); cout << "\n"; // DBGEACF
cout << "后序: "; postOrder(A); cout << "\n"; // DGEBFCA
return 0;
}
每个结点只访问一次,所以时间复杂度是 O(n);
递归深度最多等于树的高度。
7.5 并查集:把结点分成组
7.5.1 它解决什么问题
有 n 个元素,需要做两件事:
- find(x):找到 x 所在组的“代表”,用来判断两个元素是不是同一组;
- union(a, b):把 a 和 b 所在的两个组合并成一个组。
典型用途:判断两个元素是否在同一组,比如判断图里两个点是否连通。
7.5.2 用「父结点数组」表示
每个组看成一棵树,树的根就是这一组的代表。用一个数组 fa 记录每个结点的父亲:
fa[x] = x 说明 x 是根。
例如 5 个元素,fa = [0, 0, 1, 3, 3]:
- 0 是根,1 的父亲是 0,2 的父亲是 1,所以 {0,1,2} 是一组,代表是 0;
- 3 是根,4 的父亲是 3,所以 {3,4} 是另一组,代表是 3。
find(x):沿着父亲一直往上走,直到 fa[x] == x,这个 x 就是代表。
union(a, b):先找到两组的根,再让一个根指向另一个根,
例如 fa[find(a)] = find(b)。
一个小优化叫路径压缩:find 的时候,把沿途经过的结点直接连到根上, 以后再找就会更快。并查集的基础就这些,先会用 find / union 即可。
7.6 几句话小结
- 树是「一个根、下面分叉」的层次结构;二叉树每个结点最多两个孩子,分左右。
- 完全二叉树要求最后一层从左往右连续,不能只有右孩子而没有左孩子。
- 五条常用性质只记结论:第 i 层最多
2i−1个、深度 k 最多2k−1个、n0 = n2 + 1、完全二叉树深度⌊log2 n⌋ + 1、下标关系。 - 四种遍历只是「访问根」的时机不同:先序、中序、后序、层序。
- 并查集用父结点数组表示分组,核心操作是 find 找代表、union 合并两组。