数据结构 求哈弗曼编码已知某系统在通信联络中只可能出现八种字符,其出现的概率分别是0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,试构造一棵哈夫曼树.并得出哈夫曼编码.有两种做法,但是求得的树不
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/28 20:51:17
![数据结构 求哈弗曼编码已知某系统在通信联络中只可能出现八种字符,其出现的概率分别是0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,试构造一棵哈夫曼树.并得出哈夫曼编码.有两种做法,但是求得的树不](/uploads/image/z/13184274-66-4.jpg?t=%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84+%E6%B1%82%E5%93%88%E5%BC%97%E6%9B%BC%E7%BC%96%E7%A0%81%E5%B7%B2%E7%9F%A5%E6%9F%90%E7%B3%BB%E7%BB%9F%E5%9C%A8%E9%80%9A%E4%BF%A1%E8%81%94%E7%BB%9C%E4%B8%AD%E5%8F%AA%E5%8F%AF%E8%83%BD%E5%87%BA%E7%8E%B0%E5%85%AB%E7%A7%8D%E5%AD%97%E7%AC%A6%2C%E5%85%B6%E5%87%BA%E7%8E%B0%E7%9A%84%E6%A6%82%E7%8E%87%E5%88%86%E5%88%AB%E6%98%AF0.05%2C0.29%2C0.07%2C0.08%2C0.14%2C0.23%2C0.03%2C0.11%2C%E8%AF%95%E6%9E%84%E9%80%A0%E4%B8%80%E6%A3%B5%E5%93%88%E5%A4%AB%E6%9B%BC%E6%A0%91.%E5%B9%B6%E5%BE%97%E5%87%BA%E5%93%88%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81.%E6%9C%89%E4%B8%A4%E7%A7%8D%E5%81%9A%E6%B3%95%2C%E4%BD%86%E6%98%AF%E6%B1%82%E5%BE%97%E7%9A%84%E6%A0%91%E4%B8%8D)
数据结构 求哈弗曼编码已知某系统在通信联络中只可能出现八种字符,其出现的概率分别是0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,试构造一棵哈夫曼树.并得出哈夫曼编码.有两种做法,但是求得的树不
数据结构 求哈弗曼编码
已知某系统在通信联络中只可能出现八种字符,其出现的概率分别是0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,试构造一棵哈夫曼树.并得出哈夫曼编码.
有两种做法,但是求得的树不一样,大家看看哪种是对的
NO.1
no2_________________(1.00)___________________
________________/______\__________________
___________(0.42)______(0.58)_____________
___________/____\______/____\_____________
_______(0.19)_(0.23)_(0.29)_(0.29)________
_______/____\_______________/____\________
____(0.08)_(0.11)_______(0.14)_(0.15)_____
____/____\_____________________/____\_____
_(0.03)_(0.05)______________(0.07)_(0.08)_
为了方便找最小的,可以对它进行排序:
0.03,0.05,0.07,0.08,0.11,0.14,0.23,0.29
最小的两个是:0.03+0.05=0.08
再排序:
0.07,0.08,(0.08),0.11,0.14,0.23,0.29
最小的两个是:0.07+0.08=0.15
这里有两个0.08,用不同的0.08建树有不同的结果而且那个最短路径也不同
数据结构 求哈弗曼编码已知某系统在通信联络中只可能出现八种字符,其出现的概率分别是0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,试构造一棵哈夫曼树.并得出哈夫曼编码.有两种做法,但是求得的树不
这两种方法从表面上看都没有问题,第一种最短路径是279,第二种是271,显然第二种路径要短,所以我们肯定第二种是对的.我们在从本质上分析,哈弗曼数最直观的表象是权值越小的叶子离根越近,所以当一个结点和一个叶子的权值一样时就应该选取叶子与那个结点先组合.