数据结构6和二叉树

第六章

树和二叉树哈夫曼树及应用哈夫曼树及构造哈夫曼编码6.7哈夫曼树及应用6.7.1

哈夫曼树及构造1

哈夫曼树的概念路径：从一个祖先结点到子孙结点之间的分支构成这两个结点间的路径；路径长度：路径上的分支数目称为路径长度；结点的权：根据应用的需要可以给树的结点赋权值；结点的带权路径长度：从根到该结点的路径长度与该结点权的乘积；树的带权路径长度=树中所有叶子结点的带权路径之和；通常记作WPL=

wi

·

Li哈夫曼树：假设有n个权值(w1

,

w2

,

…

,

wn

)，构造有n个叶子结点的二叉树，每个叶子结点有一个wi

作为它的权值。则带权路径长度最小的二叉树称为哈夫曼树。6.7哈夫曼树及应用2应用举例在求得某些判定问题时，利用哈夫曼树获得最佳判定算法。例编制一个将百分制转换成五分制的程序。最直观的方法是利用if语句来的实现。可用二叉树描述判定过程。参见课本P145

图6.23(a)。如果这个程序很不经常使用，或要转换的分数不多，不必考虑该程序效率，我们可以按照这个流程编程。可是如果该程序经常要使用或数据量很大。比如对北京市几十万小学生的分数进行转换，在这种情况下，要考虑转换程序的效率。设有10000个百分制分数要转换，设学生成绩在5个等级以上的分布如下：分数0-5960-6970-7980-8990-100比例数0.050.150.400.300.106.7哈夫曼树及应用403060155

101530按图的判定过程，转换一个分数所需的比较次数=从根到对应结点的路径长度。转换10000个分数所需的总比较次数=10000（0.05

·

1+0.15

·

2+0.4

·

3+0.3

·

4+0.1

·

4）若将学生成绩在5个等级以上的分布比例看作描述判定过程二叉树叶子结颠点权值，（0.05

·

1+0.15

·

2

+0.4

·

3+0.3

·

4+0.1

·

4）正是该二叉树的带权路径长度。可见要想获得效率较高的转换程序，可构造以分数的分布比例为权值的哈夫曼树。1006.7哈夫曼树及应用3

哈夫曼树的构造构造哈夫曼树的步骤：根据给定的n个权值，构造n棵只有一个根结点的二叉树，n个权值分 别是这些二叉树根结点的权。设F是由这n棵二叉树构成的集合在F中选取两棵根结点树值最小的树作为左、右子树，构造一颗新的 二叉树，置新二叉树根的权值=左、右子树根结点权值之和；从F中删除这两颗树，并将新树加入F；重复2、3，直到F中只含一颗树为止；6.7哈夫曼树及应用403060155

1015303060

40155

101530例：构造以W=（5，15，40，30，10）为权的哈夫曼树。1005

15

40

30

105

10

15

40

301540

3030155

10156.7哈夫曼树及应用6.7.2哈夫曼编码哈夫曼树除了能求解最优判定问题解，还用于其他一些最优问题的求解。这里介绍用哈夫曼树求解数据的二进制编码。在进行数据通讯时，涉及数据编码问题。所谓数据编码就是数据与二进制字符串的转换。例如：邮局发电报，发送方将原文转换成二进制字符串，接收方将二进制字符串还原成原文。原文

电文（二进制字符串）

原文例

要传输的原文为ABACCDA设ABCD的编码为A；00B；01C：10D：11发送方：将ABACCDA转换成00010010101100接收方：将

00010010101100

还原为

ABACCDA6.7哈夫曼树及应用ab

cdgfeh在数据输传时，为省节费用总希望传输的二进制串尽可能短。可利用二叉树设计不等长编码：例

某通讯系统只使用8种字符a、b、c、d、e、f、g、h，其使用频率分别为0.05,0.29,0.07,0.08, 0.14,0.23,

