树

基础

基础性质

  • 一对多的关系,一个父亲有多个孩子。
  • 层次性,递归定义。
  • 边数=点数-1
  • 树上两点之间路径唯一,不存在环。

一些术语

  • 深度:选定根节点后,这棵树有几层。
  • 节点的度:这个节点往外连了几条边。
  • 子节点,父节点,兄弟节点
  • 叶子节点:没有孩子的节点。

奇奇怪怪的等比数列求和公式:

S_n=\frac{a_1(1-q^n)}{1-q}

二叉树

定义:每个节点最多只有两个子节点的树

性质

  • 一棵二叉树的第i层最多有2^{i-1}个节点
  • 一棵k层二叉树的最大节点数:2^k-1

满二叉树的堆式存储:

堆式存储

可使用一个数组逐层存储
编号为i的两个子节点的编号分别为2i2i+1

树的存储

邻接矩阵

使用一个二维数组,a[u][v]表示节点u与节点v有没有边或者边权值

缺点:浪费空间,空间复杂度O(n^2)

邻接表

使用vector,每个节点都有一个vector记录它与哪些节点相连

代码实现:

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<int> G[N];
void addedge(int u,int v)
{
    G[u].push_back(v);
    G[v].push_back(u);
}

边权实现:
使用结构体

struct Edge
{
    int v,w;
};

链式前向星

使用一个动态数组(链表)进行存储,当然这种东西没有vector方便

树的遍历

先序遍历:根->左->右

中序遍历:左->根->右

后序遍历:左->右->根

image

先序遍历:

1 2 4 5 6 3

中序遍历:

4 2 6 5 1 3

后序遍历:

4 2 5 6 3 1

例题:FBI树

题目描述

