数据结构3 特殊二叉树

1. 排序二叉树、最优二叉树、线索二叉树、平衡二叉树等是二叉树的特殊形式,分别有各自的用途,排序二叉树用于快速查找、最优二叉树用于无损压缩编码、线索二叉树通过保存结点的前驱后继信息以方便遍历、平衡二叉树通过改进排序二叉树提高了其整体查找效率。

2.对于最优二叉树用于压缩编码,非常不解树是如何用于编码的。查阅相关文章后有了大概的了解,最优二叉树是带权路径长度最短的二叉树。结点的带权路径长度即权值与路径的乘积。关于其在编码方面的应用,有一篇博文介绍地比较直观(http://blog.csdn.net/wo16fafafa/article/details/52420007),比如要传送内容为”abc bcd cdd ddd d”的报文,其中字母a,b,c,d出现的次数分别为1,2,3,7。在数据通信中,需要将传送的文字转换成二进制的字符串,用0,1码的不同排列来表示字符,如果字母只有a,b,c,d四个,可以用2位二进制编码,让00,01,10,11分别代表四位字母。但由于不同字母的使用频率不同,这样的等长编码方式会导致流量的浪费,而且现实中字母当然不止4个,于是可以在设计编码时,让使用频率高的用短码,使用频率低的用长码,以优化整个报文编码。

3. 上面所说的不等长编码的设计过程也就是霍夫曼树的构建过程。构建过程为:a, 当节点序列中的根节点数量多于一个时,从当前节点序列中选择两个权值最小的根节点,分别作为左右子节点,创建新的根节点;b, 从序列中删除上一步选择的两个根节点,将新创建的根节点加入序列。然后重复执行这两步。前面a,b,c,d的构建过程如下:

初始状态:四个节点,按照权值由小到大排列

第一步:选择两个权值最小的根节点,即a,b两节点,构建新根节点,规定左子节点权值不大于右子节点权值

第二步:按照规则,继续选择两个权值最小的根节点,构建新根节点

最终构建的霍夫曼树:

左分支看作0,右分支看作1,则a,b,c,d对应的编码为:a:000 b:001 c:01 d:1

整颗树的带权路径长度WPL=1*3+2*3+3*2+7*1=22

而定长编码的带权路径长度=(1+2+3+7)*2=26

参考资料:

https://baike.baidu.com/item/%E5%93%88%E5%A4%AB%E6%9B%BC%E6%A0%91/2305769?fr=aladdin&fromid=1792010&fromtitle=%E6%9C%80%E4%BC%98%E4%BA%8C%E5%8F%89%E6%A0%91

欢迎关注公众号【菜鸟程序员成长记】

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180226G1F0BQ00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券