专栏首页Deep learning进阶路7-2 其余的一些树-排序二叉树-霍夫曼树

7-2 其余的一些树-排序二叉树-霍夫曼树

7-2 其余的一些树

1、二叉排序树

二叉排序树可以通过递归的方法来定义,它或者是空二叉树,或者是具有如下定义的二叉树:

左子树上所有节点的关键字均小于根节点的关键字右子树上所有节点的关键字均大于等于根节点的关键字

左子树和右子树本身又各是一颗二叉排序树

二叉排序树的生成

从二叉排序树的定义中可以得出一个重要性质:

按中序遍历该树所得的中序序列是一个递增有序列!因此二叉排序树常用来对数据进行排序操作。利用二叉排序树来组织数据,可以减少数据查找次数,提高效率。

由给定的数据序列生成二叉排序树的过程是在二叉排序树上插入节点的过程,对一个序列{k1, k2, k3 ,..., kn},先设一颗空二叉排序树,然后将序列中的元素顺次生成节点后逐个插入。

第一步:k1作为二叉排序树的根;

第二步:若k2 < k1, 则k2 所在节点应插入到k1的左子树上;否则,插入到k1的右子树上。

第三步:读入 ki,如果 ki<k1,则进入左子树,反之进入右子树;继续与子树之根节点比较,直到某节点kj, 若有 ki<kj 且 kj的左子树为空,则ki插入到kj的左子树上; 若ki>=kj 且 kj的右子树为空,则ki插入到kj的右子树上。

2.普通树的存储

前面讲的都是二叉树的一些东西,二叉树比较特殊,所以有很多性质,对于普通结构的树,存储方法大致上有3种:

①双亲表示法;

②孩子表示法;

③孩子兄弟表示法;

①双亲表示法

双亲表示法采用顺序表(也就是数组)存储普通树,其实现的核心思想是:顺序存储各个节点的同时,给各节点附加一个记录其父节点位置的变量。根节点没有父节点(父节点又称为双亲节点),因此根节点记录父节点位置的变量通常置为 -1

②孩子表示法

孩子表示法存储普通树采用的是 "顺序表+链表" 的组合结构,其存储过程是:从树的根节点开始,使用顺序表依次存储树中各个节点,需要注意的是,与双亲表示法不同,孩子表示法会给各个节点配备一个链表,用于存储各节点的孩子节点位于顺序表中的位置。

如果节点没有孩子节点(叶子节点),则该节点的链表为空链表

③孩子兄弟表示法

树结构中,位于同一层的节点之间互为兄弟节点。孩子兄弟表示法,采用的是链式存储结构,其存储树的实现思想是:从树的根节点开始,依次用链表存储各个节点的孩子节点和兄弟节点。

该链表中的节点应包含以下 3 部分内容(如图):

a,节点的值;

b, 指向孩子节点的指针;

c, 指向兄弟节点的指针;

观察上面左右两图发现,左图是一颗普通树,但是右图很明显是一颗二叉树!

所以这也就给我们提供了将普通树转换为二叉树的思路

3、树, 森林 与二叉树的转换

①将普通树转化为二叉树:

a,在兄弟的之间连线;

b,对每个节点,只保留它与第一个子节点的连线,与其他子节点的连线抹去;

c,将原来的兄弟节点顺时针移动45°

②把森林转化为对应的二叉树

先将森林中的各个普通树用①中的方法,都转化为二叉树,然后将各个二叉树的根节点连在一起,自然就是一棵二叉树了。因为①的方法转换出来的二叉树,根节点没有右子树,所以将多棵这样的二叉树连起来,右边的二叉树就成了第一棵二叉树根节点的右子树部分。

4、霍夫曼编码与最优二叉树

霍夫曼编码是一种有效的数据压缩技术,能够使得编码量减少。

先来看一个霍夫曼编码的例子:

已知一个通信系统中使用的字符为a, b, c, d, e, f, g 7个不同的字母,每传输1千字,他们出现的频率为: 115,11,14,35,516,254,55.

①把7个不同的字母看成不同的节点,它们的出现频率就看成它们的权重,先按照权重对它们排序如下:

②选出其中权重最小的两个节点,分别作为左右节点,构成一棵树,一般遵循左小右大。

