数据结构课后习题(第6章)

2024年2月13日发(作者：阳光怎么形容)

楚雄师院计科系 网络工程2010级 《算法与数据结构》课后习题（第6章）

【课后习题】第6章 树和二叉树

网络工程2010级（ ）班

学号： 姓名：

题 号

得 分

一

二

三

四

五

总分

一、填空题（每空1分，共16分)

1. 从逻辑结构看，树是典型的 。

2. 设一棵完全二叉树具有999个结点，则此完全二叉树有 个叶子结点，有

个度为2的结点，有 个度为1的结点。

3. 由n个权值构成的哈夫曼树共有 个结点 。

4. 在线索化二叉树中，T所指结点没有左子树的充要条件是 。

5. 在非空树上，_____没有直接前趋。

6. 深度为k的二叉树最多有 结点，最少有 个结点。

7. 若按层次顺序将一棵有n个结点的完全二叉树的所有结点从1到n编号，那么当i为

且小于n时，结点i的右兄弟是结点 ，否则结点i没有右兄弟。

8. N个结点的二叉树采用二叉链表存放，共有空链域个数为 。

9. 一棵深度为7的满二叉树有___ ___个非终端结点。

10. 将一棵树转换为二叉树表示后,该二叉树的根结点没有 。

11. 采用二叉树来表示树时，树的先根次序遍历结果与其对应的二叉树的 遍历结果是一样的。

12. 一棵Huffman树是带权路径长度最短的二叉树，权值 的外结点离根较远。

二、判断题（如果正确，在对应位置打“”，否则打“”。每题0.5分，共5分)

1

2

3

4

5

6

7

8

9

10

i1. 对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2-1个结点。

2. 二叉树的前序遍历并不能唯一确定这棵树，但是，如果我们还知道该二叉树的根结点是那一个，则可以确定这棵二叉树。

3. 一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数。

4. 度≤2的树就是二叉树。

5. 一棵Huffman树是带权路径长度最短的二叉树，权值较大的外结点离根较远。

第 1 页

楚雄师院计科系 网络工程2010级 《算法与数据结构》课后习题（第6章）

6. 采用二叉树来表示树时，树的先根次序遍历结果与其对应的二叉树的前序遍历结果是一样的。

7. 不存在有偶数个结点的满二叉树。

8. 满二叉树一定是完全二叉树，而完全二叉树不一定是满二叉树。

9. 已知二叉树的前序遍历顺序和中序遍历顺序，可以惟一确定一棵二叉树；

10. 已知二叉树的前序遍历顺序和后序遍历顺序，不能惟一确定一棵二叉树；

三、单项选择（请将正确答案的代号填写在下表对应题号下面。每题1分，共30分)

题号

答案

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

题号 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

答案

1. 树的后根遍历序列等同于该树对应的二叉树的( ).

A). 先序序列 B). 中序序列 C). 后序序列 D) 层次序列

2. 设一棵二叉树中，度为1的结点数为9，则该二叉树的叶结点的数目是( )。

A)10 B)11 C)12 D)不确定

3. 哈夫曼算法可以用于（ ）。

A) 动态存储管理 B) 表达式求值

C) 数据通信的二进制编码 D) 城市间的交通网设计

4. 在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（ ）。

A．队列 B．栈 C．线性表 D．有序表

5. 在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（ ）。

A．不一定相同 B．都相同 C．都不相同 D．互为逆序

6. 由下列三棵树组成的森林换成一棵二叉树为（ ）。

第 2 页

楚雄师院计科系 网络工程2010级 《算法与数据结构》课后习题（第6章）

7. 若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的（ ）。

A．层次遍历算法 B．前序遍历算法 C．中序遍历算法 D．后序遍历算法

8. 哈夫曼树是访问叶结点的外部路径长（ ）的二叉树。

A.最短； B.最长 C.可变 D.不定；

9. 三个结点可以构成（ ）种不同形状的树。

A. 2； B. 3 C. 4 D. 5；

10. 三个结点可以构成（ ）种不同形状的二叉树。

A. 无穷 B. 3 C. 4 D. 5；

11. 一棵有16个结点的完全二叉树，对它按层编号，则对编号为7的结点X，它的双亲结点及右孩子结点的编号分别为（ ）。

A. 2，14 B. 2，15 C. 3，14 D. 3，15；

