数据结构 树的存储和遍历

一、树的定义

树的定义
树型结构是⼀类重要的⾮线性数据结构。
• 有⼀个特殊的结点，称为根结点，根结点没有前驱结点。
• 除根结点外，其余结点被分成M个互不相交的集合T1 、T2 、...、Tm T，其中每⼀个集合⼜是⼀棵树，称这棵树为根节点的⼦树。
因此，树是递归定义的。

树的基本术语
• 结点的度：树中⼀个结点孩⼦的个数称为该结点的度。
• 树的度：树中结点最⼤的度数称为树的度。
• 树的⾼度（深度）：树中结点的最⼤层数称为树的⾼度（深度）。
• 路径：树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，路径⻓度为序列中边的个数。

有序树和⽆序树
• 有序树：结点的⼦树按照从左往右的顺序排列，不能更改。
• ⽆序树：结点的⼦树之间没有顺序，随意更改。
这个认知会在我们后续学习⼆叉树的时候⽤到，因为⼆叉树需要区分左右孩⼦。

有根树和⽆根树
• 有根树：树的根节点已知，是固定的。
• ⽆根树：树的根节点未知，谁都可以是根结点。
这个认知主要会影响我们对于树的存储。在存储树结构的时候，我们最重要的就是要存下逻辑关系。如果是⽆根树，⽗⼦关系不明确，此时我们需要把所有的情况都存下来。⽐如a和b之间有⼀条边，我们不仅要存a有⼀个孩⼦b，也要存b有⼀个孩⼦a。
甚⾄有的时候，在有根树的题⽬⾥，也要这样存储。

二、树的存储

孩⼦表⽰法：

孩⼦表⽰法是将每个结点的孩⼦信息存储下来。
如果是在⽆根树中，⽗⼦关系不明确，我们会将与该结点相连的所有的点都存储下来。

实现⽅式⼀：vector数组实现

案例：
题⽬描述：
给定⼀棵树，该树⼀共有n 个结点，编号分别是1 ∼ n 。
输⼊描述：
第⼀⾏⼀个整数n ，表⽰n 个结点。
接下来n − 1 ⾏，每⾏两个整数u, v ，表⽰u 和v 之间有⼀条边。vector是可变⻓数组，如果只涉及尾插，效率还是可以的。⽽树结构这种⼀对多的关系，正好可以利⽤尾插，把所有的关系全部存起来。

• 因此，可以创建⼀个⼤⼩为n + 1 的vector 数组edges[n + 1] 。
• 其中edges[i] ⾥⾯就保存着i 号结点所连接的结点。

#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
int n;
vector<int> edges[N]; // 存储树 
int main()
{
 cin >> n;
 for(int i = 1; i < n; i++)
 {
 int a, b; cin >> a >> b;
 // a 和 b 之间有⼀条边 
 edges[a].push_back(b);
 edges[b].push_back(a);
 }
 return 0;
}

实现⽅式⼆：链式前向星

链式前向星的本质就是⽤数组来模拟链表。

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
// 链式前向星 
int h[N], e[N * 2], ne[N * 2], id;
int n;
// 其实就是把 b 头插到 a 所在的链表后⾯ 
void add(int a, int b)
{
 id++;
 e[id] = b;
 ne[id] = h[a];
 h[a] = id;
}
int main()
{
 cin >> n;
 for(int i = 1; i < n; i++)
 {
 int a, b; cin >> a >> b;
 // a 和 b 之间有⼀条边 
 add(a, b); add(b, a);
 }
 return 0;
}

三、树的遍历

树的遍历就是不重不漏的将树中所有的点都扫描⼀遍。
在之前学过的线性结构中，遍历就很容易，直接从前往后扫描⼀遍即可。但是在树形结构中，如不
按照⼀定的规则遍历，就会漏掉或者重复遍历⼀些结点。因此，在树形结构中，要按照⼀定规则去遍历。常⽤的遍历⽅式有两种，⼀种是深度优先遍历，另⼀种是宽度优先遍历。

深度优先遍历-DFS

（⽤ppt展⽰，效果更佳）
深度优先遍历，英⽂缩写为DFS，全称是DepthFirstSearch，中⽂名是深度优先搜索，是⼀种⽤于遍历或搜索树或图的算法。所谓深度优先，就是说每次都尝试向更深的节点⾛，也就是⼀条路⾛到⿊。
具体流程：
1. 从根节点出发，依次遍历每⼀棵⼦树；
2. 遍历⼦树的时候，重复第⼀步。
因此，深度优先遍历是⼀种递归形式的遍历，可以⽤递归来实现。

案例：
题⽬描述：
给定⼀棵树，该树⼀共有n 个结点，编号分别是1~n 。
输⼊描述：
第⼀⾏⼀个整数n ，表⽰n 个结点。
接下来n − 1 ⾏，每⾏两个整数u, v ，表⽰u 和v 之间有⼀条边。

