由于太水，建议吃沙子的时候看
树
树的特性：节点=边数+1，一个点对多个点……
二叉树：树的一种类型，每个点的度不大于2。
1.先序遍历：以根左右的顺序进行遍历
1 2 4 5 3 6 7
2.中序遍历：以左根右的方式进行遍历
4 2 5 1 6 3 7
3.后序遍历：以左右根的方式进行遍历
4 5 2 6 7 3 1
1.通过先序、中序求后序
1 2 4 5 3 6 7
4 2 5 1 6 3 7
先序遍历中的第一个数是根节点，在中序遍历中找这个点，在这个点左边的是左子树，在右边的是右子树。425是左子树，然后在这里边找2，所以4是2的左子树，5是2的右子树。再看另一边，637是右子树，在里边找3，3左边的6是3的左子树，7是3的右子树。
2.通过后序、中序求先序
4 5 2 6 7 3 1
4 2 5 1 6 3 7
后序遍历最后一个点是根节点，在中序里找这个数，左边的是左子树，右边的是右子树，然后用上面的方法继续。
3.不能通过先序、后序求中序，这样求出来的答案是不唯一的。
满二叉树
每一个节点要么是一个叶子节点，要么是一个出度为2的节点。
且一定拥有(2^n)-1个节点，一定有log2(n+1)层。
完全二叉树
前n-1层是满二叉树，最后一层的节点集中在左侧。
二叉树问题
这道题是一道综合题，要用到深度，宽度，和两点之间的距离
这道题输入可以使用vector输入
cin>>n;
for(int i=2;i<=n;i++){
int x,y;
cin>>x>>y;
a[x].push_back(y);
a[y].push_back(x);
}
使用dfs求深度。
每到达一个点，就用ans取ans和这个点的深度的最大值。然后再前往这个点能到达的点。
void dfs(int x,int dep){
ans=max(ans,dep);
for(int i=0;i<a[x].size();i++)
if(!vis[a[x][i]]){
vis[a[x][i]]=1;
//标记点
dfs(a[x][i],dep+1);
}
}
使用dfs求宽度
每检测到一个点，就让w[dep]加一。并让ans取ans和w[dep]中的最大值。
void dfs1(int x,int dep){
for(int i=0;i<a[x].size();i++)
if((!vis[a[x][i]])){
w[dep]++;
//让该层的数量统计加一
ans=max(ans,w[dep]);
//取最大值
vis[a[x][i]]=1;
//标记点
dfs1(a[x][i],dep+1);
}
}
使用bfs求两点之间最短距离
像走迷宫一样搜索，只不过每个点的到达位置规定好了而已。
void bfs(){
queue<node> q;
q.push(node{s,0});
while(!q.empty()){
node now=q.front();
q.pop();
for(int i=0;i<a[now.x].size();i++){
if(a[now.x][i]==e){
cout<<now.step+1;
return;
}
if(!vis[a[now.x][i]]){
vis[a[now.x][i]]=1;
q.push(node{a[now.x][i],now.step+1});
}
}
}
}
//最后把他们的结果一次输出，别忘了初始化。