树

1. 树的定义

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

当 $n = 0$ 时，称为 空树

对于任一棵 非空树 $(n > 0)$ ，它具备以下性质：

• 树中有一个称为 “根（Root）”的特殊结点，用 r 表示；

• 其余结点可分为 $m(m > 0)$ 个 互不相交的 有限集 $T_1,T_2, \cdots , T_m$ ，其中每个集合本身又是一棵树，称为原来树的“子树（SubTree）”

2. 树的一些基本术语

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, \cdots, n_k$ ， $n_i$ 是 $n_{i+1}$ 的父结点。路径所包含的个数为 路径的长度

8. 祖先结点（Ancestor）：沿 树根到某一结点路径 上的所有结点都是这个结点的祖先结点

9. 子孙结点（Descendant）：某一结点的 子树中所有结点 是这个结点的子孙结点

10. 结点的层次（Level）：规定 根结点在1层，其他任一结点的层数是其父结点层数加1

11. 树的深度（Depth）：树中所有结点中的 最大层次 是这棵树的深度

3. 树的表示

儿子 - 兄弟表示法