关于树
树，在二叉树中已经介绍过来，这里就不过多介绍了
有序树和无序树
• 有序树：结点的⼦树按照从左往右的顺序排列，不能更改。
• ⽆序树：结点的⼦树之间没有顺序，随意更改。
比如下面的这两颗树
从有序树的观点来看的话，B,C,D是有顺序的，顺序不一样，则这两颗树虽然孩子都是一样的，但是就属于不同的树
从无序树的观点来看，这两颗树只要根节点相同，管你顺序一不一样，都算作同一课树
在算法竞赛中，遇到的树基本上都是无序树
有根树和无根树
• 有根树：树的根节点已知，是固定的。
• ⽆根树：树的根节点未知，谁都可以是根结点。
在上面的两颗树当中，用有根树的观点来看的话，由于根是固定的，所以两颗树是不一样得，但是从无根树观点来看得话，因为谁都可以做根，所以这时候两颗树算是相同的树
在算法竞赛中，我们遇到的树一般都是无根树
树的孩子表示法
对于上面的孩子表示发起，只是关心孩子是谁，而不关心父亲是谁，但是这种表示方法，对于无根树来说，就不正确了，那我们如何来表示嘞？其实答案很简单，就把这个节点相连的节点全部表示出来
算法比赛中是如何给出树的结构的
虽然上面的图片告诉了1是根节点，但是对于2，5.......的节点，也不知到谁是根节点，谁不是根节点
用vector顺序表来是实现树的存储
在上面的图片中，我们创建一个vector数组，其中vector[i]就表示i号节点所链接的节点，在上面的上面的图片中，我们已经给出了比赛中给出的树的形式，所以用vector来实现的代码如下
#include<iostream>
#include<vector>
using namespace std;const int N=1e5+10;
vector<int> edge[N];int main()
{int n;cin>>n; //输入节点的个数 while(n--){int x,y;cin>>x>>y;edge[x].push_back(y);edge[y].push_back(x); } return 0;
}链式前向星
所谓链式前向星就是用链表的方式来实现树的存储
代码实现
#include <iostream>using namespace std;// 链式前向星
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;
} 这里e和ne数组里面的长度为什么是2*n嘞，因为就是如果有节点3-->4,你先要头插4，又有4-->3,你又要头插4，所以一个元素是被插了两遍
深度优先遍历（DFS）
深度优先遍历，简称DFS ，也就是Deepth First Search,就是一直往深处走，直到不能 走了在返回去找别的路，继续往深出走，之前我们用两种方式实现了树，这里的深度优先遍历也有两种实现方法
比如上面的树，以一条路的方式从A，再向B,在向E，再向J，J下面
顺序表的方式
bool st[N]; //用来标记已经访问过的，访问过的不打印
void DFS(int u)
{cout<<u<<" ";st[u]=true;for(auto v:edge[u]){if(st[v]==false)DFS(v); }
} 链式前向星的方式
bool st[N];
void DFS(int u)
{cout<<u<<" ";st[u]=true;for(int i=h[u];i;i=ne[i]){int x=e[i];if(st[x]==false)DFS(x); }
}
