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 ：树中所有叶子节点的带权路径长度 之和

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

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