0.03,0.11，利用二叉树设计一种不等长编码：构造以a、b、c、d、e、f、g、h为叶子结点的二叉树；将该二叉树所有左分枝标记1，所有右分枝标记0；从根到叶子结点路径上标记作为叶子结点所对应字符的编码；a:

0000b:0001c:0010d:0011e:010f:011g:10h:116.7哈夫曼树及应用应用中每个字符的使用频率是不一样的。显然，为使传输的二进制串尽可能的短，使用频率高的字符用较短编码，使用频率低的字符用较长编码电文总长=原文中字符总数（字符x使用频率字符x编码长度）为设计电文总长最短编码，可通过构造以字符使用频率作为权值的哈夫曼树实现。如何得到使二进制串总长最短编码6.7哈夫曼树及应用a:0110b:10c:1110d:1111e:110f:00g:0111h:010例

某通讯系统只使用8种字符a、b、c、d、e、f、g、h，其使用频率分别为0.05,0.29,0.07,0.08, 0.14,0.23,

0.03,0.11。构造以字符使用频率作为权值的哈夫曼树。，将权值取为整数w=(5,29,7,8,14,23,3,11)，按哈夫曼算法构造的一棵哈夫曼树如下：对应字符的编码10042

5823

19

29

2911

8

14

155

3

7

86.7哈夫曼树及应用2．构造哈夫曼树的算法输入：n个权值结果：哈夫曼树设用一维数组W存储n个权值，用静态三叉链表HT存储哈夫曼树存储哈夫曼树的静态三叉链表类型定义typedef

struct

{unsigned

int

weight;unsigned

int

parent,

lchild,

rchild;}HTNode,*HuffmanTree;

//动态分配数组存储赫夫曼树weight

parent

lchild

rchildHTNode类型的结构变量6.7哈夫曼树及应用w

p

lch

rch01234567891011121314155000290007000800014000230003000110008111715123419138929145104215611581521210001314哈夫曼树哈夫曼树对应的静态三叉链表w,p,lch,rch是

weight,parent,lchild,rchild的缩写291958421001587358112314296.7哈夫曼树及应用哈夫曼算法void

HuffmanTree(HuffmanTree

&HT, int

*

w,

int

n){//w

存放n

个字符的权值（均>0），构造赫夫曼树HTif

(n<=1)

return;m=2*

n-1;HT=(HuffmanTree)malloc(m+1)*

sizeof(HTNode);

//为哈夫曼树分配存储//空间for

(p=HT,i=1;

i<=n;

++i,++p,++w) *

p={*w,0,0,0};

//用给定的n个权//值，构造n棵只有一个根结点的二叉树for(;i<m;++i;++p){

//按构造哈夫曼树的步骤2、3、4，建哈夫曼树//在HT[1..i-1]选择parent为0且weight最小的两个结点，其序号分别为s1和s2。Select(HT,

i-1,

s1,

s2);HT[s1].

parent

=i;

HT[s2].parent=i;

//HT[i]存放新子树的根结点，HT[i].lchild=s1;

HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;6.7哈夫曼树及应用例：用哈夫曼算法构造以w=(5,29,7,8,14,23,3,11)为权值的哈夫曼树529781423311012345678Wwplchrch01234567891011121314155000290007000800014000230003000110008111715123419138929145104215611581521210001314哈夫曼树对应的静态三叉链表HTHT算法原始数据算法结果数据权值数组W6.7哈夫曼树及应用wplchrch0123456789101112131415为哈夫曼树分配存储空间哈夫曼算法主要步骤图示HT6.7哈夫曼树及应用0150002290003700048000514000623000730008110009101112131415w

p

lch

rchHT算法的第一个

FOR循环的执行结果8棵只有一个结点的二叉树523

3

1129

7

8

14HT算法的第二个

FOR循环的执行结果10042

5823

19

29

2911

8

14

155

3

7

8静态三叉链表HT对应的哈夫曼树构造哈夫曼树的过程中，新生成的结点6.7哈夫曼树及应用w

p

lch

rch01234567891011121314155

0

0

029

0

0

07

0

0

08

0

0