树论入门(一)

树论入门(一)

0 说明

前备知识可看图论初步(一)

1 基本的树与树论

1.1 介绍

,又称为树状图,是一种数据结构,它是由n个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来很像一棵倒挂的树🎄,也就是说它是根朝上,而叶朝下的。请看图示。

1.2 树的元素

树有很多基本的元素,很多题目都可能会包含这些概念:

  • 结点的度(出度):结点的子树个数。
  • 树的度:树的所有结点的结点的度的最大值。
  • 根结点:树的起始节点。
  • 叶结点结点的度为0的结点。
  • 父结点有子树的结点是其子树根节点的父结点。
  • 子结点有子树的节点的子树的根节点是该有子树结点的子节点。
  • 兄弟结点:具有同一个父节点的各结点彼此是兄弟结点。
  • 树的深度:是BFS(从根节点一层一层的遍历)的总层数。也称树的高度。
  • 树的直径:指树上距离最远的两点间的距离。

1.3 树的性质

树也有许多的性质,可能会有用:

  1. 树是一个特殊的有向无环图。在这n个结点的图里有恰好n-1条边,且这n个结点都是联通的。
  2. 任意的两个结点连接之后形成一个
  3. 每棵子树的根节点有且仅有一个直接前驱,但可以有0或多个直接后继。

1.4 特殊的树(图)

当所有非叶结点的结点都只有一个子结点的时候,这棵树就变成了,变成了线性结构,可以直接用线性表的性质来做。

  • 菊花图

当树的深度为2且有若干个结点时,这棵树就变成了一个菊花图。菊花图中任意两个结点的距离都不会超过2.下图中的a为根结点,其他都为叶结点。

1.5 树的存储与遍历

由于树本质上就是一个特殊的图,所以可以用图的方法来存储和遍历树,但实际上操作会有些不同。有些特殊的有着不同写法,以后可能会介绍(立个flag)。

1.6 贪心-求树的直径

如何求树的直径,可以知道树的深度与树的直径不一定相等,所以不能通过求深度来得到直径,而是需要其他的方法。一种方法是用贪心来求树的直径。

具体操作是任意找一个结点为根结点,dfs整棵树找到距离它最远的结点x,然后再将结点x作为根结点,dfs整棵树找到距离它最远的结点y,则这两个结点的距离就为树的直径

如何说明正确性呢?看看下图。假设我们第一次选到了根结点a,离结点a最远的结点是结点d,e,a,任选一个结点d,将结点d作为根结点,离结点d最远的结点是结点e,a,而刚好就得到了树的直径。假设第一次选到的不是根结点a而是结点b,则把结点b看成根结点也是一样的效果。

下面给出实现的代码,用的是链式前向星⭐的存图方式,图带有边权。

  • 例1.6.1
int n,m,tot,p,ans;
int fa[maxn];    //存储父节点
int head[maxn],Next[maxn],v[maxn],w[maxn];

void add(int x,int y,int z)    //存图
{
    tot++;
    v[tot]=y;
    w[tot]=z;
    Next[tot]=head[x];
    head[x]=tot;
}

void dfs(int x,int fa)
{
    if (ans<f[x])    //找最远的结点的并记录
    {
        ans=f[x];
        p=x;
    }
    for (int i=head[x];i;i=Next[i])
    {
        int u=v[i];
        if (u==fa) continue;    //自己的子结点是自己,表示这是一个叶结点
        f[u]=f[x]+w[i];
        dfs(u,x);
    }
}

void find(int x)
{
    ans=0;
    f[x]=0;
    dfs(x,0);
}

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z); 
    }
    find(1);
    find(p);
    printf("%d",ans);
}

1.7 LCA-最近公共祖先

LCA,即最近公共祖先,是指在有根树中,找出两个结点x和y最近的公共祖先。

比如结点e和a的最近公共祖先为结点c,结点e和d的最近公共祖先为结点a。

如何求出两个结点x和y的最近公共祖先?这里只先介绍一种暴力的算法。

先让结点x和y跳到统一深度,保证两个结点最后在同一结点相遇。然后让两个结点往上爪巴,如果爪巴到同一个结点,说明是最近公共祖先。下面给出代码,用的是链式前向星⭐的存图方式。

  • 例1.7.1
int n,m,tot;
int deep[maxn],vis[maxn],head[maxn],f[maxn];

//deep记录结点深度,vis判断是否遍历过,head是指向结点的头的指针,f存储父亲结点

struct Node
{
    int v,next;
}e[maxn*2];    //双向建边乘2

void add_edge(int u,int v)
{
    e[tot].v=v;
    e[tot].next=head[u];
    head[u]=tot++;
}

