C++知识点总结(50)：多叉树

大家好，欢迎来到IT知识分享网。

一、概念

1. 数据结构

一般情况下，我们会将数据结构分为逻辑结构和物理结构，其中逻辑结构是我们的逻辑下存储的结构，而物理结构是计算机的逻辑下存储的结构。数据结构的分类可以参见下表：

2. 树的基础知识

树是一种非线性的数据结构，每个数据都是一对多的关系，由结点和边组成。树是有 $n$（$n\ge 0$）个结点组成的具有分支和层次特性的数据集合。

树当中的数据就是 结点。

结点的深度：设根结点的深度为 $1$（根据题目），其他根结点深度为其父节点深度加 $1$。
结点的高度：设叶结点的高度为 $1$（根据题目），其他结点高度为其他子结点高度加 $1$。

层次：从根开始，根为第 $1$ 层，根的子结点为第 $2$ 层，以此类推。
路径：对于树中两点不同的结点，如果从一个结点出发，自上而下沿着树中连着结点的线段能到达另一个结点，称为它们之间存在着一条路径。

一棵树中，结点最大的度就是 树的度。
一个结点拥有子树的个数称为 结点的度。

具有相同父结点的结点被称为 兄弟结点。
某个结点的直接后继结点被称为该结点的 子结点。
某个结点的直接前驱结点被称为该结点的 父结点。
没有直接前驱，只有直接后继的结点为 根结点。
一棵树中，度为 $0$ 的结点称为 叶结点。

当 $n>1$ 的时候，除根结点以外其余结点可以分为 $m$ 个互不相交的有限集合，其中每个集合本身又是一棵树，这些集合称为这棵树的 子树。
当有 $m$（$m\ge 1$）个树的集合时，称呼其为 森林。
当 $n=0$ 的时候，树为 空树。

3. 树的相关概念

性质1： 树中的结点数等于所有结点的度之和加 $1$，即：
$$n=1+n_1\times 1+n_2\times 2+\cdots$$

性质2： 树中的结点树等于所有结点个数总和，即：
$$n=n_0+n_1+n_2+\cdots$$

性质3： $n$ 个结点的树中有 $n-1$ 条边。

4. 树的遍历

• 先序（根）遍历
  先遍历根结点，然后遍历左子树和右子树
  
• 中序（根）遍历
  先遍历左子树，再遍历根节点和右子树
  
• 后序（根）遍历
  先遍历左子树，在遍历右子树和根结点
  
• 层序（根）遍历
  一层一层地遍历每一层的所有结点
  

5. 多叉树

顾名思义，就是很多个分叉的树。后续也会称作 $m$ 叉树。

性质1： 在多叉树中，第 $k$ 层最多有 $m^{k-1}$ 个结点（$k\ge 1$）。

性质2： 多叉树的高度为 $h$，则整个 $m$ 叉树最多有 $\frac{m^h-1}{m-1}$ 个结点（$h\ge 1$）。

性质3： 根据性质2，$\frac{m^h-1}{m-1}\ge n$，那么 $m^h\ge n(m-1)+1$，因此 $h\ge {\log }_m(n(m-1)+1)$。

二、绘制树

1. 知先中得后

首先通过先序找到根 a，然后通过中序找到左子树（d g b）和右子树（e c h f）。

对于左子树（d g b），先序是（b d g），中序是（d g b）。通过先序找到根 b，然后通过中序找到左子树（d g）并且它没有右子树。

然后再看（d g），先序和中序都是（d g）。通过先序找到根 d，然后通过中序找到 d 的右孩子 g。

对于右子树（e c h f），先序确定根是 c，中序确定 c 的左孩子是 e，右子树是（h f），推出 h 是 f 的左孩子。

因此，后序遍历是 g d b e h f c a。

2. 知中后得先

因此，先序遍历是 a b d g c e f h。

3. 知先后猜结点数

【NOIP 2010 普及组 T17】 一颗二叉树的前序遍历是 ABCDEFG，后序遍历是 CBFEGDA，否则结点的左子树的结点个数可能是（ A ）。
A. 2
B. 3
C. 4
D. 5

我们可以直接用试的方法：

4. 知中层得先

根据层序遍历得定义，那么层序得根结点，即 A 就是这棵树得根结点。根据中序，左子树是（DBE），右子树是（C）。

对于左子树，根据层序得到根结点 B，再根据中序推导出左孩子是 D，右孩子是 E。那么这棵树如下：

三、树的操作

1. 建树

首先，每个结点都可以当作是一个数组中的元素，它有三个信息：自己本身、父结点、左孩子、右孩子。所以我们可以考虑用 struct[] 来实现。

2. 转换

1. 找根结点（先序、层序的头 / 后序的尾）
2. 存储根结点
3. 在中序找到左子树和右子树
4. 在左子树重复步骤 1~4，直到碰到叶结点
5. 在右子树重复步骤 1~4，直到碰到叶结点

根据上面的步骤，我们直到可以用递归的方法来实现。

四、例题

1. 知中层得先

