苏州网站开发建设方法大连网站建设意动科技
一、树的概念
1.1 树的定义
1）树型结构（一对多）是⼀类重要的非线性数据结构
2 ）有⼀个特殊的结点，称为根结点，根结点没有前驱结点
3）除了根节点外 ， 其余结点被分成 M（M > 0) 个互不相交的集合 T1 , T2.....Tm , 其中每个集合 Ti ( 1 <= i <= m) 又是一棵结构与树类似的子树 。 每棵子树的根节点有且只有一个前驱 ， 可以有 0 个 或者多个后继 。 因此 ， 树是递归定义的。
1.2 树的基本术语
- 结点的度 ： 一个结点有几个孩子 --> 度就有多少
- 树的度 ： 一棵树中 ， 最大的结点的度称为树的度
- 父结点 / 双亲结点 ： 若一个结点含有子节点 ， 则这个结点称为其子节点的父结点
- 子节点 / 孩子结点 : 一个结点含有的子树的根结点称为该结点的子节点
- 叶子结点 / 终端结点 ： 度为 0 的结点称为叶节点
- 分支结点 / 非终端结点： 度不为0的结点
- 兄弟结点 ： 具有相同父结点 相互成为兄弟结点 （ 亲兄弟 )
- 结点的层次 : 从根开始定义起 ， 根为 第一层 ， 根的子结点为第二层 ，依次类推
- 树的高度 或 深度 ： 树中结点的最大层次
- 路径 : 一条从树中任意结点出发 ， 沿父结点 --> 子结点 连接 ，达到任意结点 的序列
树的概念与结构-CSDN博客
1.3 有序树和无序树
1）有序树：结点的子树按照从左往右的顺序排列，不能更改。2）无序树：结点的子树之间没有顺序，随意更改。这个认知会在我们后续学习二叉树的时候用到，因为二叉树需要区分左右孩子在算法竞赛中 ， 遇到的基本上都是无序树 ， 也就是说 ， 不需要考虑孩子结点的顺序
在有序树的视角中 ， 上面两棵树 不相同 ；
但是在无序树的视角中 ， 上面两棵树是相同的 。
1.4 有根树和无根树
1）有根树： 树的根节点已知，是固定的。2）无根树：树的根节点未知，谁都可以是根结点
在有根树的视角中 ， 根结点为 : A
在无根树的视角中 ：
无根树会导致父子关系不明确 ， 在存储时候需要注意 。 在算法竞赛中 ， 一般遇到的树一般都是无根树 ， 即使有根树 ， 也会存在父子关系未知的情况 。
二、树的存储
1）树结构相对线性结构来说就比较复杂 。存储时，既要保存值域，也要保存结点与结点之间的关系。2）实际中树有很多种存储方式：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。
2.1 孩子表示法
1） 对于每一个结点，只存储所有孩子的信息。
注意：如果在无根树之中 ， 如何知道谁是孩子 ？ 谁是父亲呢？
----> 管他三七二十一 ！！！直接把相连的结点都存储起来！！！ 都给我存！起！来！
2.2 实现方式一：用vector数组实现
在算法中 ， 一般会给出树结构都是有编号的 ， 以简化我们的操作
上面的题目，虽然告知了根结点是 1 ， 但是其他的结点之间的关系还是未知的 ， 所以我们还是需要当成无序树来处理 。
1） 创建一个大小足够的 vector 数组 ：vector<int> edges[10];
2) 对于 i 的孩子 ， 直接 edges[i] .push_back 进去即可 。
#include <iostream>
#include <cstdio>
#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;edges[a].push_back(b);edges[b].push_back(a); }return 0;
}2.3 实现方式二：链式前向星
本质上就是用 链表存储 所有孩子 ， 其中链表是用数组模拟实现的 。
#include <iostream>
#include <cstdio>
#include <vector>
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;add(a,b);add(b,a);}return 0;
}2.4 总结
1）前者由于用到了容器 vector，实际运行起来相比较于后者更耗时，因为 vector 是动态实现的。2）但是在如今的算法竞赛中，⼀般不会无聊到卡这种常数时间。也就是 vector 虽然慢，但不会因此而超时。
三、树的遍历
树的遍历就是不重不漏的将树中所有的点都扫描一遍在之前学过的线性结构中，遍历就很容易，直接从前往后扫描⼀遍即可。但是在树形结构中， 如果不按照⼀定的规则遍历，就会漏掉或者重复遍历⼀些结点 。因此，在树形结构中，要按照⼀定规则去遍历。常用的遍历方式有两种，一种是深度优先遍历，另一种是宽度优先遍历。注意 ！！！树的遍历是许多关于树的算法的知识 ， 一定要掌握啊！！！
3.1 深度优先遍历 -DFS
1）深度优先遍历（DFS -- Depth First Search） ， 是一种用于遍历 或 搜索树或图的算法 。
2）每次尝试向更深的结点走 --> 一条路走到黑 ！！！走到不能再走的时候 ， 返回 ， 继续走其他的路。
不撞南墙不回头！！！
因此 ， DFS 其实就是利用 递归的形式遍历 ， 可以用递归来实现 ！
3.1.1 用vector 数组存储
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;const int N = 1e5 + 10;
int n;
vector<int> edges[N];//存储图
bool st[N];//标记哪些点已经访问了
//方法一：vector 实现 void dfs(int u)
{cout << u << " ";st[u] = true;//说明当前这个点已经访问过了//访问所有的孩子 for(auto v:edges[u]){if(!st[v]){dfs(v);}}
}
int main()
{//建树cin >> n;for(int i = 1; i< n;i++){int a,b;cin >> a >> b;edges[a].push_back(b);edges[b].push_back(a); } //深度优先遍历dfs(1); return 0;
}
3.1.2 链式向前星存储
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;const int N = 1e5 +10;
int id,h[N],e[N*2],ne[N*2];
int n;
bool st[N];//标记哪些点已经访问过了void add(int a,int b)
{id++;e[id] = b;ne[id] = h[a];h[a] = id;
}void dfs(int u)
{cout << u << " ";st[u] = true;for(int i = h[u];i; i = ne[i]){int v = e[i]; // 孩子if(!st[v])dfs(v); }
}
int main()
{//建树 cin >> n;for(int i = 1;i<n ; i++){int a,b;cin >> a >> b;add(a,b);add(b,a);}//深度优先遍历dfs(1); return 0;
}
与使用vectoc 存储的打印结果不同 ， 因为vector 是尾插到数的后面 ， 但是链式前向星是头插。
时间复杂度 ：简单估计⼀下，在 dfs 的整个过程中，会把树中所有的边扫描量两遍。边的数量为 n − 1 ， 因此时间复杂度为 O(N) 。空间复杂度：最差情况下，结点个数为 n 的树，⾼度也是 n ，也就是变成⼀个链表。此时递归的深度也是 n ， 此时的空间复杂度为 O(N) 。
3.2 宽度优先遍历 - BFS
宽度优先遍历( BFS --- Breadth First Search)，也叫广度优先遍历。也是⼀种用于遍 或搜索树或图的算法。 所谓宽度优先。就是每次都尝试访问同⼀层的节点。 如果同⼀层都访问完了，再访问下一层。一层一层来
3.1.1 用vector 数组存储
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;const int N = 1e5 + 10;
bool st[N]; //标记哪一个点已经入队了
int n;
vector<int> edges[N]; void bfs()
{queue<int> q;q.push(1);st[1] = true;while(q.size()){int u = q.front() ;q.pop() ;cout << u << " ";for(auto v : edges[u]){if(!st[v]) {q.push(v);st[v] = true;}} }
}
int main()
{//建树 cin >> n;for(int i = 1 ;i< n ; i++){int a, b;cin >> a >> b;edges[a].push_back(b);edges[b].push_back(a); }//宽度优先遍历bfs(); return 0;
}
3.1.2 链式向前星存储
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;const int N = 1e5 +10;
bool st[N];
int id,e[N*2],ne[N*2],h[N];
int n;void add(int a,int b)
{id++;e[id] = b;ne[id] = h[a];h[a] = id;
}
void bfs()
{queue<int> q;q.push(1);st[1] = true;while(q.size() ){int 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; }}}
}
int main()
{cin >> n;//建树for(int i = 1;i<n;i++){int a,b;cin >> a >> b;add(a,b);add(b,a);} bfs();return 0;
}
时间复杂度： 所有结点只会入队一次，然后出队一次，因此时间复杂度为 O(N)空间复杂度： 最坏情况下，所有的非根结点都在同⼀层，此时队列里面最多有 n-1 个元素，空间复杂度为 O(N)