【6.1】树的定义和基本术语

一、 树和森林

树 (tree) 是包括 n 个结点的有限集合 T(n ≥ 1):

• 有且仅有一个特定的结点，称为 根 (root)
• 除根以外的其他结点被分成 m 个 (m ≥ 0) 不相交的 有限集合 T1，T2，…，Tm，而每一个集合又都是树 ，称为 T 的子树 (subtree)
• 有向有序树:子树的相对次序是重要的
• 度为 2 的有序树并不是二叉树
• 第一子结点被删除后，第二子结点自然顶替成为第一

###1.1 树的逻辑结构

包含n个结点的有穷集合 K (n>0)，且在 K上 D 定义了一个关系 r，关系 r 满足以下条件:

• 有且仅有一个结点 k0∈K，它对于关系 r 来说没有 前驱。结点 k0 称作树的根
• 除结点 k0 外，K中的每个结点对于关系 r 来说都 有且仅有 一个前驱

例如，

结点集合 K={ A，B，C，D，E，F，G，H，I，J }

K 上的关系 r = { <A，B>，<A，C>，<B，D>，<B，E>，<B，F>，<C，G>，<C，H>，<E，I>，<E，J> }

1.2 树的相关术语

结点：

子结点、父结点、最左子结点 ：

若 <k，k′> ∈ r，则称 k 是 k′ 的父结点(或称“父母”) ，而 k′ 则是 k 的 子结点 (或“儿子”、“子女”)

兄弟结点前兄弟、后兄弟：

若有序对 <k，k′>及 <k，k′′>∈ r，则称 k′和 k′′互为兄弟

分支结点、叶结点：

• 没有子树的结点称作 叶结点(或树叶、终端结点)
• 非终端结点称为 分支结点

边

两个结点的有序对，称作 边

路径、路径长度

除结点k0外的任何结点 k∈K，都存在一个结点序列 k0，k1，…，ks，使得 k0 就是树根，且 ks=k，其 中有序对 $<ki-1，ki>∈ r (1≤i≤s)$ 。该序列称为从根 到结点 k 的一条路径，其路径长度为 s (包含的边数)

祖先、后代:

• 若有一条由 k 到达 ks 的路径，则称k 是 ks 的祖先，ks 是 k 的子孙

度数:

一个结点的子树的个数

层数:

根为第 0 层,其他结点的层数等于其父结点的层数加 1

深度:

层数最大的叶结点的层数

高度:

层数最大的叶结点的层数加 1

1.3 树形结构的各种表示法

• 树形表示法
• 形式语言表示法
• 文氏图表示法
• 凹入表表示法
• 嵌套括号表示法

树形表示法:

#### 形式语言表示法:

树的逻辑结构是:

结点集合K={A，B，C，D，E，F，G，H，I，J}
K上的关系N={<A，B>，<A，C>，<B，D>， <B，E>，<B，F>，<C，G>，
<C，H>，<E，I>，<E，J>}

文氏图表示法

嵌套括号表示法

(A(B(D)(E(I)(J))(F))(C(G)(H)))

文氏图到嵌套括号表示的转化

凹入表表示法

二、森林与二叉树的等价转换

森林(forest):零棵或多棵 不相交 的 树的集合(通常是有序)

树与森林的对应:

• 一棵树，删除树根，其子树就组成了森林
• 加入一个结点作为根，森林就转化成了一棵树

森林与二叉树之间可以相互转化，而 且这种转换是一一对应的

• 森林的相关操作都可以转换成对二叉树的操作

森林与二叉树如何对应?

森林转化成二叉树的形式定义

有序集合 F = {T1，T2，…，Tn} 是树 T1，T2，…，Tn 组成的森林，递归转换成二叉树B(F):

• 若F为空，即n=0，则B(F)为空
• 若 F 非空，即 n > 0，则 B(F) 的根是森林中第一棵树 T1 的根 W1，B(F) 的左子树是树 T1 中根结点 W1的子树森林 F = {T11，…，T1m} 转换成的二叉树B(T11，…，T1m); B(F)的右子树是从森林 F’ = {T2，…，Tn} 转换而成的二叉树

森林转化为二叉树

二叉树转化成森林或树的形式定义

设B是一棵二叉树，root是 B 的根，BL 是 root 的左子树，BR 是 root 的右子树， 则对应于二叉树B的森林或树 F(B) 的形式定义是:

• 若 B 为空，则 F(B) 是空的森林
• 若 B 不为空，则 F(B)是一棵树T1加上森林 F(BR)， 其中树 T1 的根为 root，root 的子树为 F(BL)

思考：

1. 树也是森林吗?
2. 为什么要建立二叉树与森林的对应关系?

三、树的抽象数据类型

四、树的遍历

森林的遍历

遍历森林vs遍历二叉树

• 先根次序遍历森林
• 前序法遍历二叉树
• 后根次序遍历森林
• 按中序法遍历对应的二叉树
• 中根遍历?
• 无法明确规定根在哪两个子结点之间

宽度优先遍历森林

宽度优先遍历

• 也称广度优先遍历
• 或称层次遍历

1. 首先依次访问层数为0的结点
2. 然后依次访问层数为1的结点
3. 直到访问完最下一层的所有结点

广度优先遍历森林

思考

1. 能否直接用二叉树前序遍历框架来编写森林的先根遍历?
2. 能否直接用二叉树中序遍历框架来编写森林的后根遍历?
3. 森林的非递归深搜框架?

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