12. 深度为k的二叉树最多有（ ）结点。

kkk-1 2A.2 B.2-1； C.2 D.k；

13. 具有100个结点的完全二叉树的深度为（ ）。

A. 6 B. 7； C. 8 D. 9；

14. 叶结点个数比度为2的结点的个数多一个，该性质只适用于（ ）。

A.完全二叉树 B.满二叉树 C.树 D.所有二叉树；

15. 具有n个结点的完全二叉树的深度为（ ）。

A. log2n+1 B. log2n+1； C. log2n D. log2n ；

16. 设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是( )

A）M1 B）M1+M2 C）M2+M3 D）M3；

17. 二叉树按二叉链表存储，每个结点包含三个域（lchild、data、rchild），若p指针指向二叉树的根结点，经过运算while（p->lchild!=Nu11）p=p->lchild，则（ ）。

A. p指向二叉树的最右下方的结点 B. p指向二叉树的最左下方的结点；

C. p仍指向根点 D. p为null；

18. 如果图1所示为一棵二叉树，则其中序遍历序为（ ）。

A、abcdefgh B、abdfcegh C、fdbgheca D、bfdagehc；

f g h

b c

a

d e

图1

19. 对任何一棵二叉树，若n0，n1，n2分别是度为0，1，2的结点的个数，则n0=( )

A.n1+1 B. n2+1 C. n1+n2 D.2n1+1

第 3 页

楚雄师院计科系 网络工程2010级 《算法与数据结构》课后习题（第6章）

20. 如图2所示为一线索化二叉树，其线索化是按（ ）进行的。

A、先序 B、中序 C、后序； D、结点生成顺序；

21. 如果图3表示一棵二叉树，且叶子结点d、g、h和i的权分别为4、10、6、12，则该树的带权路径长度为（ ）。

A、32 B、92 C、36 D、8；

g

图3

22. 如果图3所示是二叉树表示的森林，则组成该森林的树的根结点有（ ）。

A、a结点 B、a结点和c结点；

C、b结点和c结点 D、a结点、b结点和c结点；

23. 对图3进行广度优先搜索，则其搜索结点顺序为（ ）。

A、abcdefghi； B、abdegcfhi； C、dbgeahfic； D、dgebhifca。

24. 如果图4所示二叉树表示一棵树，则在该树中结点d的双亲结点是（ ）。

A、a结点； B、b结点 C、c结点 D、空；

d

图4

第 4 页

A

B

D

F G

图2

C

E

H

a

b

d e

h

f

i

c

a

b

c

楚雄师院计科系 网络工程2010级 《算法与数据结构》课后习题（第6章）

25. 已知某非空二叉树采用顺序存储结构，树中结点的数据信息依次存放在一个一维数组中，即ABC□DFE□□G□□H□□，该二叉树的中序遍历序列为( )

A) G,D,B,A,F,H,C,E B) G,B,D,A,F,H,C,E

C) B,G,D,A,F,H,C,E D) B,D,G,A,F,H,C,E

26. 对一棵深度为k且具有2 -1个结点的编号完全二叉树，其非叶子结点i的右儿子结点（ ）。

A、一定不存在； B、不一定存在；

C、一定存在且编号为2i+1； D、一定存在且编号为2i。

27. 若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是（ ）。

A.根结点无右子树的二叉树 B.根结点无左子树的二叉树

C.根结点可能有左子树和右子树； D.各结点只有一个儿子和二叉树；

28. 把一棵树转换为二叉树后，这棵二叉树的形态是 ( )

A) 唯一的，且根结点都没有左孩子 Ｂ）有多种，且根结点都没有右孩子

Ｃ）唯一的，且根结点都没有右孩子 Ｄ）有多种，且根结点都没有左孩子

29. 已知二叉树的先序序列为ABDEFC，中序序列为DBEAFC，则后序序列为( )

30. 某二叉树的后序序列和中序序列正好相同，则该二叉树一定是( )的二叉树。

A. 空或只有一个结点 B.高度等于其结点数

C. 空或任一结点无左孩子 D. 空或任一结点无右孩子

四、 简答及应用题 （共27分）

1．（6分）已知二叉树的先序序列和中序序列分别为ABCDEFGHIJ和BCDAFEHJIG。

（1）画出该二叉树；

