数据结构第六讲：树的基本概念

返回目录

§6 树和二叉树

§6.1 树

§6.1.1 树的定义

树包含若干（可以是零）个节点，当零个节点时，称为空树；非空树的定义为$T=(D,R)$，其中，$D$ 为树中节点的有限集合，关系$R$ 满足以下条件：

• 有且仅有一个节点$d_{0}\in D$，它对于关系$R$ 来说没有前驱节点，节点$d_{0}$ 称作树的根节点；
• 除根节点$d_{0}$ 外，$D$ 中的每个节点有且仅有一个前驱节点，但可以有多个后继节点；
• $D$ 中可以有多个终端节点。

§6.1.2 树的基本术语

• 节点的度：树中每个节点具有的子树数或者后继节点数称为该节点的度，注意与图的度数定义不同，这里的度不包括父节点；
• 树的度：树中所有节点的度的 最大值 称之为树的度，$m$ 次树的度为$m$；
• 分支节点（非终端节点）：度非零的节点，定义单分支节点、双分支节点……
• 叶子节点（叶节点，终端节点） ：度为零的节点；
• 孩子节点：一个节点的 后继节点；
• 双亲节点（或父亲节点）：一个节点称为其后继节点的双亲节点；
• 子孙节点：一个节点的子树中除该节点外的所有节点称之为该节点的子孙节点，注意与孩子节点的区别与联系；
• 祖先节点：从树根节点到达某个节点的路径上通过的除该节点外的所有节点称为该节点的祖先节点，注意与双亲节点节点的区别与联系；
• 兄弟节点：具有同一双亲的节点互相称之为兄弟节点；
• 节点层次：树具有一种层次结构，根节点为第一层（注意与实际常用的定义不同，不是第零层），其孩子节点为第二层，如此类推得到每个节点的层次；
• 树的高度：树中节点的最大层次称为树的高度或深度；
• 森林：零棵 或多棵互不相交的树的集合称为森林，所以光秃秃的沙漠也是森林。

§6.1.3 树的逻辑结构表示

• 树形表示法：和一般的图的表示一样，最常见最直观；
• 文氏图表示法：使用集合以及集合的包含关系描述树结构，每个节点包含其所有的子节点。
• 凹入表示法：按 DFS 序及节点深度，用线段的伸缩关系描述树结构，感觉没啥用。
• 括号表示法：对于每棵子树，其根节点写在括号的左边，除根节点之外的其余节点写在括号中并用逗号分隔。括号序代表了树的形态，可以用来判断树是否同构。

§6.1.4 树的性质

1. 树中的节点数等于所有节点的度数加一，即$n = \sum d_{u} + 1$；
2. 度为$m$ 的树的第$k$ 层至多有$m^{k-1}$ 个节点。
3. 当一棵$m$ 次树的第$k$ 层有$m^{k-1}$ 个节点时，称该层是满的，若一棵$m$ 次树的所有叶子节点在同一层，且每一层都是满的，称为满$m$ 次树。显然，满$m$ 次树是所有相同高度的$m$ 次树中节点总数最多的树。（另一种定义是所有叶子节点在同一层，除该层外其余每一层都是满的）
4. 高度为$h$ 的$m$ 次树至多有$\dfrac{m^{h}-1}{m-1}$ 个节点

§6.1.5 树的基本运算

查找、插入或删除、遍历。

§6.1.6 树的存储结构

• 双亲存储结构：顺序存储结构，在每个节点中附设一个伪指针指示其双亲节点的位置，树中节点可按任意顺序存放。方便查找双亲和祖先节点，不方便查找孩子；
• 孩子链存储结构：多重链表，每一个节点有多个 指针 域，其中每个指针指向一个子树的根节点，方便查找孩子，不方便查找父亲和祖先节点，并且当树的度较大时，十分耗费存储空间；
• 孩子兄弟链存储结构：为每个节点设计三个域：一个数据 元素 域，一个该节点的 第一个孩子节点指针 域，一个该节点的 下一个兄弟节点指针 域，方便查找孩子，不方便查找父亲。由于每个节点只有两个指针域，相较孩子链存储更节省空间。