树基础知识

【注】参考自教材「算法导论」。

1. 自由树

1.1 定义

自由树是一个连通的、无环的无向图，简称树。

【注】一个可能不连通的、无环的无向图称为森林。

1.2 概念

• 结点的度：自由树中节点的度和无向图中的一样，即相邻结点的个数。

1.3 性质

• 令 $G = (V,E)$ 是一个无向图，则下面的描述是等价的：

1. $G$ 是自由树。
2. $G$ 中任何两结点由唯一简单路径相连。
3. $G$ 是连通的，但是从图中移除任意一条边得到的图均不连通。
4. $G$ 是连通的，且 $|E| = |V| - 1$ 。
5. $G$ 是无环的，且 $|E| = |V| - 1$ 。
6. $G$ 是无环的，但是如果向 $E$ 中添加任何一条边，均会造成图包含一个环。

2. 有根树 & 有/无序树

2.1 定义

• 有根树 是一个自由树，其结点中存在根结点（简称根）。

• 有序树 是一棵有根树，其中每个结点的孩子是有序的（即树中某结点的孩子之间的左右位置关系是有影响的）。

2.2 概念

• 祖先 & 后代：考虑以 $r$ 为根的有根树 $T$ 中的一个结点 $x$

1. 从 $r$ 到 $x$ 的唯一简单路径上任意结点 $y$ 称为 $x$ 的一个祖先。如果 $y$ 是 $x$ 的祖先，则 $x$ 是 $y$ 的后代。
2. 每个结点既是自己的祖先也是自己的后代。
3. 如果 $y$ 是 $x$ 的祖先且 $x \ne y$，则 $y$ 是 $x$ 的一个真祖先，且 $x$ 是 $y$ 的一个真后代。

• 双亲 & 孩子 & 兄弟：考虑从树 $T$ 的根 $r$ 到结点 $x$ 的简单路径上最后一条边为 $(y,x)$

1. $y$ 是 $x$ 的双亲，$x$ 是 $y$ 的孩子。
2. 如果两个结点有相同的双亲，则它们是兄弟。
3. 根结点是树中唯一没有双亲的结点。

• 叶结点 & 内部结点

1. 一个没有孩子的结点称为叶结点（或外部结点）。
2. 一个非叶结点称为内部结点。

• 结点的度：有根树中结点的度指结点孩子的个数，结点的双亲不包含在内（与自由树定义不同）。

• 树的度：树中最大的结点的度称为树的度。

• 结点的深度：从根 $r$ 到结点 $x$ 的一条简单路径的长度即为结点 $x$ 在 $T$ 的深度。根的深度为 0 。

• 结点的高度：从该结点到以其为根结点的子树中的叶结点最长的一条简单路径上边的数目。所有叶结点的高度为 0 。

• 树的深度/高度：等于树中最大的结点深度/最大的结点高度。树的深度 = 树的高度。

• 内部路径长度：所有内部结点深度之和。

• 外部路径长度：所有叶结点深度之和。

3. 二叉树 & 位置树

【注】二叉树的相关定义可以引申到 k 叉树。

3.1 定义

• 二叉树 $T$ 是定义在有限结点集上的结构，它或者不包含任何结点，或者包含三个不相交的结点集合：

1. 一个根结点。
2. 一棵称为左子树的二叉树。
3. 一棵称为右子树的二叉树。

• 位置树 是指树中结点的孩子被标记为不同的正整数的树。如果没有孩子被标记为整数 $i$ ，则该结点的第 $i$ 个孩子缺失。

3.2 概念

• 空树 & 零树：不包含任何结点的二叉树，有时使用符号 $NIL$ 表示。

• 左孩子 & 右孩子：如果左/右子树非空，则它的根称为整棵树的根的左/右孩子。

• 满二叉树：每个结点是叶结点或度为 2 的二叉树是满二叉树（即满二叉树没有度为 1 的结点）。

• 完全二叉树：在一颗二叉树中，若除最后一层外的其余层都是满的，并且最后一层要么是满的，要么在右边缺少连续若干节点，则此二叉树为完全二叉树。

• 完美二叉树：所有叶结点深度相同，且所有内部结点度为 2 的二叉树。

• 平衡二叉树（AVL 树）：任何结点的两棵子树的高度差不大于 1 的二叉树。

3.3 性质

• 二叉树是一棵位置树，其中对于每个结点，所有标记大于 2 的孩子均缺失。

• 任何非空二叉树中 2 度结点数比叶结点数少 1 。

推论

1. 叶结点数为 l 的满二叉树的结点元素个数为 $n = 2l - 1$ 。
2. 结点元素个数为 $n$ 的完美二叉树的叶结点个数 $l = {(n+1) \over 2}$，非叶结点个数为 $n - l = l - 1 = {(n+1) \over 2} - 1$ 。

• 一个有 $n$ 个结点的非空二叉树的高度至少为 $\lfloor \lg n \rfloor$ 。

• 一个高度为 $h$ 的满二叉树，其结点元素个数 $n$ 满足 $ 2h + 1 \leq n \leq 2^{h+1} - 1$ 。