（2）画出与（1）求得的二叉树对应的森林。

2.(3分）设二叉树后根遍历的结果为BCA，画出所有可得到这一结果的二叉树。

3.（4分）试说明一棵二叉树无论进行前序、中序或后序遍历，其叶子结点的相对次序都不第 5 页

k

楚雄师院计科系 网络工程2010级 《算法与数据结构》课后习题（第6章）

会发生改变。

4、（3分）简要说明下列算法的功能。

输入：n个权值{W1，W2，……，Wn}；

输出：只包含一棵树的集F；

过程：

⑴根据给定的n个权值{W1，W2，……，Wn}构成n棵二叉树集合F={T1，T2，……，Tn}，其中每棵二叉树Ti中只有一个带权为Wi的根结点，其左右子树均为空；

⑵在F中选取两棵根结点权值最小的树作为左右子树，来构造一棵新的二叉树且置新二叉树根结点的权值为其左右子树上根结点权值之和；

⑶在F中删除这两棵树；

⑷重复⑵和⑶步，直到F中只有一棵树为止；

⑸返回F。

算法的功能是：

5.

（3分）给定如图所示二叉树T，请画出与其对应的中序线索二叉树。

d

g

h i

b

e f

c

a

6.(8分)假设通信电文使用的字符集为{C1,C2,C3,C4,C5,C6,C7 }，各字符在电文中出现的频度分别为：{16，2，4，19，40，11，8}，试为这7个字符设计哈夫曼编码。请先画出你所构造的哈夫曼树(要求树中左孩子结点的权值小于右孩子结点的权值)，然后分别写出每个字符对应的编码,并求出该编码的平均码长（写出计算公式及结果）。

第 6 页

楚雄师院计科系 网络工程2010级 《算法与数据结构》课后习题（第6章）

(1)哈夫曼树:

(2)

字符

权值

编码

C1

16

C2

2

C3

4

C4

19

C5

40

C6

11

C7

8

(3)平均码长=

五、算法分析与设计(22分)

已知二叉树的存储结构为二叉链表，其类型定义如下：

typedef struct BitNode

{elemtype data;

struct BitNode *lchild, *rchild;}*BinTree;

（以下各题基于上述定义）

1.(8分)计算二叉树中叶子结点数的算法：请在空白处填入适当的内容

int CountLeaf（BinTree bt）

{/*开始时，bt为根结点所在链结点的指针，返回值为bt的叶子数*/

if (① ) return 0;

if (bt->lchild==NULL &&② ) return 1;

return (CountLeaf (③ )+CountLeaf (④ ));

}

2. (8分)计算二叉树的深度的算法：请在空白处填入适当的内容

/* 其中：max( )函数可求出两个整数中的较大值 */

第 7 页

楚雄师院计科系 网络工程2010级 《算法与数据结构》课后习题（第6章）

int depth(BinTree T)

{if( ！T )

Return ⑤ ;

el

return(⑥ + max(depth(⑦ ),depth(⑧ )));}

3. (6分)阅读算法F32，并回答下列问题：

(1)对于如图所示的二叉树，画出执行算法f32的结果；

（2）简述算法abc的功能。

BinTree abc(BinTree bt1)

{

BinTree bt2;

if(bt1==NULL)

bt2=NULL;

el {

bt2=(BitNode *)malloc(sizeof(BiTNode));

bt2->data=bt1->data;

bt2->rchild=abc(bt1->lchild);

bt2->lchild=abc(bt1->rchild);

}

return bt2;

}

第 8 页

楚雄师院计科系 网络工程2010级 《算法与数据结构》课后习题（第6章）参考答案

【课后习题】第6章 树和二叉树（参考答案）

一、填空题（每空1分，共16分)

1. 从逻辑结构看，树是典型的 树型结构 。

2. 设一棵完全二叉树具有999个结点，则此完全二叉树有 500个叶子结点，有 499 个度为2的结点，有 0 个度为1的结点。

3. 由n个权值构成的哈夫曼树共有 2N-1 个结点 。

4. 在线索化二叉树中，T所指结点没有左子树的充要条件是 T->ltag=1 。

5. 在非空树上，_根_没有直接前趋。

k6. 深度为k的二叉树最多有 2-1 结点，最少有 k 个结点。

