数据结构第5章 树

第5章 树

【例5-1】写出如图5-1所示的树的叶子结点、非终端结点、每个结点的度及树深度。

A

B C D E

F G H I J 图5-1 解：

（1）叶子结点有：B、D、F、G、H、I、J。 （2）非终端结点有：A、C、E。

（3）每个结点的度分别是：A的度为4，C的度为2，E的度为3，其余结点的度为0。 （4）树的深度为3。

【例5-2】一棵度为2的树与一棵二叉树有什么区别？

解：度为2的树有两个分支，但分支没有左右之分；一棵二叉树也有两个分支，但有左右之分，左右子树的次序不能交换。 【例5-3】树与二叉树有什么区别？

解：区别有两点：

（1）二叉树的一个结点至多有两个子树，树则不然；

（2）二叉树的一个结点的子树有左右之分，而树的子树没有次序。

【例5-4】分别画出具有3个结点的树和三个结点的二叉树的所有不同形态。

解：如图5-2(a)所示，具有3个结点的树有两种不同形态。

图5-2(a) 如图5-2(B)所示，具有3个结点的二叉树有以下五种不同形态。

图5-2(b)

【例5-5】在一棵度为M树中，度为1的结点数为N1，度为2的结点数为N2，……，度为M的结点数为NM，则该数中含有多少个叶子结点？有多少个非终端结点？

解：设度为0的结点（即终端结点）数目为n0，树中的分支数为B，树中总的结点数为N，则有：

（1）从结点的度考虑：

N= n0+ n1+ n2+……+nm

（2）从分支数目考虑：一棵树中只有一个根结点，其他的均为孩子结点，而孩子结点可以由分支数得到。所以有：

N=B+1=0×n0+1×n1+2×n2+…+m×nm+1 由以上两式，可得 n0+ n1+ n2+……+nm=0×n0+1×n1+2×n2+…+m×nm+1 从而可导出叶子结点的数目为：

n0=0×n1+1×n2+…+（m-1）×nm+1=1+i2(i1)nmi

从而可以得到非终端结点的数目为

N- n0= n1+ n2+……+nm=

ni1mi

【例5-6】一棵含有N个结点的K叉树，可能达到的最大深度和最小深度各为多少？

解：（1）当k叉树中只有一层的分支数为k，其它层的分支数均为1时，此时的树具有最大的高度，为：n-k+1。

（2）当该k叉树为完全k叉树时，其深度最小。参照二叉树的性质4可知，其深度为：

logkn+1。

【例5-7】证明任何一棵满二叉树T中的分支数B满足B=2(N0-1)（其中N0为叶子结点数）。 证明：

∵T为满二叉树

∴不存在度为1的结点

设该二叉树中总的结点数为n，度为2的结点总数为n2，分支数为B 则有n＝n0+ n2 ①

又∵除了根结点外，其余n-1个结点都有一个分支进入，即有n个结点的二叉树共有n-1条边

∴n=B+1 ② 由①、②两式，可得 B+1＝n0+ n2 ③ 又由二叉树的性质3可知 n2＝n0-1 ④

由③、④两式可知 B= n0+ n0-1-1=2(n0-1) 求证成立。

a 【例5-8】如图5-3所示的二叉树，试分别写出它的顺序表示

和链接表示（二叉链表）。 c b

e d 解：

g f （1）顺序表示。

1 2 3 4 5 6 7 8 9 图5-3

10 11 a b c d e ^ ^ ^ ^ f g （2）该二叉树的二叉链表表示如图5-4所示。

a b ∧ c ∧ e ∧ d ∧ ∧ f ∧ ∧ g ∧ 图5-4

【例5-9】试找出满足下列条件的所有二叉树：

（1）先序序列和中序序列相同； （2）中序序列和后序序列相同； （3）先序序列和后序序列相同。 解：

（1）先序序列和中序序列相同的二叉树为：空树或者任一结点均无左孩子的非空二叉树；

（2）中序序列和后序序列相同的二叉树为：空树或者任一结点均无右孩子的非空二叉树；

（3）先序序列和后序序列相同的二叉树为：空树或仅有一个结点的二叉树。

【例5-10】如图5-5所示的二叉树，要求：

a （1）写出按先序、中序、后序遍历得到的结点序列。

（2）画出该二叉树的后序线索二叉树。 c b 解： （1） 先序遍历序列：ABDEFC d 中序遍历序列：DEFBAC e 后序遍历序列：FEDBCA （2）其后序线索二叉树如图5-6所示。

