01 树与树的表示

01-树与树的表示

定义

树（Tree）：\(n(n\geqslant 0)\) 个结点构成的有限集合

• \(n=0\) 时的树称为空树

对任何一棵非空树 \((n\gt 0)\)，具备以下性质：

• 树中有一个结点叫做根结点（Root），用 r 表示
• 其余节点可以分为 \(m(m\gt0)\) 个互不相交的有限集 \(T_1,T_2,\ldots,T_m\)，其中每个集合本身又是一棵树，称为原来树的子树（SubTree）

辨别树与图

如何确定是一棵树而不是一个图：

• 子树是不相交的
• 除了根节点以外，每个节点有且仅有一个父节点
• 一棵 \(N\) 个结点的树有 \(\textit{\textbf{N-1}}\) 条边

树的基本术语

1. 结点的度（Degree）：结点的子树个数
2. 树的度：所有结点的最大的度数
3. 叶结点（Leaf）：度为 0 的结点
4. 父节点（Parent）：有子树的结点是其子树根节点的父节点
5. 子节点/孩子结点（Child）：若 A 结点是 B 结点的父节点，则 B 结点是 A 结点的子节点
6. 兄弟节点（Sibling）：具有同一父节点的各节点彼此是兄弟节点
7. 路径和路径长度：从结点 \(n_1\) 到 \(n_k\) 的路径为一个结点序列 \(n_1, n_2, \ldots, n_k\) ， \(n_i\) 是 \(n_{i+1}\) 的父结点。路径所包含的个数为路径的长度。
8. 祖先结点 (Ancestor)：沿树根到某一结点路径上的所有结点都是这个结点的祖先结点。
9. 子孙结点 (Descendant)：某一结点的子树中的所有结点是这个结点的子孙。
10. 结点的层次（Level）：规定根结点在 1 层，其它任一结点的层数是其父结点的层数加 1。
11. 树的深度（Depth）：树中所有结点中的最大层次是这棵树的深度。
12. 结点的高度（Height）：从距离该结点最远的叶结点的层次与该结点层次之差。

表示方法

儿子-兄弟表示法

每个结点存储结点元素、左子节点、下一个兄弟节点。

对于下面这个图：

使用儿子-兄弟表示法之后会是这样：

而在顺时针旋转 \(45\degree\) 以后，会得到一个二叉树：

二叉树结点表示形式：

二叉树是十分重要的一种树。其用途之一就是可以通过上述儿子-兄弟表示法来表示所有的树。它还有很多的用途。