7. 若按层次顺序将一棵有n个结点的完全二叉树的所有结点从1到n编号，那么当i为

偶数 且小于n时，结点i的右兄弟是结点 i+1 ，否则结点i没有右兄弟。

8. N个结点的二叉树采用二叉链表存放，共有空链域个数为 N+1 。

9. 一棵深度为7的满二叉树有_63_个非终端结点。

10. 将一棵树转换为二叉树表示后,该二叉树的根结点没有 右子树 。

11. 采用二叉树来表示树时，树的先根次序遍历结果与其对应的二叉树的 先序 遍历结果是一样的。

12. 一棵Huffman树是带权路径长度最短的二叉树，权值 较小 的外结点离根较远。

二、判断题（如果正确，在对应位置打“”，否则打“”。每题0.5分，共5分)

1

X

2

X

3

X

4

X

5

X

6



7



8



9



10



三、单项选择（请将正确答案的代号填写在下表对应题号下面。每题1分，共30分)

题号

答案

1 2 3

C

4

A

5

B

6 7 8

A

9

A

10 11 12 13 14 15

D D B B D B B D A C

题号 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

答案 C B D B C B B A A C C C C C D

四、 简答及应用题 （共27分）

1．（6分）（1）画出该二叉树；第 1 页

楚雄师院计科系 网络工程2010级 《算法与数据结构》课后习题（第6章）参考答案

A

（2）画出与（1）求得的二叉树对应的森林。

B

E

G

C

F

A

E

H

D

I

B C D

F

J

2.(3分）设二叉树后根遍历的结果为BCA，画出所有可得到这一结果的二叉树。

3.（4分）答：因为无论在前序、中序或后序遍历中，都规定先遍历左子树，再遍历右子树，所以一棵二叉树无论进行前序、中序或后序遍历，其叶子结点的相对次序都不会发生改变。4、（3分）算法的功能是构造最优二叉树。

5.

（3分）给定如图所示二叉树T，请画出与其对应的中序线索二叉树。

a

b c

d e f

g h i

6.(8分)

字符

C1 C2 C3 C4 C5 C6 C7

权值

16 2 4 19 40 11 8

编码

110 10100 10101 111 0 100 1011

平均码长=(16*3+2*5+4*5+19*3+40*1+11*3+8*4)/100=2.4

哈夫曼树

第 2 页

G

H

I

J

楚雄师院计科系 网络工程2010级 《算法与数据结构》课后习题（第6章）参考答案

100

40

60

25 35

11

14

16

19

6

8

2

4

五、算法分析与设计(22分)

1.① bt==NULL ② bt->rchild==NULL ③ bt->lchild ④ bt->rchild

2.⑤ 0 ⑥ 1 ⑦ T->lchild ⑧ T->rchild

3.(1)

算法abc的功能: 将二叉树bt1复制到bt2,复制时,将bt1的所结点的左子树复制到bt2对应的右子树;将bt1的所有结点的右子树复制到bt2对应的左子树.

第 3 页

楚雄师院计科系 网络工程2010级 《算法与数据结构》课后习题（第6章）参考答案

【课后习题】第6章 树和二叉树（参考答案）

网络工程2010级（ ）班

学号： 姓名：

题 号

得 分

一

16

二

5

三

30

四

27

五

22

总分

100

一、填空题（每空1分，共16分)

1. 从逻辑结构看，树是典型的 树型结构 。

2. 设一棵完全二叉树具有999个结点，则此完全二叉树有 500个叶子结点，有 499 个度为2的结点，有 0 个度为1的结点。

3. 由n个权值构成的哈夫曼树共有 2N-1 个结点 。

4. 在线索化二叉树中，T所指结点没有左子树的充要条件是 T->ltag=1 。

5. 在非空树上，_根_没有直接前趋。

6. 深度为k的二叉树最多有 2-1 结点，最少有 k 个结点。

7. 若按层次顺序将一棵有n个结点的完全二叉树的所有结点从1到n编号，那么当i为

偶数 且小于n时，结点i的右兄弟是结点 i+1 ，否则结点i没有右兄弟。

8. N个结点的二叉树采用二叉链表存放，共有空链域个数为 N+1 。

9. 一棵深度为7的满二叉树有_63_个非终端结点。

10. 将一棵树转换为二叉树表示后,该二叉树的根结点没有 右子树 。

