猫史档案馆

树的概念

 

 

树形结构的一种特殊的图，能够延伸出很多算法。

一棵树是由 n 个节点、n-1 条边形成的图，每条边连接两个点，没有一个点是独立出来的。

一棵树有一个根节点，从根节点开始搜索，每向下搜索一个节点，深度就加一。

一棵树有几个子节点。一个节点 x 的子树是指所有以 x 为某一级祖先的点和边的集合（自身也算）。

下面是一个例子：根节点是1号节点。

其中，节点 2 的子树包含节点 2,6,7,8,9。

 

 

 

树的存储

 

 

存储树的方法有很多，例如父亲表示法、喵表示法等。

这些表示法的缺陷是明显的。因为树是一种特殊的图，所以我们有更加通用的方法，也就是存储图的一般方法。

也就是链式前向星存图。

需要注意的是，建树的时候需要建双向边来存储无向图，因此数组需要开两倍大小。

//快速读入函数
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x*f;
}

#define N=100005;
int ver[N<<1],nxt[N<<1],head[N],tot,edge[N];
void add(int x,int y,int z)
{
    ver[++tot]=x,edge[tot]=z,nxt[tot]=head[x],head[x]=tot;
}

//搜索时
for(int i=head[x];i;i=nxt[i])
    int y=ver[x];

//主函数中
for(int i=1;i<=n;i++)
{
    int x=read(),y=read();
    add(x,y),add(y,x);
}

 

我们用一个例子体现这种存储方法的好处。

 

 

应用例子：树的先序遍历

（Luogu P1305）

 

先介绍一下树的三种遍历顺序。

1. 先序遍历：先根后左右

2. 中序遍历：先左中根后右

3. 后序遍历：先左右后根

 

注意一点，链式前向星后加的边先遍历。

因此我们存图的时候将左右子节点互换。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}
const int SIZE=100005;
int nxt[SIZE<<1],ver[SIZE<<1],head[SIZE<<1],tot;
inline void add(int x,int y)
{
    ver[++tot]=y,nxt[tot]=head[x],head[x]=tot;
}
int n,rt;
void dfs(int x,int fa)
{
    printf("%c",x+'A');
    for(int i=head[x];i;i=nxt[i])
    {
        int y=ver[i];
        if(y!=fa)dfs(y,x);
    }
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        char x,y,z;cin>>x>>y>>z;
        int f=x-'A',l=y-'A',r=z-'A';
        if(z!='*')add(f,r),add(r,f);
        if(y!='*')add(f,l),add(l,f);
        if(i==1)rt=f;
    }
    dfs(rt,0);
    return 0;
}

 

 

当然我们还需要求出树上一些其他信息。

 

 

 

树的搜索

求出节点深度、DFS序

 

 

通常对树进行深度优先搜索（DFS），也有些时候对树进行广度优先搜索（BFS）。

这里着重讲解DFS。

其中的边怎么弄就是链式前向星的基本操作了。

对于有无访问过节点，用参数 fa 判或者 vis 数组判都是可以的。

下面的代码实现了对一棵树执行深度优先搜索，求出每个节点的深度，同时记录了 DFS 序。

//a是DFS序,d是节点深度,s是子树大小
void dfs(int x)
{
    a[++m]=x,v[x]=1,s[x]=1;
    for(int i=head[x];i;i=next[i])
    {
        int y=ver[i];
        if(!v[y])
            d[y]=d[x]+1,dfs(y),s[x]+=s[y];
    }
    a[++m]=x;
}

 

至于BFS检索，我们可以使用一个队列。

1. 先将根节点入队；

2. 然后每次取出队头元素，将队头的所有子节点入队，同时求出相关信息；

3. 重复上述过程直到队列为空。

 

与深度优先搜索不同的是，广度优先搜索按照深度递增遍历，而DFS是按照子树顺序。

 

我们仍以一个例子感受搜索的应用。

 

 

应用例子：求出二叉树深度

（Luogu P4914）

 

使用链式前向星存储，然后DFS出每个节点深度，取最大值即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}
const int SIZE=100005;
int nxt[SIZE<<1],ver[SIZE<<1],head[SIZE<<1],tot;
inline void add(int x,int y)
{
    ver[++tot]=y,nxt[tot]=head[x],head[x]=tot;
}
int n,dep[SIZE],ans;
void dfs(int x,int fa)
{
    dep[x]=dep[fa]+1;
    for(int i=head[x];i;i=nxt[i])
    {
        int y=ver[i];
        if(y!=fa)dfs(y,x);
    }
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        int x=read(),y=read();
        if(x)add(i,x),add(x,i);
        if(y)add(i,y),add(y,i);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++)ans=max(ans,dep[i]);
    printf("%d\n",ans);
    return 0;
}

 

 

 

本期总结

 

 

这期教程，我们学习了树形结构的存储、检索，深度和DFS的求解及维护。

学会这期教程之后，你的树形结构内容就已经入门了，或许也有了解决 CSP-J 中树上问题的能力。

当然，树的内容远不止这些。下期我们学习树的重心及若干模型。

本期教程是以下教程计划的内容：

https://shequ.codemao.cn/community/380955

 

大家也可以前往我的 Luogu 博客学习：246979.blog.luogu.org