序20．按层次21．
222．邻接矩阵23．2
124．
125．栈
一次
邻接表
三、综合题1．写出如下图所示的二叉树的先序、中序和后序遍历序列。答：二叉树的定义是递归的，所以，一棵二叉树可看作由根结点，左子树和右子树这三个基本部分组成，即依次遍历整个二叉树，又左子树或者右子树又可看作一棵二叉树并继续分为根结点、左子树和右子树三个部分…，这样划分一直进行到树叶结点。1先序为“根左右”，先序序列为：fdbacegihl2中序为“左根右”，中序序列为：abcdefghij3后序为“左右根”，后序序列为：acbedhjigf2．已知某二叉树的先序遍历结果是：A，B，D，G，C，E，H，L，I，K，M，F和J，它的中序遍历结果是：G，D，B，A，L，H，E，K，I，M，C，F和J，请画出这棵二叉树，并写出该该二叉树后续遍历的结果。（1）二叉树图形表示如下：
A
B
C
D
E
F
G
H
I
J
L
K
M
（2）该二叉树后序遍历的结果是：G、D、B、L、H、K、M、I、E、J、F、C和A。3．答⑴已知深度为k的二叉树最多有2k1个结点K≥1，2918922101，故树的高度为10⑵对于完全二叉树来说，度为1的结点只能是0或1因为
0
1
2和
0
21得：设
10，892
00
22
21得
2不为整数出错设
11，892
01
22
22得
2445→
0
21446叶子结点数为446。⑶由⑵得单支结点数为1⑷对于
个结点的完全二叉树，最后一个树叶结点，即序号为
的叶结点其双亲结点一个非终端结点，
8
即为最后
f序号为8922446。4．（1）先序序列和中序序列相同的二叉树为空树或任一结点均无左孩子的非空二叉树（2）中序和后序序列相同的二叉树为空树或任一结点均无右孩子的非空二叉树（3）先序和后序序列相同的二叉树为空树或仅有一个结点5．（1）哈夫曼树如图B4所示。
01
0015D08E1
1130I010A
0
1201B1
05C02F
7H
13G
图B4
（2）其带权路径长度WPL值为270。（3）每个字符的哈夫曼编码为：A100B11C1010D000E0010F10110G10111H0011I016．答（1）深度优先遍历：v1v2v3v8v5v7v4v6广度优先遍历：v1v2v4v6v3v5v7v82G的拓扑序列为：v1v2v4v6v5v5v3v5v7v83最短路径为：v1v2v5v7v87．①g1的图示和图g1的邻接表如下图所示。
图G②图G的邻接矩阵如下图所示：
9
fv1
21412
44523
53
01010
10011
00011
11100
01100
v2v3v4v5
图G的邻接矩阵
图G的邻接表
③V1、V2、V3、V4、V5的度分别为：2，3，2，3，2四、程序分析题11retur
c112NodeLevelBTrightX3c21retur
c212．1forj0j
j
2dfstreeGAj

五、算法设计r