它们的父节点的权重设为此二节点之和:

③不断重复以上过程,直到所有的节点都被使用:

如果把每条左边的边标为0,右边的边标为1,那么就得到这7个字母的霍夫曼编码:

e---1, f---01, a---001, g---0000, d---00011, b---000100, c---000101,

试想,如果使用传统的二进制编码从 000到110 共7个二进制编码对这7个数进行编码,则每个字符都需要3bit,那么1000字的内容就是3000 bit;

而如果采用霍夫曼编码,同样1000字,只需要:

1x516 + 2x254 + 3x115 + 4x55 + 5x35 + 6x11 + 6x14 = 1914 bit

数据压缩比为: (3000-1914)/3000 = 36.2%

霍夫曼编码得到的二叉树给出了一种能保证信息通信时最少的编码量,也引入了最优二叉树的概念,最优二叉树也称为 霍夫曼树。

最优二叉树(霍夫曼树)

叶子节点的权值:叶子节点的权值是对叶子节点赋予的一个有意义的数量值。霍夫曼编码中,就是某个字母出现的频次;

节点的带权路径长度:从该节点到树根之间的路径长度与该节点权的乘积;

树的带权路径长度 WPL :树中所有叶子节点的带权路径长度 之和

最优二叉树:指所有叶子节点的二叉树中带权路径最小的二叉树。

在构建哈弗曼树时,要使树的带权路径长度最小,只需要遵循一个原则,那就是:权重越大的结点离树根越近。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 7-1 树结构 和 二叉树

    前面讲的都是 线性存储结构,而树是一种典型的非线性存储结构,一个元素可以有多个直接后继元素。

    TeeyoHuang
  • Python随记(一)列表和元组

    Python随记(一)列表和元组 Python中最基本的数据结构就是序列了。Python一共包含6种内建序列:列表、元组、字符串、Unicode字符串、xra...

    TeeyoHuang
  • C++随记(二)---动态分配内存问题(1)

    C++随记(二)---动态分配内存问题(1) 面向对象的编程的一个特点就是在运行阶段(而不是编译阶段)进行决策。运行阶段决策提供了灵活性,可以根据当时的情况进行...

    TeeyoHuang
  • 使用虚拟节点改进的一致性哈希算法

    1 作者:@lionets 分析缺点 连接:http://my.oschina.net/lionets/blog/288066 2 作者:@糖拌咸鱼 ...

    程序员小王
  • 左倾红黑树、右倾红黑树、AA树,你不知道的还有很多!

    上一节,我们一起从二叉树、二叉查找树、平衡树、AVL树、2-3树、2-3-4树、B树,一路讲到红黑树,最后得出红黑树的本质:红黑树就是2-3-4树,请看下图:

    彤哥
  • 红黑树(二):删除操作

    构造上,节点会有三种可能:其一是删除节点的孩子都为Nil,其二是删除节点的一个孩子节点为Nil,其三是删除节点的两个孩子节点都不为Nil。而如果两个节点都不为N...

    每天学Java
  • 在图数据上做机器学习,应该从哪个点切入?

    自从我们在伦敦互联数据中心(Connected Data London)的演讲以来,我已经与许多拥有图数据的研究团队进行了交谈,他们希望对图进行机器学习,但不确...

    AI科技大本营
  • 面试官问你B树和B+树,就把这篇文章丢给他

    在介绍B+树之前, 先简单的介绍一下B树,这两种数据结构既有相似之处,也有他们的区别,最后,我们也会对比一下这两种数据结构的区别。

    好好学java
  • ZookeeperZNode基本命令四字命令SessionWatcherACLZookeeper集群Paxos算法ZAB协议Curator分布式锁

    在Zookeeper中,ZNode可以分为持久节点和临时节点两类。所谓持久节点是指一旦这个ZNode被创建了,除非主动进行ZNode的移除操作,否则这个ZNod...

    spilledyear
  • 面试官问你 B树 和 B+ 树,就把这篇文章丢给他

    在介绍B+树之前, 先简单的介绍一下B树,这两种数据结构既有相似之处,也有他们的区别,最后,我们也会对比一下这两种数据结构的区别。

    范蠡

扫码关注云+社区

领取腾讯云代金券