A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

分类与判定树
这个小节有个比较重要的概念,就是用于描述分类过程的二叉树称为判定树 记住即可
哈夫曼树与哈夫曼算法
首先了解一下什么是哈夫曼树
给定一组值p~1~,...p~k~,如何构造一棵有k个叶子且分别以这些值为权的判定树,使得其平均比较次数最小。满足上述条件的判定树称为哈夫曼树。
哈夫曼率先给出了一个求哈夫曼树的简单而有效的方法,称为哈夫曼算法。
非形式的描述如下
  • 给定的值{p~1~,p~2~,...,p~k~}构造森林{T~1~,T~2~,T~k~},其中每个T~i~为一棵只有根结点且其权为p~i~的二叉树。
  • 从F中选取根结点的权最小的两棵二叉树T~i~和T~j~,构造一棵分别以T~i~和T~j~为左、右子树的新的二叉树T~h~,置T~h~根结点的权为T~i~,T~j~根结点的权值之和。
  • 从F中删去T~i~和T~j~,并将T~h~加入F,若F中仍多于一棵二叉树,则返回第二步,直到F中只含有一棵二叉树为止,这棵树就是哈夫曼树。
参照案例
重点来了,看真题,请记住==哈夫曼树不唯一、时刻考虑权值最小==
真题参考
动态展示这道题目的解答方法,已经去掉了结点之间的连线
哈夫曼编码
哈夫曼编码比较简单,就是将某棵二叉树中每个结点的左分支标志“0”,右分支标志“1”,这样,从根到每个叶结点形成“0”/“1”序列,将该序列作为叶结点对应字符的编码,由此得到的二进制编码称为哈夫曼编码。
请读题
设某通讯系统中一个待传输的文本有6个不同字符,它们的出现频率分别是0.5,0.8,1.4,2.2,2.3,2.8,试设计哈夫曼编码
教材中给出了树和哈夫曼编码,直接看一下即可
出现频率为0.5的字符编码为1000
出现频率为0.8的字符编码为1001
出现频率为1.4的字符编码为101
出现频率为2.2的字符编码为00
出现频率为2.3的字符编码为01
出现频率为2.8的字符编码为11

1 个回复

倒序浏览
有任何问题欢迎添加学姐微信
DKA-2018
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马