#include <iostream> #include <string> using namespace std; int num[130]; // 下标: ASCII 元素: 下标 string InOd, LvOd; void dfs(string InOd) { 
    int len = InOd.length(); // 序列长度 if (len == 0) return; // 序列为空，表无子树 // 找根结点 int k; // 中序遍历中根结点的下标 char root; // 根结点 int minn = 1e8; // 最小值 for (int i = 0; i < len; i++) if (num[InOd[i]] < minn) { 
    k = i; // 更新根结点在的下标 root = InOd[i]; // 记录根结点 minn = num[InOd[i]]; // 记录最小值（找根结点核心） } // 输出先序遍历 cout << root; // 根结点 dfs(InOd.substr(0, k)); // 左子树 dfs(InOd.substr(k+1)); // 右子树 } int main() { 
    cin >> InOd >> LvOd; for (int i = 0; i < LvOd.length(); i++) num[LvOd[i]] = i; dfs(InOd); return 0; } 

2. 道路修改

题目描述

在 W 星球上有 $n$ 个国家。为了各自国家的经济发展，他们决定在各个国家之间建设双向道路使得国家之间连通。但是每个国家的国王都很吝啬，他们只愿意修建恰好 $n-1$ 条双向道路。
每条道路的修建都要付出一定的费用，这个费用等于道路长度乘以道路两端 的国家个数之差的绝对值。
由于国家的数量十分庞大，道路的建造方案有很多种，同时每种方案的修建费用难以用人工计算，国王们决定找人设计一个软件，对于给定的建造方案，计算出所需要的费用。请你帮助国王们设计一个这样的软件。

输入格式

输入的第一行包含一个整数 $n$，表示 $W$ 星球上的国家的数量，国家从 $1$ 到 $n$ 编号。
接下来 $n–1$ 行描述道路建设情况，其中第 $i$ 行包含三个整数 $a_i,b_i$ 和 $c_i$ ，表示第 $i$ 条双向道路修建在 $a_i$ 与 $b_i$ 两个国家之间，长度为 $c_i$。

输出格式

输出一个整数，表示修建所有道路所需要的总费用。

输入样例#1

6 1 2 1 1 3 1 1 4 2 6 3 1 5 2 1 

输出样例#1

20 

数据规模与约定

对于 $100\%$ 的数据，$1\le a_i,b_i\le n$，$0\le c\le 10^6$，$2\le n\le 10^5$。

我们可以将题目换一种说法：求从第 $1$ 个结点为根结点的总结点数。

#include <iostream> #include <vector> #include <cmath> using namespace std; int n; int a, b, c; int len[]; // 每个点到父结点的路径长度 int cnt[]; // 每个点为根的结点数 long long ans; struct Node { 
    vector<int> adj; // 邻结点数组 vector<int> w; // 和邻结点的长度差 } tree[]; // 计算以 id 为根子树的结点数 cnt[id] void dfs(int id, int father) { 
    cnt[id] = 1; // 自己本身 int len1 = tree[id].adj.size(); // 邻结点数组的长度 for (int i = 0; i < len1; i++) // 遍历 tree[id] 的所有邻结点 { 
    int son = tree[id].adj[i]; if (son == father) continue; // 碰到叶结点 len[son] = tree[id].w[i]; // 更新长度 dfs(son, id); cnt[id] += cnt[son]; // 增加结点数 } } int main() { 
    cin >> n; for (int i = 1; i < n; i++) { 
    cin >> a >> b >> c; tree[a].adj.push_back(b), tree[a].w.push_back(c); tree[b].adj.push_back(a), tree[b].w.push_back(c); } dfs(1, 0); for (int i = 2; i <= n; i++) ans += (long long)len[i]*abs(n-cnt[i]*2); cout << ans; return 0; } 

3. 最大子树和

题目描述

输入格式

第一行一个整数 $N$（$1\le N\le 16000$）。表示原始的那株花卉上共 $N$ 朵花。
第二行有 $N$ 个整数，第III个整数表示第III朵花的美丽指数。
接下来 $N-1$ 行每行两个整数 $a,b$，表示存在一条连接第 $a$ 朵花和第 $b$ 朵花的枝条。

输出格式

一个数，表示一系列“修剪”之后所能得到的”美丽指数”之和的最大值。保证绝对值不超过 。

输入样例1

7 -1 -1 -1 1 1 1 0 1 4 2 5 3 6 4 7 5 7 6 7 

输出样例1

3 

数据说明

对于 $100\%$ 的数据，有 $N\le 16000$。

#include <iostream> #include <vector> using namespace std; int n; int ans = 0xc0c0c0c0; struct Node { 
    vector<int> adj; int w; int max_w; // 以当前结点为根的子树的最大美丽指数 } tree[]; void dfs(int id, int father) { 
    tree[id].max_w = tree[id].w; for (int son : tree[id].adj) { 
    if (son == father) continue; dfs(son, id); if (tree[son].max_w > 0) tree[id].max_w += tree[son].max_w; } } int main() { 
    cin >> n; for (int i = 1; i <= n; i++) cin >> tree[i].w; for (int i = 1, u, v; i < n; i++) { 
    cin >> u >> v; tree[u].adj.push_back(v); tree[v].adj.push_back(u); } dfs(1, 0); for (int i = 1; i <= n; i++) ans = max(ans, tree[i].max_w); cout << ans; return 0; }