内容发布更新时间 : 2024/12/28 8:16:00星期一 下面是文章的全部内容请认真阅读。

第5章树

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

A 解：

J。 （1）叶子结点有：B、D、F、G、H、I、

B C D E （2）非终端结点有：A、C、E。

（3）每个结点的度分别是：A的度为F 4，G C的度为H I 2，J E的度为3，其余结点的度为0。 （4）树的深度为3。 图5-1 【例5-2】一棵度为2的树与一棵二叉树有什么区别？ 解：度为2的树有两个分支，但分支没有左右之分；一棵二叉树也有两个分支，但有左右之分，左右子树的次序不能交换。 【例5-3】树与二叉树有什么区别？ 解：区别有两点： （1）二叉树的一个结点至多有两个子树，树则不然； （2）二叉树的一个结点的子树有左右之分，而树的子树没有次序。 【例5-4】分别画出具有3个结点的树和三个结点的二叉树的所有不同形态。 解：如图5-2(a)所示，具有3个结点的树有两种不同形态。 如图5-2(B)所示，具有3个结点的二叉树有以下五种不同形态。 【例5-5】如图5-3。 所示的二叉树，试分别写出它的顺序表示和链接表示（二叉链表）解： （1）顺序表示。图5-2(a) 8 1 2 3 4 5 6 7 9 10 11 a b c 图5-2(b) d e ^ ^ ^ ^ f g （2）该二叉树的二叉链表表示如图5-4所示。 a 【例5-6】试找出满足下列条件的所有二叉树： （1）先序序列和中序序列相同； b （2）中序序列和后序序列相同；∧ c ∧ （3）先序序列和后序序列相同。 解： e ∧ d ∧ （1）先序序列和中序序列相同的二叉树为：空树或者任一结点均无左孩子的非空二叉树； （2）中序序列和后序序列相同的二叉树为：空树或者任一结点均无右孩子的非空二叉树； ∧ f ∧ ∧ g ∧ （3）先序序列和后序序列相同的二叉树为：空树或仅有一个结点的二叉树。 图5-4

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

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

（2）画出该二叉树的后序线索二叉树。 c b 解：

（1） 先序遍历序列：ABDEFC d 中序遍历序列：DEFBAC

e 后序遍历序列：FEDBCA

f 图5-5

（2）其后序线索二叉树如图5-6所示。 【例5-8】将图5-7所示的树转换为二叉树。 a 解：第一步，加线。第二步，抹线。第三步，旋转。过程如图5-8所示。 A c b A A D E A B C B C E B C B d D E D G H I J F C D F G H F G H I J I J e E L M F K H K L M J L M I 图5-7 K f 图5-9 图5-8(b)第二步 抹线 图5-8(a)第一步 加线 A NULL 图5-6 【例5-9】将如图5-9所示的二叉树转换为树。 B 解：第一步，加线。第二步，抹线。第三步，调整。过程如图5-10所示。 C D A F A 【例5-10】将如图5-11所示的森林转换成二叉树。A E G B K B A C D H B D H 解：步骤略，结果如图5-12 C D D L 所示。C H L I H E B H C F I F J M A F E E E、F、 【例5-11】假定用于通信的电文由8个字符、D、各字母在电文中出现的概率为5％、 A、B、C G、 H组成， J J K J J I 9％、12％、30％、F C G I E I B 25％、4％、7％、8％，试为这8个字母设计哈夫曼编码。 图5-8(c)第三步 图5-11 ，4， 7，9，12，30，8） 旋转解：根据题意，设这8个字母对应的权值分别为（5，25，并且n=8。 第一步 第二步D 第三步 （1）设计哈夫曼树的步骤如图 5-13所示。 图H E 5-10 5 25 4 7 9 12 30 8 第一步： F 第二步： 25 7 9 12 30 8 I 9 第三步： 25 9 12 30 G 15 L 9 J 4 5 （2）设计哈夫曼编码 第七步： 7 8 43 4 5 57 K 利用第八步得到的哈夫曼树，规定左分支用0表示，右分支用1表示，字母A、B、C、D、E、F、G、H的