11. 采用二叉树来表示树时，树的先根次序遍历结果与其对应的二叉树的 先序 遍历结果是一样的。

12. 一棵Huffman树是带权路径长度最短的二叉树，权值 较小 的外结点离根较远。

二、判断题（如果正确，在对应位置打“”，否则打“”。每题0.5分，共5分)

1

X

2

X

3

X

4

X

5

X

6



7



8



9



10



ik1. 对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2-1个结点。

2. 二叉树的前序遍历并不能唯一确定这棵树，但是，如果我们还知道该二叉树的根结点是那一个，则可以确定这棵二叉树。

3. 一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数。

4. 度≤2的树就是二叉树。

5. 一棵Huffman树是带权路径长度最短的二叉树，权值较大的外结点离根较远。

第 1 页

楚雄师院计科系 网络工程2010级 《算法与数据结构》课后习题（第6章）参考答案

6. 采用二叉树来表示树时，树的先根次序遍历结果与其对应的二叉树的前序遍历结果是一样的。

7. 不存在有偶数个结点的满二叉树。

8. 满二叉树一定是完全二叉树，而完全二叉树不一定是满二叉树。

9. 已知二叉树的前序遍历顺序和中序遍历顺序，可以惟一确定一棵二叉树；

10. 已知二叉树的前序遍历顺序和后序遍历顺序，不能惟一确定一棵二叉树；

三、单项选择（请将正确答案的代号填写在下表对应题号下面。每题1分，共30分)

题号

答案

1 2 3

C

4

A

5

B

6 7 8

A

9

A

10 11 12 13 14 15

D D B B D B B D A C

题号 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

答案 C B D B C B B A A C C C C C D

1. 树的后根遍历序列等同于该树对应的二叉树的( ).

A). 先序序列 B). 中序序列 C). 后序序列 D) 层次序列

2. 设一棵二叉树中，度为1的结点数为9，则该二叉树的叶结点的数目是( )。

A)10 B)11 C)12 D)不确定

3. 哈夫曼算法可以用于（ ）。

A) 动态存储管理 B) 表达式求值

C) 数据通信的二进制编码 D) 城市间的交通网设计

4. 在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（ ）。

A．队列 B．栈 C．线性表 D．有序表

5. 在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（ ）。

A．不一定相同 B．都相同 C．都不相同 D．互为逆序

6. 由下列三棵树组成的森林换成一棵二叉树为（ ）。

第 2 页

楚雄师院计科系 网络工程2010级 《算法与数据结构》课后习题（第6章）参考答案

7. 若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的（ ）。

A．层次遍历算法 B．前序遍历算法 C．中序遍历算法 D．后序遍历算法

8. 哈夫曼树是访问叶结点的外部路径长（ ）的二叉树。

A.最短； B.最长 C.可变 D.不定；

9. 三个结点可以构成（ ）种不同形状的树。

A. 2； B. 3 C. 4 D. 5；

10. 三个结点可以构成（ ）种不同形状的二叉树。

A. 无穷 B. 3 C. 4 D. 5；

11. 一棵有16个结点的完全二叉树，对它按层编号，则对编号为7的结点X，它的双亲结点及右孩子结点的编号分别为（ ）。

A. 2，14 B. 2，15 C. 3，14 D. 3，15；

12. 深度为k的二叉树最多有（ ）结点。

kkk-1 2A.2 B.2-1； C.2 D.k；

13. 具有100个结点的完全二叉树的深度为（ ）。

A. 6 B. 7； C. 8 D. 9；

14. 叶结点个数比度为2的结点的个数多一个，该性质只适用于（ ）。

A.完全二叉树 B.满二叉树 C.树 D.所有二叉树；

15. 具有n个结点的完全二叉树的深度为（ ）。

A. log2n+1 B. log2n+1； C. log2n D. log2n ；

16. 设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是( )

A）M1 B）M1+M2 C）M2+M3 D）M3；

17. 二叉树按二叉链表存储，每个结点包含三个域（lchild、data、rchild），若p指针指向二叉树的根结点，经过运算while（p->lchild!=Nu11）p=p->lchild，则（ ）。

A. p指向二叉树的最右下方的结点 B. p指向二叉树的最左下方的结点；

C. p仍指向根点 D. p为null；

18. 如果图1所示为一棵二叉树，则其中序遍历序为（ ）。