void build_tree(int root,int depth)    //建树,当此前所站在的点有下一个连接的点的时候,depth+1,然后继续递归下一个点
{
    deep[root]=depth;
    vis[root]=1;
    for(int i=head[root];i!=-1;i=e[i].next)    
    {
        if(vis[e[i].v]!=0)    continue;
        f[e[i].v]=root;
        build_tree(e[i].v,depth+1);
    }
}

int LCA(int u,int v)    //暴力版的LCA
{
    while(deep[u]>deep[v])    u=f[u];//先保证u和v在同一深度
    while(deep[v]>deep[u])    v=f[v];

    while(u!=v)    //然后一起往上找祖先
    {
        u=f[u];
        v=f[v];
    }
    return u;    //返回去u,v都是一样的
}
int main()
{
    cin>>n>>m;
    memset(head,-1,sizeof(head));
    for(int i=1;i<n;i++)
    {
        int a,b,c;
        cin>>a>>b;
        add_edge(a,b);
        add_edge(b,a);
    }

    build_tree(1,1);    //从结点1开始建树
    
    for(int i=1;i<=m;i++)    //查询LCA
    {
        int x,y;
        cin>>x>>y;
        cout<<LCA(x,y)<<endl;
    }
    return 0;
}

暴力求解LCA的平均时间复杂度为$O(mlogn)$,最坏时间复杂度为$O(mn)$。显然这个效率是明显不够的,可以被卡。更快的算法会再以后提到。

2 二叉树

2.1 二叉树基本概念

二叉树是树的一个特例,其有许多独特的性质。二叉树中每个结点的结点的度小于等于2或者说树的度为2。下图就是一个例子(还是这个图)。

2.2 二叉树性质

二叉树的一个有两个子树的结点的两个子树分别称为左子树右子树。二叉树有一些性质分别是:

  1. 一颗非空二叉树的第i层上最多有$2^{i-1}$个结点
  2. 深度为k的二叉树最少有k个结点,最多有$2^k-1$个结点。
  3. 一棵高度为h,且有$2^h-1$个结点的二叉树称为满二叉树
  4. 一棵高度为h,有n个结点的二叉树,当且仅当其每一个结点都与高度为h的满二叉树中编号从1-n的结点一一对应,称为完全二叉树。满二叉树也是完全二叉树中的一种。
  5. 具有n个结点的完全二叉树的深度h为$log_2(n+1)$。
  6. 包含n个结点的二叉树最大高度为n,最小高度为$log_2(n+1)$。

下图是一个满二叉树

下面是一个完全二叉树,仔细对比就可以清楚了。

2.3 二叉树存储

二叉树有着与图不同的存储方法。

  • 顺序存储

顺序存储就是使用一维数组来存储一颗树。

对于完全二叉树,存储很简单,已知完全二叉树的高度h,直接开一个大小为$2^h-1$的一维数组。上图的完全二叉树在数组中是这样存储的,下标从$1 \sim 2^h-1$,数组内存储的数据为[1,2,3,4,5,6,7,8,9,10,0,0,0,0,0]。

对于一般的树,存储也是开一个大小为$2^h-1$的数组。把一般的树补成满二叉树,把其中补的结点在数组中对应的值赋为0即可。

那么用了这个存储方法,如何遍历?可以发现对于当前结点x,其在数组中存储的位置下标为i,位置i*2和i*2+1都是其子结点,那么直接用*2的方式便可以遍历整个二叉树。

顺序存储简单,易用。但是其内存消耗十分之大,是$O(2^n)$的级别,对于有些题目,会喜得MLE

  • 链式动态结构

如何节省内存开支?这里就需要使用动态结构了,即根据需要建立新的结点,然后将其组织成一棵树。首先先建立好一个数据结构。

//类似链表
struct node
{
    int key;
    node* lt,rt;

    node (int _key,node* _lt,node* rt_)    //构造
    {
        key=_key;
        lt=_lt;
        rt=_rt;
    }
};

node *root=new node(-1,null,null);    //建立一个根结点

然后是输入左右结点(每个题目具体情况都不同)

void add_node(int l,int r,node* fa)    //fa为父结点地址
{
    fa->lt->key=l;
    fa->rt->key=r;
}
  • 链式静态数组

还有一种做法就是用静态的数组来存储二叉树,与动态数据结构其实极其相似,只不过其访问效率比动态数据结构要高很多。因为数组下标就相当于编号。

struct node
{
    int key;
    int lt,rt;
}tree[maxn];

void add_node(int l,int r,int fa)    //fa为父结点的编号
{
    tree[fa].lt=l;
    tree[fa].rt=r;
}

2.4 二叉树层次遍历

二叉树的层次遍历比较简单,实质上就是图的BFS遍历。利用队列就可以完成。下面给出用静态数组存储方式的层次遍历。

bool pd[maxn]
queue<int> q;

