树结构习题及答案.doc

第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】如图5-3所示得二叉树,试分别写出它得顺序表示与链接表示(二叉链表)。
解:
(1)顺序表示。
1
2
3
4
5
6
7
8
9
10
11
a
b
c
d
e
^
^
^
^
f
g
(2)该二叉树得二叉链表表示如图5-4所示。
a

b

c

d

∧

e

f

g

图5-4

∧

∧

∧

∧

∧

∧

∧

【例5-6】试找出满足下列条件得所有二叉树:
(1)先序序列与中序序列相同;
(2)中序序列与后序序列相同;
(3)先序序列与后序序列相同。
解:
(1)先序序列与中序序列相同得二叉树为:空树或者任一结点均无左孩子得非空二叉树;
(2)中序序列与后序序列相同得二叉树为:空树或者任一结点均无右孩子得非空二叉树;
(3)先序序列与后序序列相同得二叉树为:空树或仅有一个结点得二叉树。
b

a

c

d

e

f

图5-5

【例5-7】如图5-5所示得二叉树,要求:
(1)写出按先序、中序、后序遍历得到得结点序列。
(2)画出该二叉树得后序线索二叉树。
解:
(1) 先序遍历序列:ABDEFC
中序遍历序列:DEFBAC
后序遍历序列:FEDBCA
(2)其后序线索二叉树如图5-6所示。
NULL

c

a

b

d

e

f

图5-6

A

图5-7

B

C

D

E

F

G

H

I

K

L

M

J

【例5-8】将图5-7所示得树转换为二叉树。
解:第一步,加线。第二步,抹线。第三步,旋转。过程如图5-8所示。
A

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

B

C

D

E

F

G

H

I

K

L

M

J

A

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

B

C

D

E

F

G

H

I

K

L

M

J

A

B

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

C

F

D

K

G

E

L

H

M

I

J

A

B

C

D

E

F

H

I

J

图5-9

【例5-9】将如图5-9所示得二叉树转换为树。
解: 第一步,加线。第二步,抹线。第三步,调整。过程如图5-10所示。
A

B

D

H

C

F

E

J

I

B

A

C

D

E

F

H

I

J

第一步　　　　　　　　　第二步　　　　　　　　　第三步

B

A

C

D

E

F

H

I

J

图5-10

【例5-10】将如图5-11所示得森林转换成二叉树。
图5-11

C

D

E

F

G

A

B

H

I

L

J

K

解: 步骤略,结果如图5-12所示。
C

D

E

F

G

A

B

H

I

L

J

K

图5-12

【例5-11】假定用于通信得电文由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。
第一步:

25

5

4

7

9

12

30

8

(1)设计哈夫曼树得步骤如图5-13所示。
第四步:

25

7

9

12

30

8

15

5

4

9

18

第五步:

25

7

9

12

30

8

15

5

4

9

18

27

第六步:

25

30

9

5

4

9

18

7

12

8

15

27

43

第二步:

25

7

9

12

30

5

4

9

8

第三步:

25

7

9

12

30

5

4

9

8

15

第七步:

25

30

9

5

4

9

18

7

12

8

15

27

43

57

第八步:

25

9

5

4

9

18

43

30

7

12

8

15

27

57

100

