一、单项选择题：
1、下图中,______不是完全二叉树。
A B
C
D
2、在线索二叉树中,t所指节点没有左子树的充要条件是：
A t->left==null
B t->ltag==1
C t->ltag==1 && t->left==null
D 以上都不对
3、二叉树按某种顺序线索化后，任一节点均有指向其前驱和后继的线索，这种说法：
A 正确 B 错误
4、二叉树的前序遍历中，任意一个节点均处于其孩子节点的前面，这种说法：
A 正确 B 错误
5、由于二叉树中每个节点的度最大为 2，所以二叉树是一种特殊的树，这种说法：
A 正确 B 错误
6、设高度为 h的二叉树只有度为 0和 2的节点，则此类二叉树中所包含的节点数至少为：
A 2h B 2h-1 C 2h+1 D h+1
7、下图所示二叉树的中序遍历序列是：
A abcdgef B dfebagc C dbaefcg D defbagc
a
b c
d
e
f
g
8、已知某二叉树的后序遍历序列是 dabec，中序遍历序列是 debac，它的前序遍历序列是：
A acbed B decab C deabc D cedba
9、已知某二叉树的前序遍历序列是 abdgcefh，中序遍历序列是 dgbaechf，它的后序遍历序列是：
A bdgcefha B gdbecfha C bdgaechf D gdbehfca
10、下图是有一个森林转化成的二叉树，那么森林有 ________个叶子结点。
A 4 B 5 C 6 D 7
a
b
c
d
e
f
g
h
i j
11,设一棵完全二叉树具有 1000个结点，则此完全二叉树有 个叶子结点，有 个度为 2的结点，有 个结点只有非空左子树，有 个结点只有非空右子树。
12、按照二叉树的定义，具有 3个节点的二叉树有 ___________种。
A 3 B 4 C 5 D 6
13、深度为 5的二叉树至多有 _________个节点。
A 16 B 32 C 31 D 10
14、在一非空二叉树的中序遍历序列中，根节点的右边
A 只有右子树上的所有节点 B 只有右子树上的部分节点
C 只有左子树上的部分节点 D 只有左子树上的所有节点
15、任何一棵二叉树的叶子结点在先序、中序、后序遍历序列中的相对次序
_______
A 不发生变化 B 发生变化 C 不能确定 D 以上都不对
16、对于一个满二叉树,m个树叶,n个结点，深度为 h，则 _____
A n=h+m B h+m=2n C m=h+1 D n=2h-1
17、根据使用频率为 5个字符设计的哈夫曼编码不可能的是：
A 111,110,10,01,00 B 000,001,010,011,1
C 100,11,10,1,0 D 001,000,01,11,10
18、一棵二叉树如图，其中序遍历的序列为：
A abdgcefh B dgbaechf C gdbehfca D abcdefgh
a
b
d
g
c
e
h
f
19、以数据集 {4,5,6,7,10,12,18}为结点权值所构造的哈夫曼树为 __________
其 WPL为 ___________
20、某二叉树的节点数据采用顺序存储结构如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
E A F D H C G I B
1) 画出该二叉树
2) 写出节点值为 D的双亲结点及左右子树
3) 将此二叉树还原成森林
8题,
后序,dabec 中序,debac
c
deba
c
e
d ba
c
e
d b
a
return
12题,
1
0
1*
n
i
ibnbibn
N个结点的不相似的二叉树有
C n nn 211?
return
17题：
1
1
1
0
0
0
0 1
1
11 00
0
0 1
1
1
0
0
0
1
1
1
0
0
0
0 1
return
62
37
19
9
25
13
10
54
18
76
12
Wpl=(4+5)*4+(10+6+7)*3+(18+12)*2=165
return
19题
20题：
1）二叉树如右图：
2) D结点的双亲结点为 A，左子树为以 C
为根的子树，右子树以空。
3）还原成的森林为右图：
E
FA
HD
IGC
B
I
E
A
D
C
B
F H
G
return
上堂课例题讨论问,设一棵完全二叉树具有 1000个结点，则它有 个叶子结点，有 个度为 2的结点，有 个结点只有非空左子树，有 个结点只有非空右子树。
法 1,先 求全部叶子数。 n0＝ 489(末层 )＋ 11(k-1层 )=500个；
法 2,先求 2度结点数。 n2=255(k-2层 )＋ 244(k-1层 )=499个；
这两种方法的缺点：都要先计算树的深度 k=?log2n?＋ 1 =10;
法 3,无需求树深 k，便可快捷求出 完全二叉树的叶子数：
n0=?n/2? // 取大于 n/2的最小整数值可由二叉树性质 5轻松证明！
(编号为 i的结点，其孩子编号必为 2i和 2i+1)
①
②
④
⑧
⑤
⑨
③
⑦
…… n n
已知最后一个结点编号为 n，则其双亲（ n/2或 (n-1)/2)
肯定是最后一个非叶子结点。其编号之后的全部结点都是叶子了！
故,n0=n-n/2或 n-(n-1)/2=?n/2?
return
1、下图中,______不是完全二叉树。
A B
C
D
2、在线索二叉树中,t所指节点没有左子树的充要条件是：
A t->left==null
B t->ltag==1
C t->ltag==1 && t->left==null
D 以上都不对
3、二叉树按某种顺序线索化后，任一节点均有指向其前驱和后继的线索，这种说法：
A 正确 B 错误
4、二叉树的前序遍历中，任意一个节点均处于其孩子节点的前面，这种说法：
A 正确 B 错误
5、由于二叉树中每个节点的度最大为 2，所以二叉树是一种特殊的树，这种说法：
A 正确 B 错误
6、设高度为 h的二叉树只有度为 0和 2的节点，则此类二叉树中所包含的节点数至少为：
A 2h B 2h-1 C 2h+1 D h+1
7、下图所示二叉树的中序遍历序列是：
A abcdgef B dfebagc C dbaefcg D defbagc
a
b c
d
e
f
g
8、已知某二叉树的后序遍历序列是 dabec，中序遍历序列是 debac，它的前序遍历序列是：
A acbed B decab C deabc D cedba
9、已知某二叉树的前序遍历序列是 abdgcefh，中序遍历序列是 dgbaechf，它的后序遍历序列是：
A bdgcefha B gdbecfha C bdgaechf D gdbehfca
10、下图是有一个森林转化成的二叉树，那么森林有 ________个叶子结点。
A 4 B 5 C 6 D 7
a
b
c
d
e
f
g
h
i j
11,设一棵完全二叉树具有 1000个结点，则此完全二叉树有 个叶子结点，有 个度为 2的结点，有 个结点只有非空左子树，有 个结点只有非空右子树。
12、按照二叉树的定义，具有 3个节点的二叉树有 ___________种。
A 3 B 4 C 5 D 6
13、深度为 5的二叉树至多有 _________个节点。
A 16 B 32 C 31 D 10
14、在一非空二叉树的中序遍历序列中，根节点的右边
A 只有右子树上的所有节点 B 只有右子树上的部分节点
C 只有左子树上的部分节点 D 只有左子树上的所有节点
15、任何一棵二叉树的叶子结点在先序、中序、后序遍历序列中的相对次序
_______
A 不发生变化 B 发生变化 C 不能确定 D 以上都不对
16、对于一个满二叉树,m个树叶,n个结点，深度为 h，则 _____
A n=h+m B h+m=2n C m=h+1 D n=2h-1
17、根据使用频率为 5个字符设计的哈夫曼编码不可能的是：
A 111,110,10,01,00 B 000,001,010,011,1
C 100,11,10,1,0 D 001,000,01,11,10
18、一棵二叉树如图，其中序遍历的序列为：
A abdgcefh B dgbaechf C gdbehfca D abcdefgh
a
b
d
g
c
e
h
f
19、以数据集 {4,5,6,7,10,12,18}为结点权值所构造的哈夫曼树为 __________
其 WPL为 ___________
20、某二叉树的节点数据采用顺序存储结构如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
E A F D H C G I B
1) 画出该二叉树
2) 写出节点值为 D的双亲结点及左右子树
3) 将此二叉树还原成森林
8题,
后序,dabec 中序,debac
c
deba
c
e
d ba
c
e
d b
a
return
12题,
1
0
1*
n
i
ibnbibn
N个结点的不相似的二叉树有
C n nn 211?
return
17题：
1
1
1
0
0
0
0 1
1
11 00
0
0 1
1
1
0
0
0
1
1
1
0
0
0
0 1
return
62
37
19
9
25
13
10
54
18
76
12
Wpl=(4+5)*4+(10+6+7)*3+(18+12)*2=165
return
19题
20题：
1）二叉树如右图：
2) D结点的双亲结点为 A，左子树为以 C
为根的子树，右子树以空。
3）还原成的森林为右图：
E
FA
HD
IGC
B
I
E
A
D
C
B
F H
G
return
上堂课例题讨论问,设一棵完全二叉树具有 1000个结点，则它有 个叶子结点，有 个度为 2的结点，有 个结点只有非空左子树，有 个结点只有非空右子树。
法 1,先 求全部叶子数。 n0＝ 489(末层 )＋ 11(k-1层 )=500个；
法 2,先求 2度结点数。 n2=255(k-2层 )＋ 244(k-1层 )=499个；
这两种方法的缺点：都要先计算树的深度 k=?log2n?＋ 1 =10;
法 3,无需求树深 k，便可快捷求出 完全二叉树的叶子数：
n0=?n/2? // 取大于 n/2的最小整数值可由二叉树性质 5轻松证明！
(编号为 i的结点，其孩子编号必为 2i和 2i+1)
①
②
④
⑧
⑤
⑨
③
⑦
…… n n
已知最后一个结点编号为 n，则其双亲（ n/2或 (n-1)/2)
肯定是最后一个非叶子结点。其编号之后的全部结点都是叶子了！
故,n0=n-n/2或 n-(n-1)/2=?n/2?
return