A、abcdefgh B、abdfcegh C、fdbgheca D、bfdagehc；

f g h

b c

a

d e

图1

19. 对任何一棵二叉树，若n0，n1，n2分别是度为0，1，2的结点的个数，则n0=( )

A.n1+1 B. n2+1 C. n1+n2 D.2n1+1

第 3 页

楚雄师院计科系 网络工程2010级 《算法与数据结构》课后习题（第6章）参考答案

20. 如图2所示为一线索化二叉树，其线索化是按（ ）进行的。

A、先序 B、中序 C、后序； D、结点生成顺序；

21. 如果图3表示一棵二叉树，且叶子结点d、g、h和i的权分别为4、10、6、12，则该树的带权路径长度为（ ）。

A、32 B、92 C、36 D、8；

g

图3

h i

d

b

e f

c

a

F G

图2

H

B

D

C

E

A

22. 如果图3所示是二叉树表示的森林，则组成该森林的树的根结点有（ ）。

A、a结点 B、a结点和c结点；

C、b结点和c结点 D、a结点、b结点和c结点；

23. 对图3进行广度优先搜索，则其搜索结点顺序为（ ）。

A、abcdefghi； B、abdegcfhi； C、dbgeahfic； D、dgebhifca。

24. 如果图4所示二叉树表示一棵树，则在该树中结点d的双亲结点是（ ）。

A、a结点； B、b结点 C、c结点 D、空；

d

图4

第 4 页

a

b

c

楚雄师院计科系 网络工程2010级 《算法与数据结构》课后习题（第6章）参考答案

25. 已知某非空二叉树采用顺序存储结构，树中结点的数据信息依次存放在一个一维数组中，即ABC□DFE□□G□□H□□，该二叉树的中序遍历序列为( )

A) G,D,B,A,F,H,C,E B) G,B,D,A,F,H,C,E

C) B,G,D,A,F,H,C,E D) B,D,G,A,F,H,C,E

26. 对一棵深度为k且具有2 -1个结点的编号完全二叉树，其非叶子结点i的右儿子结k点（ ）。

A、一定不存在； B、不一定存在；

C、一定存在且编号为2i+1； D、一定存在且编号为2i。

27. 若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是（ ）。

A.根结点无右子树的二叉树 B.根结点无左子树的二叉树

C.根结点可能有左子树和右子树； D.各结点只有一个儿子和二叉树；

28. 把一棵树转换为二叉树后，这棵二叉树的形态是 ( )

A) 唯一的，且根结点都没有左孩子 Ｂ）有多种，且根结点都没有右孩子

Ｃ）唯一的，且根结点都没有右孩子 Ｄ）有多种，且根结点都没有左孩子

29. 已知二叉树的先序序列为ABDEFC，中序序列为DBEAFC，则后序序列为(

30. 某二叉树的后序序列和中序序列正好相同，则该二叉树一定是( )的二叉树。A. 空或只有一个结点 B.高度等于其结点数

C. 空或任一结点无左孩子 D. 空或任一结点无右孩子

四、 简答及应用题 （共27分）

1．（6分）已知二叉树的先序序列和中序序列分别为ABCDEFGHIJ和BCDAFEHJIG。

（1）画出该二叉树；

A

B

E

G

C

F

H

D

I

J

（2）画出与（1）求得的二叉树对应的森林。

第 5 页

)

楚雄师院计科系 网络工程2010级 《算法与数据结构》课后习题（第6章）参考答案

A

E G

H

B C D

F

I

J

