二叉树和哈夫曼树题目详解之一.doc
文本预览下载声明
已知一棵二叉树的中序序列和后序序列分别为c,b,a,e,d,h,g,j,i,f 和 c,b,e,h,j,i,g,f,d,a ，画出这棵二叉树，并写出其先序遍历序列 ，然后画出其先序线索化后的二叉链表。
给定一组数列（10,18,16,25,6, 9,16）分别代表字符A,B,C,D,E,F,G出现的频度，试画出哈夫曼树，给出各字符的编码值
答案见第二页
1.解：该二叉树的树形结构如下：
该二叉树的先序序列为：abcdefghij;
该二叉树先序线索化后的二叉链表如下：
2．该组数列的哈夫曼树结构如下：
途中各个字母的编码分别为：
A:110 B:10 C:000 D:01
E:1110 F:1111 G:001
aaaaaa
b
c
f
h
g
j
i
d
e
1 h 1
1 j 1
0 g 0
1 i 1
1 e 1
0 f 1
1 c 1
0 b 1
0 d 0
0 a 0
1000
57
32
43
25
15
25
18
16
16
9
6
10
0
0
0
D
1
0
0
1
1
1
1
1
A
0
B
F
E
G
C
显示全部