文档介绍：哈夫曼树与哈夫曼编码
1. 哈夫曼树与哈夫曼编码
2. 回溯策略
3. 章末复****br/> 4. 例题讲解
5. 课堂练****br/> 6. 作业
哈夫曼树与哈夫曼编码
树的路径长度定义为:
最优二叉树的定义
从根结点到该结点的路径上分支的数目。
结点的路径长度定义为:
树中每个结点的路径长度之和。
最优二叉树的定义
A
C
B
E
D
如图所示树:
树的路径长度为5
最优二叉树的定义
树的带权路径长度定义为:
树中所有叶子结点的带权路径长度之和
WPL(T) = wklk (对所有叶子结点)
n
k=1
最优二叉树的定义
A
B
C
H
I
D
E
F
G
7
5
2
4
9
WPL(T)= 7 × 2+5 × 2+2 × 3+4 × 3+9 × 2 =60
最优二叉树的定义
A
B
C
H
I
D
E
F
G
7
4
9
5
2
WPL(T)= 7 × 4+9 × 4+5 × 3+4 × 2+2 × 1=89
最优二叉树的定义
最优二叉树定义为:
带权路径长度WPL最小的二叉树,又称为哈夫曼树。
赫夫曼树
(赫夫曼算法)以二叉树为例:
个权值{w1, w2, …, wn},构造n 棵二叉树的集合F = {T1, T2, …, Tn},
其中每棵二叉树中均只含一个带权值为wi 的根结点,其左、右子树为空树;
F 中选取其根结点的权值为最小的两棵二叉树,分别作为左、右子树构造一棵新的二叉树,并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;
赫夫曼树