树基础

树形结构

图论中的树和现实生活中的树长得一样，只不过我们习惯于处理问题的时候把树根放到上方来考虑。这种数据结构看起来像是一个倒挂的树，因此得名。
一个没有固定根结点的树称为 无根树（unrooted tree）。无根树有几种等价的形式化定义：

• 有 N 个结点，N-1 条边的连通无向图
• 无向无环的连通图
• 任意两个结点之间有且仅有一条简单路径的无向图
• 任何边均为桥的连通图
• 没有圈，且在任意不同两点间添加一条边之后所得图含唯一的一个圈的图

在无根树的基础上，指定一个结点称为 根，则形成一棵 有根树（rooted tree）。有根树在很多时候仍以无向图表示，只是规定了结点之间的上下级关系。

有关树的定义

适用于无根树和有根树

• 森林（forest）：每个连通分量（连通块）都是树的图。按照定义，一棵树也可以是森林。

PS：并查集是典型的森林结构

• 生成树（spanning tree）：一个连通无向图的生成子图，同时要求是树。也即在图的边集中选择 n-1条，将所有顶点连通。
• 无根树的叶结点（leaf node）：度数不超过 1 的结点。

PS：为什么不是1？因为当N=1是，其度数为0

• 有根树的叶结点（leaf node）：没有子结点的结点。

  只适用于有根树

• 父亲（parent node）：对于除根以外的每个结点，定义为从该结点到根路径上的第二个结点。 根结点没有父结点。

• 祖先（ancestor）：一个结点到根结点的路径上，除了它本身外的结点。 根结点的祖先集合为空。
• 子结点（child node）：如果 u 是 v 的父亲，那么 v 是 u 的子结点。
  子结点的顺序一般不加以区分，二叉树是一个例外。
• 结点的深度（depth）：到根结点的路径上的边数。
• 树的高度（height）：所有结点的深度的最大值。
• 兄弟（sibling）：同一个父亲的多个子结点互为兄弟。
• 后代（descendant）：子结点和子结点的后代。
  或者理解成：如果 u 是 v 的祖先，那么 v 是 u 的后代。

• 子树（subtree）：删掉与父亲相连的边后，该结点所在的子图。

特殊的树

• 链（chain/path graph）：满足与任一结点相连的边不超过 条的树称为链。
• 菊花/星星（star）：满足存在 u 使得所有除 u 以外结点均与 u 相连的树称为菊花。
• 有根二叉树（rooted binary tree）：每个结点最多只有两个儿子（子结点）的有根树称为二叉树。常常对两个子结点的顺序加以区分，分别称之为左子结点和右子结点。
  大多数情况下，二叉树 一词均指有根二叉树。
• 完整二叉树（full/proper binary tree）：每个结点的子结点数量均为 0 或者 2 的二叉树。换言之，每个结点或者是树叶，或者左右子树均非空。

• 完全二叉树（complete binary tree）：只有最下面两层结点的度数可以小于 2，且最下面一层的结点都集中在该层最左边的连续位置上。

• 完美二叉树（perfect binary tree）：所有叶结点的深度均相同的二叉树称为完美二叉树。