int main()
{
    q.push(root);    //根结点编号
    while (!q.empty())
    {
        int x=q.front();
        cout<<tree[x].key;
        q.pop();
	
        if (!pd[tree[x].lt])
        {
             pd[tree[x].lt]=1;
             q.push(tree[x].lt);    //压入队列
        }
        if (!pd[tree[x].rt])
        {
             pd[tree[x].rt]=1;
             q.push(tree[x].rt);    //压入队列
        }
    }
}

2.5 二叉树的递归遍历

二叉树的递归遍历也叫DFS遍历,一共有三种,分别是先序遍历中序遍历后序遍历

  • 先序遍历:先遍历根结点,再遍历左子树,最后遍历右子树。
  • 中序遍历:先遍历根左子树,再遍历根结点,最后遍历右子树。
  • 后序遍历:先遍历左子树,再遍历右子树,最后遍历根结点。

2.6 二叉树递归遍历有关问题

现在有这样的一个问题:给出二叉树的先序遍历和中序遍历,求出其后序遍历。如何求解这个问题?这需要抓住根结点。

观察可以发现,根据先序遍历的特性,先序遍历中第一个出现的一定是根结点,然后我们查看中序遍历中根结点的位置,根据中序遍历的特性,可以判断根结点左边的就是根结点的左子树,右边的就是根结点的右子树,这样先输出左子树的根结点,再输出右子树的根结点,最后输出当前根结点,上述操作时递归进行的,请看代码。

  • 例2.6.1(求先序)
string fi,mi;

void build(int l1,int r1,int l2,int r2)
{
    for (int i=l2;i<=r2;i++)
        if (mi[i]==fi[l1])
        {
            //i-l2为左子树的长度
            build(l1+1,l1+i-l2,  l2,i-1);    //左子树
            build(l1+i-l2+1,r1,  i+1,r2);    //右子树
            cout<<fi[l1];    
            return;
        }
}

int main()
{
    cin>>mi;
    cin>>fi;
    int l=mi.size();
    build(0,l-1,0,l-1);
}
  • 例2.6.2(求后序)
string mi,af;

void build(int l1,int r1,int l2,int r2)
{
    for (int i=l2;i<=r2;i++)
        if (t[i]==s[r1])
        {
            //i-l2为左树的长度
            cout<<s[r1];
            build(l1,l1+(i-l2)-1,l2,i-1);    //左子树
            build(l1+(i-l2),r1-1,i+1,r2);    //右子树
            return;
        }
}

int main()
{
    cin>>mi;
    cin>>af;
    int l=s.size();
    build(0,l-1,0,l-1);
}

注意上面两段代码三个语句cout<<s[r1];,build(l1,l1+(i-l2)-1,l2,i-1);,build(l1+(i-l2),r1-1,i+1,r2);的顺序,这体现了这些遍历的特性。

前面给的都是求先序遍历和后序遍历的代码,为什么没有求中序遍历的代码?原因是给定先序遍历和后序遍历,中序遍历可能不只一种写法。例如下图的这几棵树,它们的先序遍历和后序遍历都是相同的,而它们的中序遍历却不同。
现在给出一个问题:给定先序遍历和中序遍历,输出中序遍历的数量。

08-06

可以观察得出,只有一个子结点的结点才会存在前序遍历和后序遍历相同的情况下有不同的中序遍历,所以将题目转化成找 只有一个子结点的结点个数。并且可以很容易的找出这类节点在前序后序中出现的规律。(前序中出现AB,后序中出现BA,则这个节点只有一个儿子)

每个这类节点有两种中序遍历(及儿子在左,儿子在右),根据乘法原理中序遍历数为$2^{\tt{这类节点数}}$。代码如下。

  • 例2.6.3(求后序)
int ans;
string fi,af;
int main()
{
    cin>>fi;
    cin>>af;

    int l=fi.size();
    for(int i=0;i<l;i++)
        for(int j=1;j<l;j++)
            if(fi[i]==af[j]&&fi[i+1]==af[j-1])    //满足只有一个子结点的结点
                ans++;
    cout<<(1<<ans);
    return 0;
}

2.7 表达式树

08-07

表达式树就是由带数字或者运算符的结点组成的二叉树,其性质就是二叉树的性质,由于二叉树的递归遍历有前序遍历,中序遍历和后序遍历,所以表达式也有前缀表达式,中缀表达式和后缀表达式之分。

对于上面的那棵表达式树。

前缀表达式是++a*bc*de。

中缀表达式是a+b*c+d*e,中序表达式是我们平常最常见的表达式。

后缀表达式是abc*+de*+,后缀表达式是计算机中最常用的表达式,因为便于计算机计算。


感谢浏览😝!

此文章可能会在后续更新,欢迎纠错。