f

图5-5

a b c

d

e

f NULL

图5-6

【例5-11】将图5-7所示的树转换为二叉树。 A B C D E F G H I J K L M 图5-7

解：第一步，加线。第二步，抹线。第三步，旋转。过程如图5-8所示。

A A

B C E B C D E D

F G H F G H I J I J

K K L M L M

图5-8(b) 第二步 抹线 图5-8(a) 第一步 加线

A

B C D F

E

K G

L H M I

A B C E

D H J F I

J

图5-8(c) 第三步 旋转

图5-9

【例5-12】将如图5-9所示的二叉树转换为树。

解： 第一步，加线。第二步，抹线。第三步，调整。过程如图5-10所示。

A A

B B D C D C F H F H E E

I J J I

第一步 第二步

图5-10

【例5-13】将如图5-11所示的森林转换成二叉树。 A C D

I B E J G F

图5-11

解： 步骤略，结果如图5-12所示。

A

C B

A B C E F I

D H J

第三步

H K L D

H E

F I

L G J

K

图5-12

【例5-14】假定用于通信的电文由8个字符A、B、C、D、E、F、G、H组成，各字母在电文中出现的概率为5％、25％、4％、7％、9％、12％、30％、8％，试为这8个字母设计哈夫曼编码。

解： 根据题意，设这8个字母对应的权值分别为（5，25，4，7，9，12，30，8），并且n=8。

（1）设计哈夫曼树的步骤如图5-13所示。

5 25 4 7 9 12 30 8 第一步：

第二步： 25 7 9 12 30 8 9

4 5

第三步： 15 9 25 9 12 30

7 8 4 5

43 第七步： 57

27 30 18 25

12 15 9 9

7 8 4 5

100 第八步：

43 57

18 30 25 27 15 9 9 12

8 4 5 7

图5-13

（2）设计哈夫曼编码

利用第八步得到的哈夫曼树，规定左分支用0表示，右分支用1表示，字母A、B、C、D、E、F、G、H的哈夫曼编码如下表示：

A:0011 B:01 C:0010 D:1010 E:000 F:100 G:11 H:1011 四、应用题

1. 已知一棵树边的集合为{，，，，，，，，，，，，}，请画出这棵树，并回答下列问题：

（1）哪个是根结点？ （2）哪些是叶子结点？ （3）哪个是结点g的双亲？ （4）哪些是结点g的祖先？ （5）哪些是结点g的孩子？

（6）哪些是结点e的孩子？

（7）哪些是结点e的兄弟？哪些是结点f的兄弟？ （8）结点b和n的层次号分别是什么？ （9）树的深度是多少？

（10）以结点c为根的子树深度是多少？ 1. 解答： 根据给定的边确定的树如图5-15所示。 a 其中根结点为a； c b 叶子结点有：d、m、n、j、k、f、l；

c是结点g的双亲；

g f h d e

a、c是结点g的祖先；

j、k是结点g的孩子； i i k j m、n是结点e的子孙；

m n e是结点d的兄弟；

g、h是结点f的兄弟；

图5-15

结点b和n的层次号分别是2和5； 树的深度为5。

5. 一棵深度为H的满k叉树有如下性质：第H层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树，如果按层次自上至下，从左到右顺序从1开始对全部结点编号，回答下列问题：

（1）各层的结点数目是多少？

（2）编号为n的结点的父结点如果存在，编号是多少？

（3）编号为n的结点的第i个孩子结点如果存在，编号是多少？

（4）编号为n的结点有右兄弟的条件是什么？其右兄弟的编号是多少？ 5. 解答： （1）第i层上的结点数目是mi-1。

（2）编号为n的结点的父结点如果存在，编号是((n-2)/m)+1。

（3）编号为n的结点的第i个孩子结点如果存在，编号是(n-1)*m+i+1。

（4）编号为n的结点有右兄弟的条件是(n-1)%m≠0。其右兄弟的编号是n+1。

9. 给出如图5-14所示的森林的先根、后根遍历结点序列，然后画出该森林对应的二叉树。

9. 解答： 先根遍历：ABCDEFGHIJKLMNO 后根遍历：BDEFCAHJIGKNOML 森林转换成二叉树如图5-16所示。

A G K L C I B H M D E

F

J

N

O

图5-14