我们可以把由“`0”和“1”组成的字符串分为三类:全“0”串称为B串,全“1”串称为I串,既含“0”又含“1”的串则称为F串。

FBI树是一种二叉树,它的结点类型也包括F结点,B结点和I结点三种。由一个长度为2^N的“0101”串S可以构造出一棵FBI树T,递归的构造方法如下:

  1. T的根结点为R,其类型与串S的类型相同;
  2. 若串S的长度大于1,将串S从中间分开,分为等长的左右子串S_1S_2;由左子串S_1构造R的左子树T_1,由右子串S_2构造R的右子树T_2

现在给定一个长度为2^N的“01”串,请用上述构造方法构造出一棵FBI树,并输出它的后序遍历序列。

输入格式

第一行是一个整数N(0≤N≤10),

第二行是一个长度为2^N的“01”串。

输出格式

一个字符串,即FBI树的后序遍历序列

代码:

#include <iostream>
#include <string>
#define DAD(x) (x>>1)
#define LF(x) ((x)<<1)
#define RT(x) (((x)<<1)+1)
using namespace std;
string s;
int n,maxn;

struct node{
    string s;
    char type;
}t[3000];

void make_tree(string s,int cur)
{
    t[cur].s=s;
    int len=s.length();
    if(len!=1)
    {
        string left(s,0,len/2);
        string right(s,len/2,len/2);
        make_tree(left,LF(cur));
        make_tree(right,RT(cur));
    }
    return;
}

char dfs(int cur)
{
    char a,b;
    if(t[cur].s.length()>1)
    {
        //cout<<cur<<endl;
        a=dfs(LF(cur));
        b=dfs(RT(cur));
        if(a!=b||a=='F'||b=='F') t[cur].type='F';
        if(a=='I'&&b=='I') t[cur].type='I';
        if(a=='B'&&b=='B') t[cur].type='B';
    }
    else
    {
        t[cur].type=t[cur].s=="0"?'B':'I';
    }
    printf("%c",t[cur].type);
    return t[cur].type;
}

int main()
{
    cin>>n>>s;
    maxn=1<<n;
    make_tree(s,1);
    dfs(1);
    return 0;
}

二叉排序树

中序遍历有序的二叉树,即满足左<根<右
代码:

#include <bits/stdc++.h>
//二叉排序树:左小于根小于右 
using namespace std;
const int N=1e5+10;
struct node{
    int val,lc,rc,w;
}T[N];
int n,cnt,a[N];
void ins(int o,int v){
    if(!T[o].val)//如果该节点没有定义 
    {
        T[o].val=v;//插入值 
        T[o].w++;//w表示相同的数的数量 
        return;
    }
    if(v<T[o].val)//如果该值小于该节点的值 
    {
        if(!T[o].lc) T[o].lc=++cnt;//若未定义左节点,则定义 
        ins(T[o].lc,v);//递归 
    }
    if(v>T[o].val)//同理 
    {
        if(!T[o].rc) T[o].rc=++cnt;
        ins(T[o].rc,v);
    }
}
void dfs(int o)
{
    if(!T[o].val)return;//如果遍历到未定义节点 ,返回 
    if(T[o].lc) dfs(T[o].lc);//如果已定义,则前往左节点继续递归 
    for(int i=1;i<=T[o].w;i++)//输出 
        printf("%d ",T[o].val);
    if(T[o].rc) dfs(T[o].rc); //再遍历右节点 
}
int main()
{
    scanf("%d",&n);
    cnt=1;
    for(int i=1;i<=n;i++) scanf("%d",a+i);//扫入数据 
    for(int i=1;i<=n;i++) ins(1,a[i]);//构建 二叉排序树 
    dfs(1);//开始遍历 
    return 0;
}

树的重心

定义:挑选某个节点作为树的根节点的话,两子树的大小会相对接近,这个节点就是树的重心

理解:某些树的根不是固定的(无根树)

性质

  • 树中所有点到某点的距离和中,到重心的距离和是最小的,如果树有两个重心,到他们的距离和一样
  • 把两个树通过某一点相连得到一棵新的树,则新的树的重心必然在连接原来两棵树的重心的路径上
  • 一棵树添加或者删除一个节点,树的重心最多只移动一条边的位置

求树的重心

思想:找出最大的子树最小的节点,就是重心

  • dfs一次,算出以每个点为根的子树大小
  • 记录以每个节点为根的最大子树的大小
  • 判断:如果以当前节点为根的最大子树大小比当前更优,更新当前根
  • 代码实现:
#include<bits/stdc++.h>
const int N=1000010;
const int inf=0x7f7f7f7f;
using namespace std;
int f[N],size[N],n;
//f[i]为以i为根时,最大子树的大小
//size[i]表示以i为根的子树大小
int rt,sum;
vector<int> G[N];//存边
void addedge(int u,int v)
{
    G[u].push_back(v);
    G[v].push_back(u);
}
inline void getrt(int u,int fa)
{
    size[u]=1;f[u]=0;//先将size赋初值1
    for(int i=0;i<G[u].size();i++)//开始遍历
    {
        int v=G[u][i];
         if(v==fa)
             continue;//如果遍历到的点是其父节点,忽略
        getrt(v,u);//继续递归查询
        size[u]+=size[v];//u节点的值加上以v节点为根的子树的大小
        f[u]=max(f[u],size[v]);//更新最大值
    }
    f[u]=max(f[u],sum-size[u]);//上面部分如果比下面部分还要大,更新
    if(f[u]<f[rt])rt=u;//如果子树大小的最大值比之前求出的重心的更小,则更新重心编号
}

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

int main()
{
    n=read();
    for(int i=1;i<n;i++){//扫入边
        int u=read(),v=read();
        addedge(u,v);
    }
    rt=0;sum=n;//rt表示树的重心,sum表示总结点数
    f[0]=inf;
    getrt(1,0);
    printf("%d\n",rt);
    return 0;
}

即:先假定1节点为根,然后递归自叶子节点开始求出各节点为根的子树大小,然后利用补集思想求出当该节点为整棵树的根时另一个子树的大小。当最大的子树大小最小时,说明这个节点是重心,更新

树的直径

定义:树上最长的一条树链。

求树的直径

法1 dfs

在一棵树上,对于一个点而言,离他最远的一个点一定是这棵树的直径的一个端点

第一遍dfs:找到直径的一个端点(就是从任意点出发,离它最远的点)

第二遍dfs:从一个端点开始,直接找到另一个端点

时间复杂度O(n)

代码实现:

#include<bits/stdc++.h>
const int N=1000010;
using namespace std;
int n,m,head[N],tot,dis[N],cur,mx;
//cur为直径的端点
//head数组存储以每个u为起点第一个相连的位置
//mx为最远距离max

inline int read(){
    int f=1,x=0;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
    do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
    return f*x;
}

struct Edge{
    int u,v,w,next;
}G[N<<1];

inline void addedge(int u,int v,int w){//前向星加边
    G[++tot].u=u;G[tot].v=v;G[tot].w=w;G[tot].next=head[u];head[u]=tot;
    G[++tot].u=v;G[tot].v=u;G[tot].w=w;G[tot].next=head[v];head[v]=tot;
}

inline void dfs(int u,int fa){
    for(int i=head[u];i;i=G[i].next)//链式前向星
    {
        int v=G[i].v;
         if(v==fa)//如果走回头路了
             continue;
        dis[v]=dis[u]+G[i].w;//更新距离
        if(dis[v]>mx)cur=v,mx=dis[v];//如果比目前的距离更长,更新最长值并更新端点cur
        dfs(v,u);//继续遍历
    }
}
int main(){
    n=read();
    for(int i=1;i<n;i++){
        int u=read(),v=read(),w=read();
        addedge(u,v,w);
    }
    dfs(1,0);
    mx=0;
    memset(dis,0,sizeof(dis));
    dfs(cur,0);
    printf("%d\n",mx); 
}

法2 dp

不会

树是一种特殊的无向连通图

定义

$G(V,E)$,由边和点组成的二元组

一些术语

  • 有/无向图:如果给图的每条边规定一个方向,那么得到的图称为有向图。在有向图中,与一个节点相关联的边有出边和入边之分。相反,边没有方向的图称为无向图。
  • 度:一个顶点的度是指与该顶点相关联的边的条数
  • 入度和出度:对于有向图来说,一个顶点的度可细分为入度和出度。一个顶点的入度是指与其关联的各边之中,以其为终点的边数;出度则是相对的概念,指以该顶点为起点的边数。
  • 自环:若一条边的两个顶点为同一顶点,则此边称作自环。

  • 点权,边权

  • DAG:有向无环图
  • 二分图:设G(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点ij分别属于这两个不同的顶点集(i \in A,j \in B),则称图G为一个二分图。判定:黑白染色法

树没有环

图的存储

类比树的存储

图的遍历

要建立一个vis数组,vis[i]表示该点有没有遍历过

因为可能会有回路出现而进入死循环

图的深度优先遍历实现:

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<int> G[N];
void addedge(int u,int v){
    G[u].push_back(v);
    G[v].push_back(u);
}
int vis[N];
void dfs(int u){
    vis[u]=1;
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(vis[v])continue;
        dfs(v);
    }
}

广度优先:

const int N=1e5+10;
vector<int> G[N];
int vis[N];
queue<int> q;
void bfs(int s)
{
    vis[s]=1;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=0;i<G[u].size();i++)
        {
            int v=G[u][i];
            if(vis[v]) continue;
            q.push(v);
            vis[v]=1;
        }
    }
}

例题:封锁阳光大学:

题目描述

曹是一只爱刷街的老曹,暑假期间,他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹,感到不爽。河蟹决定封锁阳光大学,不让曹刷街。

阳光大学的校园是一张由N个点构成的无向图,N个点之间由M条道路连接。每只河蟹可以对一个点进行封锁,当某个点被封锁后,与这个点相连的道路就被封锁了,曹就无法在与这些道路上刷街了。非常悲剧的一点是,河蟹是一种不和谐的生物,当两只河蟹封锁了相邻的两个点时,他们会发生冲突。

询问:最少需要多少只河蟹,可以封锁所有道路并且不发生冲突。

输入格式

第一行:两个整数N,M

接下来M行:每行两个整数A,B,表示点A到点B之间有道路相连。

输出格式

仅一行:如果河蟹无法封锁所有道路,则输出“Impossible”,否则输出一个整数,表示最少需要多少只河蟹。

思路分析

  1. 每一条边所连接的点中,至少要有一个被选中。
  2. 每一条边所连接的两个点,不能被同时选中。由此,可以推断出:

每一条边都有且仅有一个被它所连接的点被选中。

因此可以对每个连通图进行黑白染色

代码实现

//P1330
#include <cstdio>
#include <vector>
using namespace std;
const int N=1e5+10;
vector<int> G[N];
void addedge(int u,int v)
{
    G[u].push_back(v);
    G[v].push_back(u);
}

bool vis[N];
bool color[N];
int c[2];
int n,m;

bool dfs(int cur, bool col)
{
    if(vis[cur]){
        if(color[cur]==col)
            return true;
        else 
            return false;
    }
    vis[cur]=1;
    c[color[cur]=col]++;
    bool flag=1;
    for(int i=0;i<G[cur].size();i++)
    {
        int v=G[cur][i];
        flag=flag&&dfs(v,!col);
    }
    return flag;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        addedge(x,y);
    }
    int ans=0;
    for(int i=1;i<=n;i++)//从第一个点开始遍历处理连通图 
    {
        c[1]=c[0]=0;
        if(vis[i]) continue;//如果已处理,跳过
        if(!dfs(i,0))
        {
            puts("Impossible\n");
            return 0;
        }
        ans+=min(c[1],c[0]);
    }
    printf("%d\n",ans);
    return 0;
}

例题:信息传递:

题目描述

有 n 个同学(编号为 1 到 n)正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象,其中,编号为 i 的同学的信息传递对象是编号为T_i的同学。

游戏开始时,每人都只知道自己的生日。之后每一轮中,所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象(注意:可能有人可以从若干人那里获取信息, 但是每人只会把信息告诉一个人,即自己的信息传递对象)。当有人从别人口中得知自 己的生日时,游戏结束。请问该游戏一共可以进行几轮?

输入格式

共2行。

第1行包含1个正整数 n ,表示 n 个人。

第2行包含 n 个用空格隔开的正整数 T_1,T_2,\cdots\cdots,T_n,其中第 i 个整数T_i 表示编号为 i的同学的信息传递对象是编号为T_i的同学,T_i \leq nT_i \neq i

输出格式

1个整数,表示游戏一共可以进行多少轮。

思路分析

可以将其看作一个有向图,求其中的最小环

对每一个节点打一个时间戳,比较两次进入同一节点的时间戳之差即可。

代码实现

//P2661
#include <cstdio>
using namespace std;

int g[200050],t[200050];
int n;
int time,ans=1000000000;

inline void make_edge(int u,int v)
{
    g[u]=v;
}

inline void dfs(int cur)
{
    if(!g[cur]) return;
    time++;
    if(time>t[cur]&&t[cur]){
        ans=min(ans,time-t[cur]);
        t[cur]=0;
        g[cur]=0;
        return;
    }
    t[cur]=time;
    dfs(g[cur]);
    t[cur]=0;
    g[cur]=0;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int t;
        scanf("%d",&t);
        make_edge(i,t);
    }
    for(int i=1;i<=n;i++) dfs(i);
    printf("%d",ans);
    return 0;
}
最后修改日期: 2020年2月7日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。