2024年6月2日发(作者：)
第7章 树和森林
树形结构是一类重要的非线性结构。树形结构的特点是结点之间具有层次关系。本章介
绍树的定义、存储结构、树的遍历方法、树和森林与二叉树之间的转换以及树的应用等内容。
重点提示：
树的存储结构
树的遍历
树和森林与二叉树之间的转换
7-1 重点难点指导
7-1-1 相关术语
1．树的定义：树是n（n>=0）个结点的有限集T，T为空时称为空树，否则它满足如下
两个条件：①有且仅有一个特定的称为根的结点；②其余的结点可分为m（m>=0）个互不相
交的子集T
1
，T
2
，…，T
m
，其中每个子集本身又是一棵树，并称为根的子树。
要点：树是一种递归的数据结构。
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所示的树为例。
e
a
b
f
c
g
h
d
i
图7-1 一棵深度为3的树
1
（1）存储思想:因为树中每个元素的双亲是惟一的，因此对每个元素，将其值和一个指
向双亲的指针parent构成一个元素的结点，再将这些结点存储在向量中。
（2）存储示意图:
0 1 2 3 4 5 6 7 8 9 MaxTreeSize-1
data:
parent:
a b
-1
0
c
0
d
0
e
1
f
1
g
2
h
3
i
3
…
…
（3）注意: Parrent域存储其双亲结点的存储下标，而不是存放结点值。
下面的存储是不正确的：
0 1 2 3 4 5 6 7 8 9 MaxTreeSize-1
data:
parent:
a
-1
b
a
c
a
d
a
e
b
f
b
g
c
h
d
i
d
…
…
2．孩子链表表示法
（1）存储思想：
将每个数据元素的孩子拉成一个链表，链表的头指针与该元素的值存储为一个结点，树
中各结点顺序存储起来，一般根结点的存储号为0。
（2）存储示意图:
data firstchild child next
0
1
2
3
4
5
6
7
8
A
B
C
D
E
F
G
H
I
∧
∧
∧
∧
∧
图7-2 孩子链表存储示意图
1
4
6
∧
7
2
5
∧
3
∧
8
∧
（3）需注意的问题：
① 每个结点的孩子结点的child域存放该孩子的存储序号，而不是存放其结点的值。
② 孩子链表的最后一个结点的next域置入空指针。
③ 叶子结点的firstchild域也要置入空指针。
3．双亲-孩子兄弟链表表示法
将双亲表示和孩子兄弟链表表示法结合起来。
4．孩子兄弟链表表示法
（1）存储思想是：树中每个数据元素存储为一个结点，结点的结构如下：
leftmostchild
其中：data为该数据元素的信息；
2
data rightsilling
leftmostchild为该元素第一个孩子的指针；
rightsilling 为该元素右兄弟的指针。
（2）存储示意图:
a
∧
d
∧
b
c
∧
g
∧
∧
h
∧
f
∧
∧
e
图7-3 孩子-双亲链表存储示意图
∧
i
∧
7-1-3 树的基本运算
1．树的遍历
（1）先根遍历：若树T非空，则：
① 访问根结点R；
② 依次先根遍历根R的各个子树T
1
、T
2
、…、T
k
。
（2）后根遍历：若树T非空，则：
① 依次后根遍历根R的各个子树T
1
、T
2
、…、T
k
；
② 访问根结点R。
2．森林的遍历
（1）前序遍历：若森林F非空，则
① 访问森林中第一棵树的根结点；
② 前序遍历第一棵树的根结点的子树；
③ 前序遍历去掉第一棵树后的子森林。
（2）中序遍历：若森林F非空，则
① 中序遍历第一棵树的根结点的子树；
② 访问森林中第一棵树的根结点；
③ 中序遍历去掉第一棵树后的子森林。
7-1-4 树、森林和二叉树的相互转换
1．树转换成为二叉树
要点：
（1）转换规则：
① 原树的根仍为转换后二叉树的根；
② 原树中每一个非终端结点的第一个孩子转换后成为其双亲的左孩子；
③ 原树中每一个结点右边的第一个兄弟孩子转换后成为它的右孩子。
（2）转换为二叉树后的特点：
① 所转换成的二叉树其根结点的右子树为空；
② 其二叉链表可解释为原树的孩子-兄弟链表。
3
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棵树，每棵树有v
i
个顶点（1≤i≤m），则有：
v
1
+v
2
+…+v
m
=N
(v
1
-1)+(v
2
-1)+…+(v
m
-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．由树转换成二叉树，根结点没有左子树。
【分析】由树转换成二叉树，根结点必有左子树而没有右子树。
4
【答案】错误
2．用树对应二叉树的前序遍历和中序遍历可以导出树的后根遍历序列。
【分析】因为后根遍历树和中序遍历与该树对应的二叉树结果相同。
【答案】正确
3．先根遍历一棵树和前序遍历与该树对应的二叉树，其结果不同。
【分析】先根遍历一棵树和前序遍历与该树对应的二叉树结果相同。
【答案】错误
4．前序遍历森林和前序遍历与该森林对应的二叉树，其结果不同。
【分析】前序遍历森林和前序遍历与该森林对应的二叉树结果相同。
【答案】错误
5．后序遍历树和中序遍历与该树对应的二叉树，其结果不同。
【分析】后序遍历树和中序遍历与该树对应的二叉树结果相同。
【答案】错误
7-2-3 填空题
1．树在计算机内的表示方式有： 、 、 。
【答案】双亲表示法；孩子表示法；孩子兄弟表示法
2．设F是由T
1
、T
2
、T
3
三棵树组成的森林，与F对应的二叉树为B。已知T
1
、T
2
、T
3
的结点数分别为n
1
、n
2
和n
3
，则二叉树B的左子树中有 个结点，二叉树B的右子树
中有 个结点。
【分析】根据森林转换为二叉树的方法知，根和左子树为森林的第一棵树，而其余的树
都在根的右子树上。
【答案】n
1
-1；n
2
+n
3
3．树和二叉树的主要差别是： 、 、 。
【答案】树的叶结点数至少为1，而二叉树的结点数可以为0；树中结点最大度数没有
限制，而二叉树结点最大度数为2；树的结点无左、右之分，而二叉树结点有左、右之分。
4．将树转换成二叉树的目的是： 。
【答案】可采用二叉树的存储结构，并利用二叉树有关算法解决树的有关问题。
7-2-4 应用题
1．画出下图所示的森林经转换后所对应的二叉树，并指出在二叉链表中某结点所对应
的森林中结点为叶子结点的条件。
F J
A
C
B
D G
H
E
I
【解答】
5
在二叉链表中某结点所对应的森林中结点为叶子结点的条件是该结点在森林中既没有
孩子也没有右兄弟。
2．画出和下列已知序列对应的森林F：
森林的先序访问序列为：ABCDEFGHIJKL；森林的中序访问序列为：CBEFDGAJIKLH。
【解答】方法是先根据森林的先序序列和中序序列画出对应的二叉树，然后将二叉树转
换成森林。
该题目最后转换的森林为：
7-2-5 算法设计题
1．对以孩子－兄弟链表表示的树编写计算树的深度的算法。
【分析】
采用递归算法实现。
0 若树为空
树的深度＝
max（第一棵子树的深度＋1，兄弟子树的深度） 若树非空
存储表示定义为：
typedef struct TreeNode{
DataType data;
struct TreeNode *child,*nextsibling;
}NodeTtpe,*CSTree; // 孩子－兄弟链表类型定义
【算法】
int high(CSTree t){
int h1,h2;
if (t==NULL)
return 0; // 若树为空，返回0
else{
h1=high(t->child); // h1为t的第一棵子树的深度
h2=high(t->nextsibling); // h2为t的兄弟子树的深度
return max(h1+1,h2);
}
}
6
2．对以双亲链表表示的树编写计算树的深度的算法。
【分析】
从每一个结点开始，从下向上搜索至根结点，记录结点的层次数，其中的最大值就是树
的深度。存储表示定义为：
typedef struct{
DataType data;
int parent;
}NodeType; // 双亲链表的结点类型
【算法】
int high(NodeType t[],int n){
// 求有n个结点的树t的深度
int i,max,s,h;
maxh=0;
for (i=0;i if (t[i].parent==-1) h=1; else{ s=i; h=1; while (t[s].parent !=-1){ s=t[s].parent; h++; } } if (h>maxh) maxh=h; } return maxh; } 7-3 课后习题选解 1．一棵度为2的树与一棵二叉树有何区别？ 树与二叉树之间有何区别？ ① 二叉树是有序树，度为2的树是无序树， 二叉树的度不一定是2。 ② 二叉树是有序树，每个结点最多有两棵 子树，树是无序树，且每个结点可以有多棵子树。 2．对于如图所示的树，试给出： （1）双亲数组表示法示意图； （2）孩子链表表示法示意图； （3）孩子兄弟链表表示法示意图。 A B E J D C G H F I M N K （题2图） 7 3．画出下图所示的森林经转换后所对应的二叉树，并指出在二叉链表中某结点所对应 的森林中结点为叶子结点的条件。 （参考典型例题解析中的应用题1） A C B F E D G H （题4图） 4．将如图所示的二叉树转换成相应的森林。 5．在具有n（n>1）个结点的各棵树中，其中深度最小的那棵树的深度是多少？它共有 多少叶子和非叶子结点？其中深度最大的那棵树的深度是多少？它共有多少叶子和非叶子结 点？ 2；n-1；1；n；1；n-1 6．画出和下列已知序列对应的树T： 8 树的先根访问序列为：GFKDAIEBCHJ；树的后根访问序列为：DIAEKFCJHBG。 7．画出和下列已知序列对应的森林F： 森林的先序访问序列为：ABCDEFGHIJKL；森林的中序访问序列为：CBEFDGAJIKLH。 （参考典型例题解析中的应用题2） 8．对以孩子－兄弟链表表示的树编写计算树的深度的算法。 （参考典型例题解析中的算法设计题1） 9．对以孩子链表表示的树编写计算树的深度的算法。 【提示】采用递归算法实现。 1 若根结点没有子树 树的深度＝ max(所有子树的深度)＋1 若根结点有子树 #define MAXNODE …… //树中结点的最大个数 typedef struct ChildNode{ int childcode; struct ChildNode *nextchild; }ChildNode； // 孩子链表的表结点 typedef struct{ DataType data; struct ChildNode *firstchild; }NodeType; // 孩子链表的头结点 int high(NodeType t[MAXNODE],int j){ int h,max; ChildNode *p; if (t[j].firstchild==NULL) return 1; // 若根结点没有子树 else{ // 若根结点有子树 p=t[i].firstchild; max=high(t,p->data); p=p->nextchild; while (p){ h=high(t,p->data); if (h>max) max=h; p=p->nextchild; } return max+1; } 9 } 10．对以双亲链表表示的树编写计算树的深度的算法。 （参考典型例题解析中的算法设计题2） 10
发布评论