41. 证明，由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。设一棵二叉树的前序序列为ABDGECFH，中序序列为：DGBEAFHC 。试画出该二叉树。【浙江大学 1996 六、 (8分)】
答：因为知道先序遍历后,第一个根是唯一确定的.然后在中序遍历里这个根将它分为两个部分,第一个根的两棵子树的根也会唯一确定,依次此类推,所有子树的根都唯一确定,二叉树就是唯一的。 A
B C
D F E
G H
44．将下列由三棵树组成的森林转换为二叉树。（只要求给出转换结果）
A B C D E H K G I J M N O 【南京航空航天大学 1998 一、 (10分)】
解：
A
B D C E G F H
I K
L J
M
P N
F L P
O
46．设一棵二叉树的先序、中序遍历序列分别为
先序遍历序列： A B D F C E G H 中序遍历序列： B F D A G E H C （1） 画出这棵二叉树。
A
B
C
D E
F
G H
（2） 画出这棵二叉树的后序线索树。 0 A 0 1 B 0 0 C 1 NULL 0 D 1 0 E 0 1 F 1 1 G 1 1 H 1 后序遍历：F D B G H E C A
（3）将这棵二叉树转换成对应的树（或森林）。【南京航空航天大学 1997 二、、
A C
B
D E H
F G
47．已知一棵二叉树的对称序和后序序列如下： 对称序：GLDHBEIACJFK 后序： LGHDIEBJKFCA (1) （2分)给出这棵二叉树：
A
B C
D E F G H I J K
L
(2) （2分)转换为对应的森林： (3)
分)】 (10
G
A
B D
H
E
I
C F
J
K
L
【山东大学 1998 八、（16分）】
66．在二叉树的Ｌlink-Rlink存储表示中，引入“线索”的好处是什么？
【山东大学 1999 六、１(２分))
答：一般的二叉树大多用二叉链表来表示,线索二叉树链表是为了节约资源而出的,因为有些二叉树,不会是完全二叉树,左右指针有可能为空,这样就浪费了计算机资源,所以要把这些空的资源利用起来 空的指针就用来指向在某种遍历下的该结点的前驱和后继，这样在遍历二叉树时可有此信息直接查找到遍历次序下的前驱和后继，从而加快遍历速度。
68．对下图所示二叉树分别按前序﹑中序﹑后序遍历， 给出相应的结点序列，同时给二叉树加上中序线索。 【青岛海洋大学 1999年一、1 （5分）】
答：前序：A B D E H C F G
中序：D H E B A F C G 后序：H E D B F G C A
0 1 H D 0 A 0 0 B 1 0 C 0 0 E 1 1 F 1 1 G 1 0 70．已知一棵二叉树的中序（或中根）遍历结点排列为DGBAECHIF，后序（或后根）遍历结点排列为GDBEIHFCA，
（1）试画出该二叉树； A B C D E F G
H
I
（3） 试画出该二叉树的中序穿线（或线索）树；
1 0 D 0 B 1 0 A 0 0 C 0 0 0 E 0 H 0 0 F 0 1 G 1 1 1 I 1 （4） 试画出该二叉树（自然）对应的森林；【吉林大学 2000 一、1 （5分）】
A C F
B E H I
D G
79．给定集合{15,3,14,2,6,9,16,17}
(1)（3分）用□表示外部结点，用○表示内部结点，构造相应的huffman树：
82
49 33
16 17
20 29
9 14 15 11
6 5
2 3
(2) (2分)计算它的带权路径长度：
3*(16+17)+4*(9+14+15)+5*6+6*(2+3) = 311 (3)（3分)写出它的huffman编码： 答： 15: 111 3 : 10101 14: 110 2 : 10100 6 : 1011