数据结构-基于C++语言（微课版） 课件 1-2 哈夫曼树的定义

哈夫曼树应用背景；哈夫曼编码策略。本节目录：本节内容：哈夫曼树的应用背景层次结构-树与二叉树例哈夫曼树及应用哈夫曼树的应用背景

编码结果

AB C D00 01 10 11

码长:14bit在电文传输过程中，首先编码，然后传输。如有一段长为7个字符的电文“ABACCDA”,应如何编码？总的编码长度尽可能小,传输速度尽可能快。例哈夫曼树及应用哈夫曼树的应用背景

编码结果

AB C D01 001

0001

00001 码长:21

bit在电文传输过程中，首先编码，然后传输。如有一段长为7个字符的电文“ABACCDA”,应如何编码？总的编码长度尽可能小，传输速度尽可能快。例哈夫曼树及应用哈夫曼树的应用背景

编码结果

AB C D0 00

1 10 码长:9

bit在电文传输过程中，首先编码，然后传输。如有一段长为7个字符的电文“ABACCDA”,应如何编码？总的编码长度尽可能小，传输速度尽可能快。哈夫曼树的应用背景段电文，应该如何编码？例

电文“ABACCDA”的码长问题。 AB C D 电文“ABACCDA”码长00 01 10 11 14bit0 00 1 01 9bit01 0010001 00001 21bit编码主要策略？哈夫曼树及应用给出现概率（频率）最高的信源符号赋予最短的码字，给出现频率低的符号赋予长码，使平均码长最短。例电文编码，使得传输速度尽可快。哈夫曼树及应用哈夫曼树的应用背景字符频率A3B1C2D1

给出现概率（频率）最高的信源符号赋予最短的码字，给出现频率低的符号赋予长码，使平均码长最短。

Huffman编码为一种不等长最佳即时可译码，可通过构造huffman树（译码树）设计码字。

DavidHuffman教授1999年10月7日逝世。在他的一生中，他对于有限状态自动机，开关电路，异步过程和信号设计有杰出的贡献。

他发明的Huffman编码能够使我们通常的数据传输数量减少到最小。他的算法也广泛应用于传真机，图象压缩和计算机安全领域。但是Huffman却从未为此算法申请过专利或其它相关能够为他带来经济利益的东西，他将他全部的精力放在教学上，以他自己的话来说，“我所要带来的就是我的学生。”哈夫曼树及应用哈夫曼树中的基本概念；哈夫曼树的概念。本节目录：本节内容：哈夫曼树的定义层次结构-树与二叉树定义：具有n个叶子结点(每个结点的权值为wi)的带权路径长度（WPL）为最小的树称为Huffman树。哈夫曼树及应用路径：从一个结点到另一个结点间的分支构成两结点的路径；路径长度：路径上的分支数目称为路径长度；带权二叉树12345867

结点3到结点8的路劲长度：2结点1到结点7的路劲长度：4哈夫曼树及应用结点的带权路径长度：从根到该结点的路径路径长度与其权值的乘积；带权二叉树12345867结点6的带权路劲长度：12结点7的带权路劲长度：28哈夫曼树及应用树的带权路径长度：树中所有叶子结点的带权路径之和；通常记WPL=W1*L1+W2*L2+⋯+Wn*Ln=带权二叉树12345867=2*4+3*7+3*8+2*6=65树的带权路径长度：65三个树的带权路径长度分别为：哈夫曼树及应用哈夫曼树:树的带权路径长度最小的二叉树。(b)2845(a)8452(c)2485权值分别为2、4、5、8的4个叶子结点构造的树：例WPL=2*2+3*5+3*8+2*4=51WPL=1*2+2*4+3*5+3*8=49W