提高级-算法总结--树1

· · 算法·理论

(｡･∀･)ﾉﾞ嗨飞竹小课堂第28课开课喽!
好好好，今天终于开始学tree了~

## 有诸多特点： - 每个不是根节点的节点都**有且仅有**一个父节点 - 一棵树有$n$个点$n$-$1$条边，且不会形成环 - 每条边表示两个及以上的点的关系 根节点：一个没有父节点的节点 ## 树的分类 - 无根树：可以从中任选一个点当根节点 - 有根树：固定一个点是根节点 ## 树的表示法: ### 父节点表示法： 用一个数组$da$，表示每个点的父节点是谁 ### 子节点表示法： 用$vector$记录当前点所有的子节点 和昨天的邻接表很像，所以我们用邻接表的方法实现 适用于自顶向下 ## 有关度 - 图的度：出度+入度 - 树的度：这个点的直接子节点 来了来了，来切水题喽！ [找根节点和子节点](https://gonoi.com.cn/problem/D1280) 诺，模板题~ 这道题我们先用两种方法中的其一记录父子关系，如果用的是父节点表示法，就得加一个$vis$，找出根节点，如果是子节点表示法，则要在输出时排序QWQ $code: 
#include<bits/stdc++.h>
using namespace std;
int da[100005];
int vis[1000005];
int n,m;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        da[y]=x;
        vis[x]++;
    }
    int maxn=-2e9,ans,ans2;
    for(int i=1;i<=n;i++)
    {
        if(da[i]==0) ans2=i;
        if(vis[i]>maxn)
        {
            maxn=vis[i];
            ans=i;
        }
    }
    cout<<ans2<<endl<<ans<<endl;
    for(int i=1;i<=n;i++)
    {
        if(da[i]==ans) cout<<i<<" ";
    }
    return 0;
}

二叉树深度
这道题让我们求的是二叉树的深度，我们可以先把左子节点和右子节点存在结构体里，然后dfs，往他的左右子节点下面延伸，在dfs过程中比大小，找到最深的step，code: 

#include<bits/stdc++.h>
using namespace std;
vector<int> op[1000005];
bool vis[1000005];
int n,m,maxn=-2e9;
void dfs(int x,int step)
{
    if(op[x][0]==0&&op[x][1]==0) maxn=max(maxn,step);
    if(op[x][0]!=0) dfs(op[x][0],step+1);
    if(op[x][1]!=0) dfs(op[x][1],step+1);
    return;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        op[i].push_back(x);
        op[i].push_back(y);
    }
    dfs(1,1);
    cout<<maxn;
    return 0;
}

或者说用飞竹带来的模板，这个模板可以处理大部分题目，且不仅适用于二叉树，还可以求深度，子树大小： 

void dfs(int x,int da)
{
    siz[x]=1;//子树大小，自己也算进去，所以一开始为1
        dep[x]=dep[da]+1;//每个点的深度，子节点深度=父节点深度+1
    for(int i=0;i<op[x].size();i++)//遍历所有子节点
    {
        int v=op[x][i];//代表i下一个去的节点
        if(v!=da)//判断有没有立马走回来，也就是重复走
        {
            dfs(v,x);//dfs
            siz[x]+=siz[v];
                        //在dfs后计算字数大小，子树大小等于自己的所有子节点的子树大小再+1
        }
    }
    return;
}
//这里判断有没有重复走是不用$vis$的，因为如果重复走，他只会走到自己的父节点，我们正好传了参，可以直接判断QWQ

我宣布，今天的树结束啦QWQ！

下课！

ヾ(￣▽￣)Bye~Bye~