图5-12 27 30 18 25 哈夫曼编码如下表示： A:0011 B:01 C:0010 12 15 E:000 F:100 G:11 第四步： D:1010 9 9 H:1011 4 15 7 57 5 8 9 7 25 8 12 30 100 习题5 18 9 4 5 第八步： 一、单项选择题 43 1.在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为第五步： 18 25 18 30 25 27 27 30 0的结点数为（1.C）个。 15 15 D.7 9 9 A.4 9 B.5 9 12 C.612 2.假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（2.B）个。

7 4 5 7 8 8 4 5 A.15 B.16 C.17 D.47 3.假定一棵三叉树的结点数为50，则它的最小高度为（3.C）。

图5-13 30 27 43 第六步：

A.3 B.4 C.5 D.6 4.在一棵二叉树上第4层的结点数最多为（4.D）。 25 12 15 18 7

8

9

9

A.2 B.4 C.6 D.8

5.用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R[1..n]，结点R[i]若有左孩子，其左孩子的编号为结点（5.B）。

A.R[2i+1] B.R[2i] C.R[i/2] D.R[2i-1]

6.由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（6.D）。 A.24 B.48 C.72 D.53 7.线索二叉树是一种（7.C）结构。

A.逻辑 B.逻辑和存储 C.物理 D.线性 8.线索二叉树中，结点p没有左子树的充要条件是（8.B）。 A.p->lc=NULL B.p->ltag=1

C.p->ltag=1且p->lc=NULL D.以上都不对

9.设n,m为一棵二叉树上的两个结点，在中序遍历序列中n在m前的条件是（9.B）。 A.n在m右方 B.n在m左方 C.n是m的祖先 D.n是m的子孙 10.如果F是由有序树T转换而来的二叉树，那么T中结点的前序就是F中结点的（10.B）。 A.中序 B.前序 C.后序 D.层次序 11.欲实现任意二叉树的后序遍历的非递归算法而不必使用栈，最佳方案是二叉树采用（11.A）存储结构。 A.三叉链表 B.广义表 C.二叉链表 D.顺序 12.下面叙述正确的是（12.D）。 A.二叉树是特殊的树 B.二叉树等价于度为2的树 C.完全二叉树必为满二叉树 D.二叉树的左右子树有次序之分 13.任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序（13.A）。 A.不发生改变B.发生改变 C.不能确定 D.以上都不对 14.已知一棵完全二叉树的结点总数为9个，则最后一层的结点数为（14.B）。 A.1 B.2 C.3 D.4 15.根据先序序列ABDC和中序序列DBAC确定对应的二叉树，该二叉树（15.A）。 A.是完全二叉树 B.不是完全二叉树 C.是满二叉树 D.不是满二叉树 二、判断题 1.二叉树中每个结点的度不能超过2，所以二叉树是一种特殊的树。 2.二叉树的前序遍历中，任意结点均处在其子女结点之前。 3.线索二叉树是一种逻辑结构。 4.哈夫曼树的总结点个数（多于1时）不能为偶数。 5.由二叉树的先序序列和后序序列可以唯一确定一颗二叉树。 6.树的后序遍历与其对应的二叉树的后序遍历序列相同。 7.根据任意一种遍历序列即可唯一确定对应的二叉树。 8.满二叉树也是完全二叉树。 9.哈夫曼树一定是完全二叉树。 10.树的子树是无序的。 三、填空题

1.假定一棵树的广义表表示为A（B（E），C（F（H，I，J），G），D），则该树的度为_____，树的深度为_____，终端结点的个数为______，单分支结点的个数为______，双分支结点的个数为______，三分支结点的个数为_______，C结点的双亲结点为_______，其孩子结点为_______和_______结点。1.3，4，6，1，1，2，A，F，G

（1.× ） （2.√） （ 3.×） （4.√） （5.×） （6.√） （7.√） （ 8.√） （9.×） （10.× ）