数据结构-从概念到C++实现（第4版）课件 4-7最优二叉树

4-7最优二叉树v第四章树和二叉树哈夫曼算法学什么？哈夫曼编码最优二叉树（哈夫曼树）的基本概念最优二叉树叶子结点的权值：对叶子结点赋予的一个有意义的数值量二叉树的带权路径长度：从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和取决于具体问题第k个叶子的权值从根结点到第k个叶子的路径长度最优二叉树（哈夫曼树）：给定一组具有确定权值的叶子结点，带权路径长度最小的二叉树323428324552345432最优二叉树最优二叉树有什么特点?（1）权值越大的叶子结点越靠近根结点（2）只有度为0和度为2的结点，不存在度为1的结点4-7-1哈夫曼算法v第四章树和二叉树哈夫曼算法【问题】给定一组权值，构造最优二叉树1.初始化：由n个权值构造n棵只有一个根结点的二叉树，得到一个二叉树集合F＝{T1，T2，…，Tn}；2.重复下述操作，直到集合F中只剩下一棵二叉树

2.1选取与合并：在F中选取根结点的权值最小的两棵二叉树分别作为左右子树构造一棵新的二叉树，这棵新二叉树的根结点的权值为其左右子树根结点的权值之和；

2.2删除与加入：在F中删除作为左右子树的两棵二叉树，并将新建立的二叉树加入到F中；【想法——哈夫曼算法的基本思想】例给定权值集合{2，4，5，3}初始化选取与合并删除与加入245323

54523

5运行实例23

545

923

545

914【算法——数据表示】如何存储哈夫曼树呢？23

545

914采用数组还是链表呢？

n

个叶子结点合并

n-1次n-1个分支结点哈夫曼树共有2n-1个结点设数组huffTree[2n-1]须存储哪些关系呢？选取根结点权值最小的二叉树存储parent信息作为左右子树进行合并存储lchild和rchild信息weightlchildrchildparent哈夫曼算法23

545

914weightlchildrchildparentstructElemType{

intweight;/*假定权值为整数*/

intparent,lchild,rchild;};函数原型：voidHuffmanTree(ElemTypehuffTree[],intw[],intn)哈夫曼算法【算法——数据表示】如何存储哈夫曼树呢？【算法——数据处理过程】-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1例给定权值集合{2，4，5，3}24530123456weightparentlchildrchildfor(i=0;i<2*n-1;i++){huffTree[i].parent=-1;huffTree[i].lchild=-1;huffTree[i].rchild=-1;}算法描述：哈夫曼算法-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-124530123456weightparentlchildrchildfor(i=0;i<n;i++)huffTree[i].weight=w[i];算法描述：例给定权值集合{2，4，5，3}哈夫曼算法【算法——数据处理过程】2453-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-124530123456weightparentlchildrchild4523

5i1i25huffTree[k].weight=huffTree[i1].weight+huffTree[i2].weight;算法描述：k例给定权值集合{2，4，5，3}哈夫曼算法【算法——数据处理过程】2453-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1245324530123456weightparentlchildrchild4523

5i1i250344huffTree[i1].parent=k;huffTree[i2].parent=k;huffTree[k].lchild=i1;huffTree[k].rchild=i2;算法描述：k例给定权值集合{2，4，5，3}哈夫曼算法【算法——数据处理过程】【程序】voidHuffmanTree(ElemTypehuffTree[],intw[],intn){inti,k,i1,i2;

}for(i=0;i<2*n-1;i++)/*初始化，所有结点均没有双亲和孩子*/{huffTree[i].parent=-1;huffTree[i].lchild=-1;huffTree[i].rchild=-1;}for(k=n;k<2*n-1;k++)/*n-1次合并*/{

Select(huffTree,i1,i2);/*权值最小的两个根结点下标为i1和i2*/huffTree[k].weight=huffTree[i1].weight+huffTree[i2].weight;huffTree[i1].parent=k;huffTree[i2].parent=k;huffTree[k].lchild=i1;huffTree[k].rchild=i2;}for(i=0;i<n;i++)/*构造n棵只含有根结点的二叉树*/huffTree[i].weight=w[i];算法实现4-7-2哈夫曼编码v第四章树和二叉树编码编码：给每一个对象标记一个二进制位串来表示一组对象等长编码：用长度相等的二进制位串表示一组对象酸甜

01酸甜苦辣00011011酸

甜苦辣

咸麻000

001

010

011

100101编码的目的是什么?数字化编码效率取决于编码长度如果每个对象的使用频率不等，如何获得较高的编码效率市区出生日期顺序校验身份证号码不等长编码：表示一组对象的二进制位串的长度不相等设计不等长编码时，必须考虑解码的唯一性

字符串：AABACD

编码：00100110ABCDE

一组对象3525151510

使用频率01011011

不等长编码前缀（无歧义）编码保证了在解码时不会有多种可能前缀无歧义编码（简称前缀编码）：在一组编码中，任一编码都不是其它任何编码的前缀解码

00100110

00100110

解码：哈夫曼编码如何设计一个编码效率最高的前缀编码呢?哈夫曼编码例一组字符{A,B,C,D,E,F,G}出现的频率分别是{9,11,5,7,8,2,3}，设计最经济的编码方案。00000011111195231187ABDCEFG哈夫曼编码方案：A：00B：10C：010D：110E：111F：0110G：011151510261945等长编码的长度：3哈夫曼编码的平均长度：(2×9+3×5+4×2+4×3+2×11+3×7+3×8)/45=2.67该编码方案的压缩比是多少?(3-2.