平
f均搜索长度是多少？答案：
ASLsucc112234717
7
5、在结点个数为
1的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？
答案：结点个数为
时，高度最小的树的高度为1，有2层；它有
1个叶结点，1个分支结点；高度最大的树的高度为
1有
层；它有1个叶结点，
1个分支结点。
6、一棵高度为h的满k叉树有如下性质第h层上的结点都是叶结点其余各层上每个结点都有k棵非空子树如果按层次自顶向下同一层自左向右顺序从1开始对全部结点进行编号试问
1各层的结点个数是多少2编号为i的结点的父结点若存在的编号是多少3编号为i的结点的第m个孩子结点若存在的编号是多少
f4编号为i的结点有右兄弟的条件是什么其右兄弟结点的编号是多少
5若结点个数为
则高度h是
的什么函数关系
答案：
（1）各层的结点个数是kii012h
（2）编号为i的结点的父结点若存在的编号是└ik2k」
（3）编号为i的结点的第m个孩子结点若存在的编号是i1km1
（4）当i1k0时有右兄弟，右兄弟的编号为i1
（5）若结点个数为
，则高度h和
的关
系为：hlogk
k111h1

0时
9、题目：11、将下面的森林变换成二叉树（7分）。
A
B
C
D
E
G
F
H
I
J
K
f答案：
A
B
E
C
F
G
D
H
I
J
K
10、将算术表达式abcdefgh转化为二叉树。（7分）
答案：



f
h
g

a
b

c
d
e
12、将给定的图简化为最小的生成树，要
求从顶点1出发。（7分）
f8
1
5
32
315
10
124
6
57
92
6
7
答案
15
32
315
742
5
6
6
7
13、某子系统在通信联络中只可能出现8种字符，其出现的概率分别为005，029，007，008，014，023，003，011试设计赫夫曼编码。
答案：
为方便起见，设各种字符的权值w529781423311。因为
8，所以要构造的赫夫曼树共有m2
128115个结点。生成的赫夫曼树为下图所示：
f00
1
1
0
1
230
290
1
1
110
140
1
1
5
3
7
8
赫夫曼编码为：概率为023的字符编码为：00
概率为011的字符编码为：010
概率为005的字符编码为：0110
概率为003的字符编码为：0111
概率为029的字符编码为：10
为：110
概率为014的字符编码
为：1110
概率为007的字符编码
为：1111
概率为008的字符编码
f14、已知一棵二叉树的前序遍历的结果是
ABECDFGHIJ中序遍历的结果是EBCDAFHIGJ试画出这棵二叉树，并给出这棵二叉树的后
序遍历序列r