3.(3分）设二叉树后根遍历的结果为BCA，画出所有可得到这一结果的二叉树。

4.（4分）试说明一棵二叉树无论进行前序、中序或后序遍历，其叶子结点的相对次序都不会发生改变。

答：因为无论在前序、中序或后序遍历中，都规定先遍历左子树，再遍历右子树，所以一棵二叉树无论进行前序、中序或后序遍历，其叶子结点的相对次序都不会发生改变。

5、（3分）简要说明下列算法的功能。

输入：n个权值{W1，W2，……，Wn}；

输出：只包含一棵树的集F；

过程：

⑴根据给定的n个权值{W1，W2，……，Wn}构成n棵二叉树集合F={T1，T2，……，Tn}，其中每棵二叉树Ti中只有一个带权为Wi的根结点，其左右子树均为空；

⑵在F中选取两棵根结点权值最小的树作为左右子树，来构造一棵新的二叉树且置新二叉树根结点的权值为其左右子树上根结点权值之和；

⑶在F中删除这两棵树；

⑷重复⑵和⑶步，直到F中只有一棵树为止；

⑸返回F。

算法的功能是构造最优二叉树。

6.

（3分）给定如图所示二叉树T，请画出与其对应的中序线索二叉树。

d

g

h i

第 6 页

a

b

e f

c

楚雄师院计科系 网络工程2010级 《算法与数据结构》课后习题（第6章）参考答案

7.(8分)假设通信电文使用的字符集为{C1,C2,C3,C4,C5,C6,C7 }，各字符在电文中出现的频度分别为：{16，2，4，19，40，11，8}，试为这7个字符设计哈夫曼编码。请先画出你所构造的哈夫曼树(要求树中左孩子结点的权值小于右孩子结点的权值)，然后分别写出每个字符对应的编码,并求出该编码的平均码长（写出计算公式及结果）。

字符

权值

编码

C1

16

110

C2

2

10100

C3

4

10101

C4

19

111

C5

40

0

C6

11

100

C7

8

1011

平均码长=(16*3+2*5+4*5+19*3+40*1+11*3+8*4)/100=2.4

哈夫曼树

100

40

60

25 35

11

14

16

19

6

8

2

4

五、算法分析与设计(22分)

已知二叉树的存储结构为二叉链表，其类型定义如下：

typedef struct BitNode

{elemtype data;

struct BitNode *lchild, *rchild;}*BinTree;

（以下各题基于上述定义）

1.(8分)计算二叉树中叶子结点数的算法：请在空白处填入适当的内容

int CountLeaf（BinTree bt）

{/*开始时，bt为根结点所在链结点的指针，返回值为bt的叶子数*/

第 7 页

楚雄师院计科系 网络工程2010级 《算法与数据结构》课后习题（第6章）参考答案

if (① bt==NULL ) return 0;

if (bt->lchild==NULL &&② bt->rchild==NULL ) return 1;

return (CountLeaf (③ bt->lchild )+CountLeaf (④ bt->rchild ));

}

2. (8分)计算二叉树的深度的算法：请在空白处填入适当的内容

/* 其中：max( )函数可求出两个整数中的较大值 */

int depth(BinTree T)

{if( ！T )

Return ⑤ 0 ;

el

return(⑥ 1 + max(depth(⑦T->lchild ),depth(⑧ T->rchild )));}

3. (6分)阅读算法F32，并回答下列问题：

(1)对于如图所示的二叉树，画出执行算法f32的结果；

（2）简述算法abc的功能。

BinTree abc(BinTree bt1)

{

BinTree bt2;

if(bt1==NULL)

bt2=NULL;

el {

第 8 页

楚雄师院计科系 网络工程2010级 《算法与数据结构》课后习题（第6章）参考答案

bt2=(BitNode *)malloc(sizeof(BiTNode));

bt2->data=bt1->data;

bt2->rchild=abc(bt1->lchild);

bt2->lchild=abc(bt1->rchild);

}

return bt2;

}

算法abc的功能: 将二叉树bt1复制到bt2,复制时,将bt1的所结点的左子树复制到bt2对应的右子树;将bt1的所有结点的右子树复制到bt2对应的左子树.

-------------------------------------------------------------------------------------------------------------------

1、知二叉树bt。设对bt进行中序线索化过程后，指向根结点的头结点为thrt。再设该线索二叉树最后一个结点的后续结点为thrt，第一个结点的前驱结点为thrt。简要描述其线索二叉树的中序遍历过程 。

输入：线索化二叉树thrt

输出：线索化二叉树thrt的中序遍历序列

过程

⑴指针P从根结点开始遍历直到P指向thrt为止，每次遍历执行⑵～⑸步；

⑵P向左分枝遍历直到没有左儿女结点为止；

⑶访问当前结点P；

⑷如果P存在后继结点（非右儿女结点），则不断向右线索遍历后继结点P并访问P结点；

⑸P指向其右结点；

⑹结束返回。

2．（3分）已知一棵树如右图所示,请将该树转化为二叉树。

A

B

E

F

C

D

G

第 9 页