15
例：证明：一棵二叉树的前序序列和中序序 列可以唯一的确定这棵二叉树。
用归纳法证明： 1、当 n = 1时，结论显然成立； 2、假定当 n <= k 时，结论成立； 3、当 n = k + 1 时，假定前序序列为和中序序列 分别为： {a1，…，am} 和 {b1， … ，bm}
16
如 中 序 序 列 中 与 前 序 序 列 a1 相 同 的 元 素 为 b j 。 j =1时，二叉树无左子树，由 {a2，…，am} 和
先举例！
3
例1：设有4个字符d,i,a,n，出现的频度分别为7,5,2, 4，
怎样编码才能使它们组成的报文在网络中传得最快？ 法1：等长编码。例如用二进制编码来实现。 取 d=00，i=01，a=10，n=11
法2：不等长编码，例如用哈夫曼编码来实现。 取 d=0; i=10, a=110, n=111 最快的编码是哪个？是非等长的Huffman码！
提示2：霍夫曼树的存储结构可采用顺序存储结构： 将整个霍夫曼树的结点存储在一个数组中：HT[1..n]; 将结点的编码存储在HC[1..n]中。 提示3：霍夫曼树如何构造？构造好之后又如何求得 各结点对应的霍夫曼编码？——算法参见教材P147。
参考 实验二补充材料中的方案二程序； 资料 喻信星空FTP网站上的“数据结构”演示程序
注：若圆满实现了此方案，平时成绩将以满分计。
字符 空格 频度 186 a 64 b 13 c 22 d 32
e
103
f 21
g 15
h 47
i 57
字符 频度
字符 频度
j 1
k 5
u 23
l 32
v 8
m 20
w 18
n 57
x 1
o 63
y 16
p 15
z 1
q 1
r 48
s 51
t
80
11
提示1：霍夫曼树中各结点的结构可以定义为如下 5个分量： char weight parent lchild Rchild
——将 Huffman树 与 Huffman编码
0 d 1
挂钩
0
i 0 a
1
1 n
Huffman编码结果：d=0, i=10, a=110, WPL=1bit×7＋2bit×5+3bit(2+4)=35
n=111
特点：每一码都不是另一码的前缀，绝不会错译! 称为前缀码
6
霍夫曼编码的基本思想是：概率大的字符用短码，概率小的用 长码。由于霍夫曼树的WPL最小，说明编码所需要的比特数最 少。这种编码已广泛应用于网络通信中。
怎样实现Huffman编码？先要构造Huffman树！
4
构造Huffman树的步骤：
操作要点1：对权值的合并、删除与替换
——在权值集合{7,5,2,4}中，总是合并当前值最小的两个权
注：方框表示外结点（叶子，字符对应的权值）， 圆框表示内结点（合并后的权值）。
5
操作要点2：按左0右1对Huffman树的所有分支编号！
6.5
Huffman树及其应用
b d e
a c f g
一、最优二叉树（霍夫曼树）
预备知识：若干术语 路 径： 由一结点到另一结点间的分支所构成
路径长度： 路径上的分支数目
a→e的路径长度＝ 2
树长度＝ 10 树的路径长度：从树根到每一结点的路径长度之和。 带权路径长度：结点到根的路径长度与结点上权的乘积 树中所有叶子结点的带权路径长度之和 树的带权路径长度： 霍 夫 曼 树： 带权路径长度最小的树。
解：先将概率放大100倍，以方便构造哈夫曼树。 权值集合 w={7, 19, 2, 6, 32, 3, 21, 10}， 按哈夫曼树构造规则（合并、删除、替换），可得到哈夫曼树。
7
为清晰起见，重新排序为: w={2, × 6, 7, 10, 19, 21, 32} × 3, w1={5, × 7, 10, 19, 21, 32} × 6, w2={7, 10, 11, 19, 21, 32} × × w3={11, 17, 19, 21, 32} × × w4={19, 21, 28, 32} × × w5={28,32,40} ×× w6={40,60} × × w7={100} 哈夫曼树 19 b
{b2， … ，bm} 可以唯一的确定二叉树的右子树；
j= m时，二叉树无右子树，由 {a2，…，am} 和
{b1， … ，bm-1} 可以唯一的确定二叉树的左子树；
如2<=j<=m-1，则子序列 {a2，…，aj} 和 {b1， …
，bj-1}唯一的确定二叉树的左子树；子序列{aj+1，
…，am} 和 {bj+1， … ，bm}唯一的确定二叉树的右
例2（严题集6.26③）：假设用于通信的电文仅由8个字母
{a, b, c, d, e, f, g, h} 构成，它们在电文中出现的概率分别 为{ 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10}， 试为这8个字母设计哈夫曼编码。如果用0～7的二进制编码方 案又如何？
子树
17
{a1，a2 ， …，aj， aj+1， …，am}
个数相同
{b1，… ，bj-1，bj ，bj+1，… ，bm }
唯一的确定左子树
唯一的确定右子树
18
100
40
21 32 g e 17 7 a
60
28 11 10 h 6 d 2 c 5 3 f
8
对应的哈夫曼编码（左0右1）：
符 编码 频率 符 编码 频率
100
a
b
1100
00
0.07
0.19
a
b
000
001
0.07
0 40
1
60 0 1 1 28 21 32 g e 0 1 17 11 0 1 0 1 5 7 10 6 a d 0 1 h 2 3 f c
1
Huffman树简介：
Weighted Path Length
树的带权路径长度如何计算？ WPL = 哈夫曼树则是：WPL 最小的树。
w kl k
k=1
n
经典之例：
2 c 7 a 5 2 b c 4 d
Huffman树
7 a
4 d
7 a (b)
5 b
5 b
2 c (c)
4 d
(a)
WPL=36
12
二叉树小结
1、定义和性质 树
顺序结构
2、存储结构
链式结构
二叉链表
森林
二叉树
先序遍历
三叉链表
3、遍历
中序遍历
后序遍历
先序线索树
中序线索树
4、线索化：线索树 霍夫曼树
后序线索树
霍夫曼编码
13
附：中序遍历迭代算法(利用堆栈)
void iter_inorder(tree_pointer node) { int top= -1; /* initialize stack */ tree_pointer stack[MAX_STACK_SIZE]; for (;;) { for (; node; node=node->left_child) add(&top, node);/* add to stack */ node= delete(&top); /* delete from stack */ if (!node) break; /* empty stack */ printf(“%D”, node->data); node = node->right_child; } } 时间复杂度O(n)
=1.44+0.92+0.25=2.61
二进制码 WPL＝3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3
9
另一26个英文字母，其出 现频度如下表所示。 要求编程实现： 先建哈夫曼树，再利用此树对报文“This program is my favorite”进行编码和译码。
14
附：层序遍历算法(利用队列)
void level_order(tree_pointer ptr) /* level order tree traversal */ { +*E*D /CAB int front = rear = 0; tree_pointer queue[MAX_QUEUE_SIZE]; if (!ptr) return; /* empty queue */ addq(front, &rear, ptr); for (;;) { ptr = deleteq(&front, rear);
WPL=46
WPL= 35
2
构造霍夫曼树的基本思想： 权值大的结点用短路径，权值小的结点用长路径。 构造Huffman树的步骤（即Huffman算法）：
(1) 由给定的 n 个权值{w0, w1, w2, …, wn-1}，构造具有 n 棵扩充 二叉树的森林F = { T0, T1, T2, …, Tn-1 }，其中每一棵扩充二叉树 Ti 只有一个带有权值 wi 的根结点，其左、右子树均为空。 (2) 重复以下步骤, 直到 F 中仅剩下一棵树为止： ① 在 F 中选取两棵根结点的权值最小的扩充二叉树, 做为左、 右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为 其左、右子树上根结点的权值之和。 ② 在 F 中删去这两棵二叉树。 ③ 把新的二叉树加入 F。
c
d
11110
1110
0.02
0.06