完整word版,6、树
男子乒乓球-驻足痴望
6 树
一、单项选择题（15题）
1、按照二叉树的定义，具有3个结点的二叉树有（ ）种。
A． 3
B．
4
C． 5
D． 6
2、深度为5的二叉树至多有（
）个结点。
A． 16
B． 32
C． 31
D． 10
3、在一非空二叉树的中序遍历序列中，根结点的右边（ ）。
A
只有右子树上的所有结点 B 只有右子树上的部分结点
C 只有左子树上的部分结点
D 只有左子树上的所有结点
4、深度为4的完全二叉树至少有（ ）个结点。
A 16 B 15 C 8 D 7
5、具有n个结点的二叉树若采用链式存储，则空闲的指针域有（ ）个。
A n
B n-1 C n+1 D 2n
6、针对右图的这棵二叉树，下列哪个说法是正确的？（ ）
A 该树的度为3
B 该树的深度为4
C 结点D的度为0 D 结点A是结点D和F的双亲
7、某二叉树高度为h，所有结点的度为0或为2，则这棵二叉树最少有（ ）
个结点。
A 2h B 2h-1 C 2h+1 D h+1
8、针对右图的这棵二叉树，下列哪个说法是不正确的？（ ）
A 该树的度为3
B 该树的深度为4
C 结点D的度为0 D 结点A是结点B和C的双亲
9、 二叉树是非线性数据结构,所以（ ）。
A) 它不能用顺序存储结构存储
B）它不能用链式存储结构存储
C）顺序存储结构和链式存储结构都能存储
D）顺序存储结构和链式存储结构
都不能使用
10、设n，m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是（ ）。
A．n在m右方 B．n是m祖先 C．n在m左方
D．n是m子孙
11、由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度
为(
)。
A. 24 B. 48 C. 72 D. 53
12、高度
k
的二叉树的最大结点数为( )。
A.
2
k
-1 B 2
k
+1
C.2
k
-1 D. 2
k
-1
13、有n(n>0)个结点的完全二叉树的深度为( )。
A）log
2
(n) B) log
2
(n)
C） log
2
(n) +1 D）
log
2
(n)+1
14、设二叉树根结点的层次为1，所有含有63个结点的二叉树中，最小高度是
（
）。
(A) 6 (B) 5 (C) 4 (D) 7
15、设二叉树根结点的层次为1，所有含有15个结点的二叉树中，最小高度是
（ ）
A、6 B、5 C、4 D、3
二、填空题（20题）
1、在一棵二叉树中，若度为零的结点的个数为n0，度为2的结点的个数为n2，
则有n0=
。
2、前序遍历序列与中序遍历序列相同的二叉树满足特征： （1）空树
；（2）仅
有一个结点的二叉树 ；（3）
。
3、 二叉树的顺序存储结构中，结点i的双亲是编号为_
___的结点。
4、 二叉树的顺序存储结构中，结点i的左孩子是编号为__
___的结点。
5、二叉树的顺序存储结构中，结点i的右孩子是编号为__
_的结点。
6、在
n
个带权叶子结点构造出的所有二叉树中，带权路径长
度最小的二叉树称
为 。
7、树的带权路径长度WPL定义为树中所有
结点的带权路径长度之和。
8、
某二叉树有20个叶子结点，有30个结点度为1，则该二叉树总结点数是_ _。
9、二叉树若采用链式存储,则每个结点至少应设 个指针域。
10、后序遍历序列与中序遍历序列相同的二叉树满足特征： （1）空树
；（2）
仅有一个结点的二叉树；（3）
。
11、一棵具有257个结点的完全二叉树，它的深度为 。
12、已知二叉树T的中根序列是CBEDAGJIFH，后根序列是CEDBJIGHFA
，二叉树
根结点的右子女是 。
13、在树形结构中,树根结点没有 结点,
可以有1个或多个直接后继结
点。
14、在树形结构中,树根结点没有直接前驱结点, 可以有
直接后继结
点。
15、在树形结构中,除树根结点外的其余每个结点有且只有
个直接前驱结
点；可以有0个或多个直接后继结点。
16、高度为h（>=0）的二叉树，至少有 个结点。
17、一
棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中
度为2的结点有
个。
18、对某二叉树进行前序遍历的结果为EBADCFHGIKJ，中序遍历的结果为
ABCDEFGHIJK,则后序遍历的结果为 。
19、对某二叉树进行后序遍历的结果为DCEGBFHKJIA，中序遍历的结果为
DCBG
EAHFIJK,则前序编历的结果为 。
20、高度为h（>=0）的二叉树，最多有 个结点。
三、综合题（21题）
1、假定一棵二叉树广义表表示为a(b(c,e),d(
f,g))，分别写出对它进行先序、
中序、后序遍历的结果。
2、已知二叉树的
先序、中序遍历序列分别为ＡＢＤＦＪＧＫＣＥＨＩＬＭ和Ｂ
ＦＪＤＧＫＡＣＨＥＬＩＭ，试写出后序遍
历时得到的结点序列。
3、已知二叉树的后序、中序遍历序列分别为JFKGDBHLMI
ECA和BFJDGKACHELIM，
试写出前序遍历时得到的结点序列。
4、
设给定权集Ｗ＝｛2，3，4，7，8，9｝，试构造关于Ｗ的一棵哈夫曼树和哈夫
曼编码，并求其加权
路径长度ＷＰＬ。
5、给定一组权值W={12，15，4，9，3，1}。
（1） 构造出相应的哈夫曼树（规定左孩子的权值不大于右孩子的权值）。
（2） 写出哈夫曼编码。
（3） 计算其带权路径长度WPL。
6、设有字符集{A，B，C，D，E，F
}，相应频度为{0.05，0.1，0.2，0.35，0.05，
0.25}。
（1）构造出相应的哈夫曼树（规定左孩子的权值不大于右孩子的权值）。
（2）给出各个字符的哈夫曼编码。
（3）计算加权路径长度WPL。
7、已知一棵二叉树如图所示，试求：
a
b
c
d e f
g h
（1）写出二叉树的前、中、后序遍历的结果。
（2）将它转换为对应的树或森林。
（3）对该二叉树进行前序线索化。
8、根据如图所示的树结构，完成下列各题。
A
B
C
F G
D
H E
L M
I J K
（1）将给定的树转化成一棵二叉树。
（2）写出二叉树的前、中、后序遍历序列。
（3）将此二叉树中序线索化。
9、请回答具有三个结点的树和二叉树分别有几种形状？并分别画出所有形状。
1
0、已知某二叉树的后序遍历序列是KJIFEMLHGDCBA，中序遍历序列是
EIJKFBCGL
MHDA，画出二叉树，给出先序遍历序列。
11、已知某二叉树的先序遍历序列是A
BEFIJKCDGHLM，中序遍历序列是
EIJKFBCGLMHDA，画出二叉树，给出后序遍历
序列。
12、已知某二叉树的后序遍历序列为DBEFCA，中序遍历序列为DBAECF
，请画出
该二叉树，并对其进行前序线索化。
13、请画出下图所示二叉树的链式存储示意图，并写其前序、中序、后序遍历序
列。
14、已知一组权值序列为{3,
20, 6, 8, 7},请构造哈夫曼树,
给出相应的哈夫
曼编码,并计算树的带权路径长度。（注，按照左小右大的原则）。
15、将如下的森林转换为一棵二叉树，然后写出其前、中、后序遍历序列。
16、假设字符a,b,c,d,e,f,g的
使用频度分别是0.06,0.03,0.19,0.22,0.16,
0.27,0.07，写出a
,b,c,d,e,f,g的Huffman编码(在构造哈夫曼树时，要求左子树
根结点的权值小于等
于右子树根结点的权值)。
17、已知某二叉树的前序遍历序列为ABDCEF，中序遍历
序列为DBAECF，请画出
该二叉树，并对其进行后序线索化。
18、已知一串
电文中出现的字符为{s,g,j,y,q},它们出现的次数分别为{4，5，1，
6，2}，请以此
画出其相对应的哈夫曼树，计算WPL，并给出每个字符的哈夫
曼编码。
19、写出如图所示的二叉树分别按先、中、后序遍历时得到的结点序列。
20、字符a,b,c,d,e,f,g的使用频度分别是0.07,0.09,0.12,
0.22,0.20, 0.27,
0.03，写出a,b,c,d,e,f,g的Huffman编
码(在构造哈夫曼树时，要求左子
树根结点的权值小于等于右子树根结点的权值)。
21、一个二叉树按顺序方式存储在一个一维数组中，如图：
1 2 3 4 5 6 7
8 9 10 11 12 13 14 15
E B C I A F G J D H
（1）根据其存储结构，画出该二叉树。
（2）写出按前序、中序、后序编历该二叉树所得的结点序列。
四、编程题（2题）
1、编写一个计算二叉树中叶子结点的数目递归算法。
2、编写递归算法，计算二叉树中所有结点的数目。
树部分答案
一、单项选择题（15题）
1.C 2.C 3.A 4.C
5.C 6.C 7.B
8.A 9.C 10.C 11.D 12.A
13.C 14.A 15.C
二、填空题（20题）
1、
n0= n2+1 。
2、
任一结点均无左孩子的非空二叉树（右单支） 。
3、_ _i2____
4、___2i____
5、2i +1 _
6、
最优二叉树（或哈夫曼树） 。
7、 叶子
8、_69_。
9、
2
10、任一结点均无右孩子的非空二叉树（左单支） 。
11、 9 。
12、F 。
13、 直接前驱
14、 0个或多个
15、1
16、 h
17、 33
18、
ACDBGJKIHFE 。
19、 ABCDGEIHFJK 。
20、2
h
-1
三、综合题（21题）
1、解：先序遍历序列：abcedfg
中序遍历序列：cbeafdg
后序遍历序列：cebfgda
2、解：后序遍历序列：
JFKGDBHLMIECA
3、解：前序遍历序列：ＡＢＤＦＪＧＫＣＥＨＩＬＭ
4、解：（1）哈夫曼树见图：
33
18 15
9
9 7 8
5
2 3
4
（2）哈夫曼编码：
2：0000 3：0001 4：001 7：10 8：11
9：01
（3）WPL=2*4+3*4+4*3+7*2+8*2+9*2＝80
5、解：（1）哈夫曼树如图所示：
4
12
9 8
1
1
（2） 哈夫曼编码如下：
4
4
权值为12的编码：10
权值为15的编码：11
3 1
权值为4的编码：010
权值为9的编码：00
权值为3的编码：0110
权值为1的编码：0111
（3） 带权的路径长度WPL=12*2+15*2+4*3+9*2+3*4+1*4=100
6、解：（1）哈夫曼树如图所示：
0.1
0.4
0.6
0.2 0.2
0.25
0.3
C
F D
0.1
0.1
B
0.00.0
A
E
（2）哈夫曼编码如下：
A：0110 B：010 C：00 D：11
E：0111 F：10
（3）
WPL=0.05*4+0.1*3+0.2*2+0.35*2+0.05*4+0.25*2=2.3
7. 解：（1）二叉树的前、中、后序遍历的结果。
前序：abdgecfh
中序：dgbeafhc
后序：ghebhfca
（2）换为对应的树或森林
c
a
be
f h
d g
（3）前序线索化
a
b
c
d e f
NULL
g
h
8、解：（1）
A
B
C
E
F D
I
G
J H
K L
M
（2）二叉树的前序遍历序列：ABEFIJKCDGHLM
二叉树的中序遍历序列：EIJKFBCGLMHDA
二叉树的后序遍历序列：KJIFEMLHGDCBA
（3）中序线索化：
A
NULL
B
NULL
E
C
F D
I G
J H
K L
M
9. 解：（1）三个结点的树有两种形状：
（2）三个结点的二叉树有五种形状：
10.
解：（1）二叉树如图所示：
A
B
C
E
F D
I G
J H
K L
M
（2）先序遍历序列为：ABEFIJKCDGHLM。
11、解：（1）二叉树如图所示：
A
B
C
E
F D
I G
J H
K L
M
（2）后序遍历序列为：KJIFEMLHGDCBA
12. 解：（1）二叉树如图所示：
A
B
C
D
E
F
前序遍历序列为：ABDCEF。
（2）前序线索树如图所示：
A
B
C
D
E
F
NULL
13.
解：（1）链式存储图：
^
A
t
A
A
^
^
A
^ ^
A
^
A
^
（2）前序遍历序列：ABDCEF，中序遍历序列：DBAEFC，后序遍历序列：DBFECA
14. 解：（1）哈夫曼树如图所示：
44
20
9
24
15
6
7
8
3
（2）权为3的编码为：100
权为20的编码为：0
权为6的编码为：101
权为8的编码为：111
权为7的编码为：110
（3）WPL＝20×1＋（3＋6＋7＋8）×3＝92
15. 解：（1）转换后的二叉树为：
（2）前序遍历序列：ABCDFGEIHJ
中序遍历序列：CBAFGEDHJI
后序遍历序列：CBEGFJHIDA
16、解： 6(a)：11111
3(b)：11110 19(c)：00 22(d)：01 16(e)：110
27(f)：10 7(g)：1110
17、解：（1）构造的二叉树如下：
（2）中序线索化如下：
NULL
18.
解：（1）哈夫曼树为：
18
7
11
4
3
5
6
s
g
y
2
1
q
j
（2）WPL=4*2+1*3+2*3+5*2+6*2=39
（3）各字符编码为：
s:00 g:10 j:010
y:11 q:011
19、解：前序遍历序列：ABDGHJKECFIM，中序
遍历序列：GDJHKBEACFMI，后序遍
历序列：GJKHDEBMIFCA
20、解：7(a)：11111 9(b)：1110 12(c )：110
22(d)：01 20(e)：00
27(f)：10 3(g)：11110
21. 解：（1）二叉树如图所示：
E
B C
I A F
G J D H
（2）前序序列：EBIGCAJFDH
中序序列：IGBEJACDFH
后序序列：GIBJADHFCE
四、编程题（2题）
1.
解：int leafs( bitree *t)
{ int num1,num2;
if(t = = NULL)
return(0);
else if (t->lchild= =NULL &&
rchild= =NULL) return(1);
else {
num1=leafs(t->lchild);
num2=leafs(t->rchild);
return
(num1+num2);
}
}
2.
解：int nodes( bitree *t)
{ int
num1,num2;
if(t = = NULL) return(0);
else
{ num1=nodes(t->lchild);
num2=nodes(t->rchild);
return
(num1+num2+1);
}
}