树的学习

164天前 · OI · 10次阅读

其实树是一种特殊的图,他可以帮助我们解决很多问题,比如STL中的MAP就是用平衡树实现的,我们还可以用线段树实现RMQ等。

总之树的功能非常强大。

将树当作图看待时,他的特殊在于:

  • 图中有 n 个点和 n − 1 条边,且连通
  • 不存在环,任意两个点之间有且仅有一条简单路径
树(数据结构名词)_百度百科 (baidu.com)

eg:组织架构

现在我们有一个组织,创始人叫做“根”是组织的实际掌权者。

他有两个得力干将分别叫“左孩子”和“右孩子”。

左孩子和右孩子下面又各有两个孩子也叫“左孩子”和“右孩子”。

如果无法想象出来可以看图。

这就是一棵二叉树,因为他的每一个节点都是满的,所以称为完美二叉树(也叫满二叉树)。

那如果是这样一棵树呢?

这样的树被成为完全二叉树,他的节点排列和完美二叉树一样,但不是满的。

img

还有这样的二叉树,被成为完全二叉树,所有的节点的度都是2,说人话就是,如果你有孩子,那就必须为2个。

满二叉树和完全二叉树的定义可以看出, 满二叉树是完全二叉树的特殊形态, 即如果一棵二叉树是满二叉树, 则它必定是完全二叉树。

终于来到了题目环节:

今有一个 n 人团伙,除了老大(1 号)之外的每一个人都有个直接领导。当然,一个人的领导的领导也是他的领导。

给定这个组织的结构。接下来有 mm 组询问,每次询问给定 x,y ,问 x 是否为 y 的领导。

第一眼想到并查集?我们是来学习树的怎么能用并查集呢?

可以建一颗树,dfs/bfs遍历找x是否为y的祖先即可:

定义dad[x]记录x的父节点,询问是否为dad只需要dfs查询即可,这里选择dfs:

int ask(int x, int y)
{
    int cur = dad[y];//向上找dad
    while (cur != 0)//如果不是根节点如果没有dad了
    {
        if (cur == x)//如果找到了
            return true;
        cur = dad[cur];//没找到就继续向上
    }

    return false;//找到根了还是没有就返回false
}

eg:混乱的组织

今有一个 $n$ 人组织,除了老大(1 号)之外的每一个人都有个直接领导。当然,一个人的领导的领导也是他的领导。

不幸的是,你拿到的资料相比起上一题少一些——资料里只写了 $x$ 和 $y$ 之间存在直接上下级关系,而没写谁是领导、谁是打工的!

但你仍然要面对 $m$ 组询问,每次询问给定 $x, y$ ,问 $x$ 是否为 $y$ 的领导。

似乎和刚刚的不一样,不知道如何入手?

想一想,组织的老大我们是知道的,直接从根结点开始遍历即可完成。

我们先按照图的方式存储,从根节点遍历建树。

定义visit数组记录是否访问过,因为一开始是一个无向图。

void init(int x)
{
    vis[x] = true;
    for (int &p : e[x])
    {
        if (!vis[p])
        {
            dad[p] = x;
            init(p);
        }
    }
}

图的存储之前说过,e[x]什么意思便不提了。

总结:

树的存储方法比较多样。

  • dad 数组存储
  • 图存储

针对不同的题目,要选择效率较好的存储方法。

This post was written on 2022/8/19.
👍 0

none

最后修改于12天前

评论

贴吧 狗头 原神 小黄脸
收起

贴吧

  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡

狗头

  • 狗头
  • 狗头
  • 狗头
  • 狗头
  • 狗头
  • 狗头
  • 狗头
  • 狗头
  • 狗头
  • 狗头
  • 狗头
  • 狗头

原神

  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神

小黄脸

  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸

目录

avatar

only_matthew

人生如戏,戏如人生。

41

文章数

2

评论数

7

分类