图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
习题5
一、单项选择题
1、 在一棵度为3得树中,度为3得结点数为2个,度为2得结点数为1个,度为1得结点数为2个,则度为0得结点数为( 1、 C)个。
A、 4 B、 5 C、 6 D、 7
2、 假设在一棵二叉树中,双分支结点数为15,单分支结点数为30个,则叶子结点数为(2、 B )个。
A、 15 B、 16 C、 17 D、 47
3、 假定一棵三叉树得结点数为50,则它得最小高度为(3、 C )。
A、 3 B、 4 C、 5 D、 6
4、 在一棵二叉树上第4层得结点数最多为( 4、 D)。
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,所以二叉树就是一种特殊得树。 (1、×　)
2、 二叉树得前序遍历中,任意结点均处在其子女结点之前。 ( 2、√ )
3、 线索二叉树就是一种逻辑结构。 (　3、×)
4、 哈夫曼树得总结点个数(多于1时)不能为偶数。 (4、√)
5、 由二叉树得先序序列与后序序列可以唯一确定一颗二叉树。 (5、×)
6、 树得后序遍历与其对应得二叉树得后序遍历序列相同。 (6、√)
7、 根据任意一种遍历序列即可唯一确定对应得二叉树。 (7、√)
8、 满二叉树也就是完全二叉树。 (　8、√)
9、 哈夫曼树一定就是完全二叉树。 (9、×)
10、 树得子树就是无序得。 (10、×　)
三、填空题
1、 假定一棵树得广义表表示为A(B(E),C(F(H,I,J),G),D),则该树得度为_____,树得深度为_____,终端结点得个数为______,单分支结点得个数为______,双分支结点得个数为______,三分支结点得个数为_______,C结点得双亲结点为_______,其孩子结点为_______与_______结点。1、 3,4,6,1,1,2,A,F,G
2、 设F就是一个森林,B就是由F转换得到得二叉树,F中有n个非终端结点,则B中右指针域为空得结点有_______个。2、 n+1
3、 对于一个有n个结点得二叉树,当它为一棵________二叉树时具有最小高度,即为_______,当它为一棵单支树具有_______高度,即为_______。3、 完全,,最大,n
4、 由带权为3,9,6,2,5得5个叶子结点构成一棵哈夫曼树,则带权路径长度为___。4、 55
5、 在一棵二叉排序树上按_______遍历得到得结点序列就是一个有序序列。5、 中序
6、 对于一棵具有n个结点得二叉树,当进行链接存储时,其二叉链表中得指针域得总数为_______个,其中_______个用于链接孩子结点,_______个空闲着。6、 2n,n-1,n+1
7、 在一棵二叉树中,度为0得结点个数为n0,度为2得结点个数为n2,则n0=______。7、 n2+1
8、 一棵深度为k得满二叉树得结点总数为_______,一棵深度为k得完全二叉树得结点总数得最小值为_____,最大值为______。8、 2k-1,2k-1,2k-1
9、 由三个结点构成得二叉树,共有____种不同得形态。9、 5
10、 设高度为h得二叉树中只有度为0与度为2得结点,则此类二叉树中所包含得结点数至少为____。10、 2h-1
11、 一棵含有n个结点得k叉树,______形态达到最大深度,____形态达到最小深度。11、 单支树,完全二叉树
12、 对于一棵具有n个结点得二叉树,若一个结点得编号为i(1≤i≤n),则它得左孩子结点得编号为________,右孩子结点得编号为________,双亲结点得编号为________。12、 2i,2i+1,i/2(或ëi/2û)
13、 对于一棵具有n个结点得二叉树,采用二叉链表存储时,链表中指针域得总数为_________个,其中___________个用于链接孩子结点,_____________个空闲着。13、 2n,n-1,n+1
14、 哈夫曼树就是指________________________________________________得二叉树。14、 带权路径长度最小
15、 空树就是指_______________最小得树就是指_______________________。15、 结点数为0,只有一个根结点得树
16、 二叉树得链式存储结构有______________与_______________两种。16、 二叉链表,三叉链表
17、 三叉链表比二叉链表多一个指向______________得指针域。17、 双亲结点
18、 线索就是指___________________________________________。18、 指向结点前驱与后继信息得指针
19、 线索链表中得rtag域值为_____时,表示该结点无右孩子,此时______域为指向该结点后继线索得指针。19、 1,RChild
20、 本节中我们学习得树得存储结构有_____________、___________与___________。20、 孩子表示法,双亲表示法,长子兄弟表示法
四、应用题
1、 已知一棵树边得集合为{,,,,,,,,,,,,},请画出这棵树,并回答下列问题:
(1)哪个就是根结点？
(2)哪些就是叶子结点？
(3)哪个就是结点g得双亲？
(4)哪些就是结点g得祖先？
(5)哪些就是结点g得孩子？
(6)哪些就是结点e得孩子？
(7)哪些就是结点e得兄弟？哪些就是结点f得兄弟？
(8)结点b与n得层次号分别就是什么？
(9)树得深度就是多少？
(10)以结点c为根得子树深度就是多少？
1、 解答:
a

b

c

d

e

g

f

h

i

m

n

j

k

i

图5-15

根据给定得边确定得树如图5-15所示。
其中根结点为a;
叶子结点有:d、m、n、j、k、f、l;
c就是结点g得双亲;
a、c就是结点g得祖先;
j、k就是结点g得孩子;
m、n就是结点e得子孙;
e就是结点d得兄弟;
g、h就是结点f得兄弟;
结点b与n得层次号分别就是2与5;
树得深度为5。
4、 已知用一维数组存放得一棵完全二叉树:ABCDEFGHIJKL,写出该二叉树得先序、中序与后序遍历序列。
4、 解答:　
先序序列:ABDHIEJKCFLG
中序序列:HDIBJEKALFCG
后序序列:HIDJKEBLFGCA
6、 找出所有满足下列条件得二叉树:
(1)它们在先序遍历与中序遍历时,得到得遍历序列相同;
(2)它们在后序遍历与中序遍历时,得到得遍历序列相同;
(3)它们在先序遍历与后序遍历时,得到得遍历序列相同;
6、 解答:
(1)先序序列与中序序列相同得二叉树为:空树或者任一结点均无左孩子得非空二叉树;
(2)中序序列与后序序列相同得二叉树为:空树或者任一结点均无右孩子得非空二叉树;
(3)先序序列与后序序列相同得二叉树为:空树或仅有一个结点得二叉树。
7、 假设一棵二叉树得先序序列为EBADCFHGIKJ,中序序列为ABCDEFGHIJK,请写出该二叉树得后序遍历序列。
7、 解答:后序序列:ACDBGJKIHFE
8、 假设一棵二叉树得后序序列为DCEGBFHKJIA,中序序列为DCBGEAHFIJK,请写出该二叉树得后序遍历序列。
8、 解答:先序序列:ABCDGEIHFJK
9、 给出如图5-14所示得森林得先根、后根遍历结点序列,然后画出该森林对应得二叉树。
9、 解答:
先根遍历:ABCDEFGHIJKLMNO
后根遍历:BDEFCAHJIGKNOML
森林转换成二叉树如图5-16所示。
10.给定一组权值(5,9,11,2,7,16),试设计相应得哈夫曼树。
10、 解答:构造而成得哈夫曼树如图5-17所示。
A

B

D

E

F

C

G

H

J

I

K

N

O

M

L

图5-14