跳转至

树基础

算法竞赛的树和现实生活中的树长得一样,只不过我们习惯于处理问题的时候把树根放到上方来考虑。

这种数据结构看起来像是一个倒挂的树,因此得名。

形式化的定义:

  • n 个节点, n-1 条边的连通无向图

  • 无向无环连通图

  • 任意两个节点之间有且仅有一条简单路径的无向图

有关树的定义

森林

每个连通分量(连通块)都是树的图

生成树

一个图的生成子图,同时要求是树。

有根树

指定了一个点是根的树

无根树

没有指定一个根节点的树

深度

节点的深度

到根节点的距离(最短路径的长度)

树的深度

所有节点的深度的最大值

父亲

一个节点到根节点的路径上的第二个节点

祖先

一个节点到根节点的路径上,除了它本身外的所有节点

子节点

如果 u v 的父亲,那么 v u 的子节点。

兄弟

同一个父亲的多个子节点互为兄弟

后代(子孙)

子节点和子节点的后代

或者理解成:如果 u v 的祖先,那么 v u 的后代。

度数

无根树

和一个点相关的边的个数

有根树

子节点个数

叶节点

无根树

度数不超过 1 的节点

为什么不是度为 1

考虑 n = 1 的时候。

有根树

没有子节点(度数为 0 )的节点

子树

删掉与父亲相连的边后,该节点所在的子图

特殊的树

只有一个节点

没有边

n = 1, m = 0

i 的父亲为 i - 1

树的深度为 n - i

菊花

所有非根节点的父亲均为根节点。

树的深度为 1

二叉树

每个节点最多只有两个儿子(子节点)的树

满二叉树

Full binary tree,每个节点度数为 0 或者 2。换言之,每个节点或者是树叶,或者左右子树均非空。

完全二叉树

Complete binary tree,只有最下面两层节点的度数可以小于 2,且最下面一层的节点都集中在该层最左边的连续位置上。

如何存树

存父亲

用一个数组记录每个节点的父亲节点:fa数组

邻接表

当成图来存

有根树:vector<int> childs[n], fa[n]

二叉树:int lch[n], rch[n], fa[n]


评论