树和图的基本概念

图论是C++算法竞赛中很重要的一个算法，其中各种图论算法难度不小，所以往往是比赛重点，也是有必要掌握的部分。

接下来我将会介绍树和图的基本知识。

树和图的基本知识

树是一种特殊的图。想要了解树和图的概念，应当先了解图的基本信息。

为了辅助理解，在介绍前强烈推荐一个常用生成图网站——Graph Editor。他的输入是大部分图论题输入数据的输入方式——一条边表示为a b（两个端点）。
示例：

图的概念

图论中的图，可以理解为点与边的集合。

点是图论中最基本的单位，可能有点权，但这不影响任何图上算法。

边，在图论中用于连接两个点，当边权对应这条边的长度时，会直接对图上的搜索和其他算法产生影响。

度则是涉及点和边的一个概念——一个点的度数就是与该点相连的边的个数。

重边指的是两条边连接了同样的两点，图论的不少算法要对存在的重边在输入时就进行预处理（如在SPFA算法计算单源最短路时，重边需要通过取最小值简化为一条边避免错误）。

图上的环指的是几个点连接成一个环，可以通过一定的路径从自己走回自己。
自环则指的是只经过一条边的环，即自己只需要走一步就能走回自己，一条边的两端是同一个点。

简单图是一种特殊的图，没有重边、自环。假设其有$n$个点，易得边的数量最多$n(n - 1) / 2$条。

连通图是另一种图，图上的任意两点间都存在路径，相当于是一个大的连通分量。

树的概念

通用概念

树，作为一种特殊的图，还有一些性质。让我们先通过三张图区分什么是树，什么是普通的图。

这是树。

这也是刚刚的那棵树，只是换了个形态。

这不是树，因为比如以1为根节点，2和7的最近公共祖先是1（在他们的上面）但他们有连边。

所以，总结得出树是有$n$个点的无环连通图。多个树组成森林。

树的根节点没有父亲节点。树的叶子结点没有儿子节点。

所以，树除了根节点的每一个点都和其父亲有且仅有一条边，因为总共除了根节点有$n - 1$个点，那么就有$n - 1$条边。

每个节点的度就是与这个点存在直连边的子节点数量。

所有点的度数都$\le2$的树就是二叉树。同理，$\le k$的树就是$k$叉树。

两个点的最近公共祖先（LCA）就是两个点最近的公共祖先节点（父节点的父节点的父节点…）。

二叉树概念

在树中，我们重点研究二叉树。

满二叉树是指除了叶子结点，每个节点都度数都为$2$，顺次编号，一般根节点编号为$1$，左儿子就是$2$、右儿子是$3$。

完全二叉树是指指深度为$k$、有$n$个结点的二叉树，结点编号连续，其结点编号与相同深度的满二叉树对应位置一致。满二叉树是一种特殊的完全二叉树。

由上图得到满二叉树的规律：

对于结点$i$，
其左节点为$2i$，
右节点为$2i + 1$。