1、⽤vector数组存储

注：存储树结构的时候，会把相邻的所有结点都存下来，这样在扫描⼦树的时候会直接扫描到上⼀
层，这不是我们想要的结果。
因此，需要⼀个st 数组来标记，哪些结点已经访问过，接下来dfs 的时候，就不去遍历那些点

int n;
vector<int> edges[N]; // edges[i] 保存着 i 号结点相连的所有点 
bool st[N]; // 标记当前结点是否已经被遍历过 
// 当前遍历到 u 这棵⼦树 
void dfs1(int u)
{
 // 先访问该点 
 cout << u << " ";
 st[u] = true; // 标记该点已经被访问过 
 // 访问它的⼦树 
 for(auto v : edges[u])
 {
 if(!st[v]) dfs1(v); // 如果没有遍历过，再去遍历 
 }
}
// ⽤ vector 数组 
void test1()
{
 cin >> n;
 for(int i = 1; i <= n - 1; i++)
 {
 int a, b; cin >> a >> b; // 读⼊⼀条边 
 edges[a].push_back(b); // 保存 a -> b 的⼀条边 
 edges[b].push_back(a); // 保存 b -> a 的⼀条边 
 }
 dfs1(1);
}

2、链式向前星存储

int n;
int h[N], e[N * 2], ne[N * 2], id;
bool st[N]; // 标记当前结点是否已经被遍历过 
void add(int a, int b)
{
 id++;
 e[id] = b; // 搞⼀个格⼦，存 b 
 // 把 b 头插在 a 这个链表的后⾯ 
 ne[id] = h[a];
 h[a] = id;
}
// 当前遍历到 u 这棵⼦树 
void dfs2(int u)
{
 cout << u << " ";
 st[u] = true;
 for(int i = h[u]; i; i = ne[i])
 {
 int v = e[i];
 if(!st[v]) dfs2(v);
 }
}
// ⽤数组模拟链表 
void test2()
{
 cin >> n;
 for(int i = 1; i <= n - 1; i++)
 {
 int a, b; cin >> a >> b;
 add(a, b); add(b, a);
 }
 dfs2(1);
}

宽度优先遍历-BFS

宽度优先遍历，英⽂缩写为BFS，全称是BreadthFirstSearch，也叫⼴度优先遍历。也是⼀种⽤于遍历或搜索树或图的算法。所谓宽度优先。就是每次都尝试访问同⼀层的节点。如果同⼀层都访问完了，再访问下⼀层。
算法过程可以看做是在树和图中，在起点放上⼀个细菌，每秒向周围的那些⼲净的位置扩散⼀层，直到把所有位置都感染。

具体实现⽅式：借助队列。
1. 初始化⼀个队列；
2. 根节点⼊队，同时标记该节点已经⼊队；
3. 当队列不为空时，拿出队头元素，访问，然后将队头元素的所有孩⼦⼊队，同时打上标记；
4. 重复3 过程，直到队列为空。

用vector实现：

int n;
vector<int> edges[N]; // edges[i] 保存着 i 号结点相连的所有点 
bool st[N]; // 标记哪些点已经⼊过队了 
void bfs1()
{
 queue<int> q;
 q.push(1);
 st[1] = true;
 while(q.size())
 {
 auto u = q.front(); q.pop();
 cout << u << " ";
 // 让孩⼦⼊队 
 for(auto v : edges[u])//把这点的孩子全部加入进来
 {
 if(!st[v])
 {
 q.push(v);
 st[v] = true;
 }
 }
 }
}
// ⽤ vector 数组 
void test1()
{
 cin >> n;
 for(int i = 1; i <= n - 1; i++)
 {
 int a, b; cin >> a >> b; // 读⼊⼀条边 
 edges[a].push_back(b); // 保存 a -> b 的⼀条边 
 edges[b].push_back(a); // 保存 b -> a 的⼀条边 
 }
 bfs1();
}

链式向前星存储：

int n;
int h[N], e[N * 2], ne[N * 2], id;
bool st[N]; // 标记哪些点已经⼊过队了 
void add(int a, int b)
{
 id++;
 e[id] = b; // 搞⼀个格⼦，存 b 
 // 把 b 头插在 a 这个链表的后⾯ 
 ne[id] = h[a];
 h[a] = id;
}
void bfs2()
{
 queue<int> q;
 q.push(1);
 st[1] = true;
 while(q.size())
 {
 auto u = q.front(); q.pop();
 cout << u << " ";
 for(int i = h[u]; i; i = ne[i])
 {
 int v = e[i];
 if(!st[v])
 {
 q.push(v);
 st[v] = true;
 }
 }
 }
}
// ⽤数组模拟链表 
void test2()
{
 cin >> n;
 for(int i = 1; i <= n - 1; i++)
 {
 int a, b; cin >> a >> b;
 add(a, b); 
 add(b, a);
 }
 bfs2();
}