Tree
树(Tree)
[TOC]
树的基本概念
树是一种非常重要的非线性数据结构，树的一个节点可能会生出多个分支。一般而言，一棵树会包含一个根节点，向下延伸出若干子节点，每个末端的节点被称为叶子节点。
有根树
有根树存在一个根节点Root，如下：
对于图中概念的一些补充：
- 节点拥有的子节点个数叫做节点的度。
- 具有相同深度的节点处于同一层，方便表示。
- 节点和节点之间的线叫做边。
- 路径：指从树上一点到另外一点所经过的不重合的点和边的集合，题目中有时会单指点或边的集合。
- 一颗 $n$ 个节点的树，一定有 $n-1$ 条边
无根树
二叉树
二叉树是一种特殊的树。
- 所有节点的度都不超过2的树称为二叉树。
- 因为每个二叉树的节点最多只会有两个子结点，它的两个子节点一般会被称为左、右儿子，两棵子树一般会被称为左、右子树。
- 左、右儿子甚至根节点本身都有可能缺失（一个节点都没有可以称为空二叉树）。
满二叉树和完全二叉树
二叉树也有两个比较特殊的类型：满二叉树和完全二叉树。
- 满二叉树：所有层的节点全满。
- 满二叉树的一些规律
- 第 $n$ 层的节点个数为 $2^{n-1}$
- 深度为 $n$ 的满二叉树节点数为 $2^0 + 2^1 + 2^2 + \dots + 2^{n-1}= 2^n-1$
- 满二叉树的一些规律
- 完全二叉树：除了最后一层以外，其他层的节点个数全满，而且最后一层的节点从左到右排满直到最后一个节点。
- 完全二叉树的一些规律
- 完全二叉树的节点个数不会少于 $(2^{n-1}-1)+1 = 2^{n-1}$
- 完全二叉树的节点个数不会多于 $2^{n} - 1$
- 一棵完全二叉树，设当前节点为 $t$，其父节点为 $t/2$，其左儿子为 $2t$，其右儿子为 $2t+1$，借助该规律，我们可以将完全二叉树使用数组进行存储。
- 完全二叉树的一些规律
- 完全二叉树的存储
- 完全二叉树由于它的特性，可以简单用数组来模拟其结构
- 一般会以数组$[1]$位置为根节点建立二叉树
- 数组$[t]$位置的左儿子和右儿子对应的位置分别为$[2t]$和$[2t+1]$，父节点的位置为$[t/2]$。
- 堆、线段树等数据结构的建立也会参考这个方式
完全二叉树的建立（使用数组），使用这种方法建立非完全二叉树，会导致空间的浪费：
1 | void build(int t) { |
为了解决这个问题，我们可以使用其他方法来完成一般二叉树的存储，可以用数组下标模拟节点编号，用多个数组来记录节点信息。为了方便，我们也可以使用结构体来存储这些信息：
1 | // 使用结构体来实现上述操作 |
当然，作为一种树形结构，使用指针显然是更合适的方法：
1 | // 使用指针来实现上述操作 |
使用指针的一些操作：
- 新建节点：
1
2
3
4
5
6
7struct TreeNode {
int value;
TreeNode *l, *r, *fa; // 初始为 NULL
TreeNode(int x){ value = x; }
};
TreeNode* treeNode = new TreeNode(x); - 根节点初始化：
1
2TreeNode* root;
root = new TreeNode(v); - 插入节点：
1
2
3
4
5
6
7
8
9
10
11void Insert(TreeNode* fa, TreeNode* p, int flag){
// flag = 0 插入到左边
// flag = 1 插入到右边
if (!flag)
fa->l = p;
else
fa->r = p;
p->fa = fa;
}
TreeNode* treeNode = new TreeNode(v);
Insert(fa, treeNode, flag); - 删除节点
1
// 删除节点
二叉树的遍历
二叉树的遍历可分为先序遍历、中序遍历和后序遍历，这三种方式以访问根节点的时间来区分。
先序遍历（Degree-Left-Right, DLR）：根→左→右
中序遍历（Left-Degree-Right, LDR）：左→根→右
先序遍历（Left-Right-Degree, LRD）：左→右→根
在该图中，先序遍历的结果为 1 2 4 5 3 6 7，先序遍历代码如下：
1 | void preOrder(TreeNode* treeNode) { |
在该图中，中序遍历的结果为 4 2 5 1 6 3 7，中序遍历代码如下：
1 | void inOrder(TreeNode* treeNode) { |
在该图中，后序遍历的结果为 4 5 2 6 7 3 1，后序遍历代码如下：
1 | void postOrder(TreeNode* treeNode) { |
除了上述的几种遍历方式，还有层级遍历（BFS）方式对树进行遍历。层级遍历是借助队列（Queue）来实现的，其过程可以描述如下：
层级遍历的代码如下：
1 | TreeNode* q[N]; |
计算节点的深度
我们可以在遍历树的时候同时进行节点深度的记录，简单来讲就是：
$$depth_{儿子} = depth_{父亲} + 1$$
有根树(Tree)
这里不再是二叉树这种特殊的树，而是一般意义的树。
树的存储方式
vector/链表1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18// vector 方式
vector<int> nodes[N + 1];
int n, father[N + 1];
// 在 x 和 y之间构建一条边
void addEdge(int x, int y) {
nodes[x].push_back(y);
}
// 遍历 x 的所有儿子
int l = nodes[x].size();
for (int i = 0; i < l; i++) {
nodes[x][i];
}
for (auto i: nodes[x]) {
...
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18// 链表方式
struct Node {
int where;
Node *next;
} *head[N + 1], a[M];
int n, father[N + 1], l = 0;
void addEdge(int x, int y) {
a[++i].where = y;
a[l].next = head[x];
head[x] = &a[l];
}
// 遍历 x 的所有儿子
for (Node* p = head[x]; p; p->next) {
p->where;
}
有根树遍历
遍历一棵树一般有 DFS 和 BFS 两种方式。
DFS：深度优先搜索，从一个节点开始，选择一条路径并走到底，并通过回溯来访问所有节点。
BFS：广度优先搜索，也称层级顺序探索，从一个节点开始，遍历该节点的所有子节点，或称按照深度从小到大的顺序依次遍历所有点。
- 有根树的DFS序
有根树的 DFS 序是指，从根节点开始的深度优先搜索过程中，依次记录的点所生成的序列。
对于上图，所生成的 DFS 序即为ABCDEFGHIJKLMN。当然这个只是其中一种 DFS 序，因为A可以走向B，也可以走向E，当然也可以走向F。不同的走向会有不同的 DFS 序。1
2
3
4
5
6
7
8
9
10
11vector<int> dfn; // 用于存储 DFS 序, 常用 DFN 表示 DFS 序
// dfn 中的元素即为 DFS 序
void dfs(int x) {
dfn.push_back(x);
// for x的所有儿子y { dfs(y); }
//
for (Node* p = x; p; p->next){ dfs(p->next) }
}
dfs(root); - 有根树的BFS序
有根树的 BFS 序是指，从根节点开始的广度优先搜索过程中，依次记录的点所生成的序列。
对于上图，所生成的 BFS 序即为ABENCDFMGJHIKL。当然这个只是其中一种 BFS 序，因为同一深度可能会有不同的遍历顺序，如深度为 $2$ 时，BEN、BNE、EBN、…都是可能出现的顺序，不同的顺序会有不同的 BFS 序。1
2
3
4
5
6
7
8
9
10
11
12
13void bfs(int root) {
// 将 root 加入队列 q;
q.push(root);
// 遍历队列 q
while(队列 q 非空) {
x = q.top(); // 取队首元素
q.pop(); // x 出队
for x的所有儿子y {
y 入队;
}
}
}
无根树(Unrooted Tree)
无根树即没有固定根结点的树，树中的节点只有相邻关系而没有父子关系。无根树有几种等价的形式化定义（建议搭配图论一起学习）：
- 有 $n$ 个结点， $n−1$ 条边的连通无向图
- 无向无环的连通图
- 任意两个结点之间有且仅有一条简单路径的无向图
- 任何边均为桥的连通图
- 没有圈，且在任意不同两点间添加一条边之后所得图含唯一的一个圈的图
如下图所示，即一棵无根树：
无根树中的任意一个节点可以被指定为根，变成一棵有根树。
无根树的遍历
遍历一棵无根树一般也有 DFS 和 BFS 两种方式。
遍历无根树时，可以从任意一个节点开始，以类似有根树的方式，遍历整棵树。唯一的区别是在进入一个新节点时，需要记录这个节点的来源节点，在遍历新节点的相邻节点时，避免重复访问来源节点即可。
- 无根树的 DFS
1
2
3
4
5
6
7
8
9void dfs(int from, int x) {
for x的所有响铃节点y {
if (y != from) {
dfs(x, y);
}
}
}
dfs(-1, x); - 无根树的 BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16void bfs(int x) {
// 将 x 加入队列 q，x 的来源为空
while (队列 q 非空) {
x = q.top();
from = x的来源节点;
q.pop;
for x的所有相邻节点 y {
if (y != from) {
y 入队;
记录 y 的来源节点为 x;
}
}
}
}
bfs(x);
树的直径
- 树的直径是指树上任意两个节点之间最长（路径的长度一般指的是路径经过的边的数量）的路径。
- 一棵树可以存在很多条直径，他们的长度相等。
- 树的直径的中间节点被称为树的中心（图中C节点），如果直径上有偶数个节点，那么中间的两个节点都可以是树的中心。
- 树的中心到其它点的最长路径最短。