第7章 树和森林
树形结构是一类重要的非线性结构。树形结构的特点是结点之间具有层次关系。本章介绍树的定义、存储结构、树的遍历方法、树和森林与二叉树之间的转换以及树的应用等内容。
重点提示：
●树的存储结构
●树的遍历
●树和森林与二叉树之间的转换
7-1 重点难点指导
7-1-1 相关术语
1．树的定义：树是n（n>=0）个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：①有且仅有一个特定的称为根的结点；②其余的结点可分为m（m>=0）个互不相交的子集T1，T2，…，Tm，其中每个子集本身又是一棵树，并称为根的子树。
要点：树是一种递归的数据结构。
2．结点的度：一个结点拥有的子树数称为该结点的度。
3．树的度：一棵树的度指该树中结点的最大度数。如图7-1所示的树为3度树。
4．分支结点：度大于0的结点为分支结点或非终端结点。如结点a、b、c、d。
5．叶子结点：度为0的结点为叶子结点或终端结点。如e、f、g、h、i。
6．结点的层数：树是一种层次结构，根结点为第一层，根结点的孩子结点为第二层，…依次类推，可得到每一结点的层次。
7．兄弟结点：具有同一父亲的结点为兄弟结点。如b、c、d；e、f；h、i。
8．树的深度：树中结点的最大层数称为树的深度或高度。
9．有序树：若将树中每个结点的子树看成从左到右有次序的（即不能互换），则称该树为有序树，否则称为无序树。
10．森林：是m棵互不相交的树的集合。
7-1-2 树的存储结构
1．双亲链表表示法
以图7-1所示的树为例。
a
c
d
b
h
i
g
f
e
图7-1 一棵深度为3的树
（1）存储思想:因为树中每个元素的双亲是惟一的，因此对每个元素，将其值和一个指向双亲的指针parent构成一个元素的结点，再将这些结点存储在向量中。
（2）存储示意图:
0 1 2 3 4 5 6 7 8 9 MaxTreeSize-1
data: | a | b | c | d | e | f | g | h | i | … | ||
parent: | -1 | 0 | 0 | 0 | 1 | 1 | 2 | 3 | 3 | … | ||
（3）注意: Parrent域存储其双亲结点的存储下标，而不是存放结点值。
下面的存储是不正确的：
0 1 2 3 4 5 6 7 8 9 MaxTreeSize-1
data: | a | b | c | d | e | f | g | h | i | … | ||
parent: | -1 | a | a | a | b | b | c | d | d | … | ||
2．孩子链表表示法
（1）存储思想：
将每个数据元素的孩子拉成一个链表，链表的头指针与该元素的值存储为一个结点，树中各结点顺序存储起来，一般根结点的存储号为0。
（2）存储示意图:
2 ∧ ∧
1 ∧ ∧
data firstchild child next0 | A | 3 ∧ ∧ ∧ |
1 | B | 4 ∧ ∧ 5 ∧ ∧ ∧ |
2 | C | 6 ∧ ∧ ∧ |
3 | D | 7 ∧ ∧ 8 ∧ ∧ ∧ |
4 | E | ∧ |
5 | F | ∧ |
6 | G | ∧ |
7 | H | ∧ |
8 | I | ∧ |
图7-2 孩子链表存储示意图
（3）需注意的问题：
① 每个结点的孩子结点的child域存放该孩子的存储序号，而不是存放其结点的值。
② 孩子链表的最后一个结点的next域置入空指针。
③ 叶子结点的firstchild域也要置入空指针。
3．双亲-孩子兄弟链表表示法
将双亲表示和孩子兄弟链表表示法结合起来。
4．孩子兄弟链表表示法
（1）存储思想是：树中每个数据元素存储为一个结点，结点的结构如下：
leftmostchild | data | rightsilling |
其中：data为该数据元素的信息；
leftmostchild为该元素第一个孩子的指针；
rightsilling 为该元素右兄弟的指针。
（2）存储示意图:
a ∧
b
∧ g ∧
∧ f ∧
c
d ∧
∧ e
∧ i ∧
∧ h
图7-3 孩子-双亲链表存储示意图
7-1-3 树的基本运算
1．树的遍历
（1）先根遍历：若树T非空，则：
① 访问根结点R；
② 依次先根遍历根R的各个子树T1、T2、…、Tk先序中序后序遍历二叉树。
（2）后根遍历：若树T非空，则：
① 依次后根遍历根R的各个子树T1、T2、…、Tk；
② 访问根结点R。
2．森林的遍历
（1）前序遍历：若森林F非空，则
① 访问森林中第一棵树的根结点；
② 前序遍历第一棵树的根结点的子树；
③ 前序遍历去掉第一棵树后的子森林。
（2）中序遍历：若森林F非空，则
① 中序遍历第一棵树的根结点的子树；
② 访问森林中第一棵树的根结点；
③ 中序遍历去掉第一棵树后的子森林。
7-1-4 树、森林和二叉树的相互转换
1．树转换成为二叉树
要点：
（1）转换规则：
① 原树的根仍为转换后二叉树的根；
② 原树中每一个非终端结点的第一个孩子转换后成为其双亲的左孩子；
③ 原树中每一个结点右边的第一个兄弟孩子转换后成为它的右孩子。
（2）转换为二叉树后的特点：
① 所转换成的二叉树其根结点的右子树为空；
② 其二叉链表可解释为原树的孩子-兄弟链表。
2．森林转换为二叉树
要点：
转换规则：将森林中第二棵树的树根结点视为第一棵树树根的第一个兄弟，第三棵树的树根结点视为第二棵树树根的第一个兄弟，依次类推，仍按树的转换规则进行即可。
7-2 典型例题解析
7-2-1 选择题
1．以下说法错误的是（ ）。
A．存在这样的二叉树，对其采用任何次序的遍历其结点访问序列均相同。
B．二叉树是树的特殊情形。
C．由树转换成二叉树，其根结点的右子树总是空的。
D．在二叉树只有一棵子树的情况下，也要指出是左子树还是右子树。
【分析】二叉树的特点是仅有一个分支时也有左右之分，而树无此特点，也即二叉树不是树的特殊情形。
【答案】B
2．如果T＇是由有序树T转换而来的二叉树，那么T中结点的后序就是T＇中结点的（ ）。
A．先序 B．中序 C．后序 D．层次序
【分析】树的先序遍历序列与其转换的二叉树的先序遍历序列相同，树的后序遍历序列与其转换的二叉树的中序遍历序列相同。
【答案】B
3．若一个具有N个顶点，K条边的无向图是一个森林（N>K），则该森林中必有（ ）棵树。
A．K B．N C．N－K D．1
【分析】由于一棵有n个顶点的树具有n－1条边，故设森林中有m棵树，每棵树有vi个顶点（1≤i≤m），则有：
v1+v2+…+vm=N
(v1-1)+(v2-1)+…+(vm-1)=K
以上两式相减得：m=N-K。
【答案】C
4．设F是一个森林，B是由F变换得到的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（ ）个。
A．n-1 B．n C．n+1 D．n+2
【分析】通过一个简单的森林及其对应二叉树的实例即可确定答案。
【答案】C
7-2-2 判断题
1．由树转换成二叉树，根结点没有左子树。
【分析】由树转换成二叉树，根结点必有左子树而没有右子树。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论