1、6.8 哈 夫 曼 树 与哈 夫 曼 编 码l 最优树的定义l 如何构造最优树l 前缀编码l 赫夫曼编码一、最优树的定义树的路径长度 定义为：树中每个结点的路径长度之和。结点的路径长度 定义为：从根结点到该结点的路径上分支的数目。树的带权路径长度 定义为：树中所有叶子 结点的带权路径长度 之和WPL(T) = wklk (对所有叶子结点 )。假设有 n个权值 w1,w2, wn，构造一棵有 n个叶子结点的二叉树，每个叶子结点带权为 Wi，则其中 带权路径长度取最小值 的二叉树称为 “最优树 ”。例如：2 7 9 7 5492WPL(T)= 72+52+23+43+92 =60WPL(T)= 7
2、4+94+53+42+21 =89 54根据给定的 n 个权值 w1, w2, , wn，构造 n 棵二叉树的集合F = T1, T2, , Tn，其中每棵二叉树中均只含一个带权值 为 wi 的根结点 ， 其左、右子树为空树；二、如何构造最优树(1) (赫夫曼算法 ) 以二叉树为例：在 F 中选取其根结点的权值为最小的两棵二叉树，分别作为左、 右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和；(2)从 F中删去这两棵树，同时加入刚生成的新树；重复 (2) 和 (3) 两步，直至 F 中只含一棵树为止。(3)(4)9例如 : 已知权值 W= 5, 6, 2,
3、 9, 7 5 6 2 75 276 9 76 71395 276 71395 2795 27166 7132900 0011 1100 01 10110 111从根结点到叶子结点的路径上分支字符组成的字符串，可以作为每个叶子结点编码。约定左分支表示字符 0 ，右分支表示字符 1 。若要设计不等长的编码，则必须 任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀 ， 这种编码称为前缀编码。三、前缀编码以传送的电文为例比较等长编码和不等长编码方法：一、 等长编码： 电文中所需传送的字符有 A、 B、 C、 D，编码分别为 00、 01、 10、 11，若要发送 ABACCDA 电文，则以字符串 00010010101100 发送，根据字符对应的编码，在接收端能知道发送的电文为 ABACCDA 。二、 不等长编码： 当 A、 B、 C、 D的编码分别为 0、 00、 1、 10，要发送上述电文以电文 ABACCDA ，相应的字符串为 000011100 ，在接收端，对于子串 0000 的译法就有多种，可以是 AAAA 、 BB 、 ABA 、 BAA 等等。
