数据结构（9）之树的补充（赫夫曼树；线索二叉树树；树与二叉树转换）

1 前言

这篇文章主要介绍了线索二叉树，树，森林与二叉树的转换以及赫夫曼树的相关内容。

转载请注明出处：http://blog.csdn.net/developer_zhang

2 详述

2.1 线索二叉树

在二叉树的结点添加指向前驱和后继的指针，而指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，响应的二叉树就称为线索二叉树（Threaded Binary Tree）。

二叉树转化为线索二叉树：

转化方法：例如对如下二叉树：

中序遍历这棵二叉树，把所有的空指针中的rchild，改为指向它的后继结点，最右边的后继为NULL，得到：

然后，将这棵二叉树的所有空指针域中的lchild，改为指向当前结点的前驱。而最左边的结点的前驱为NULL：

对二叉树以某种次序遍历使其变为线索二叉树额过程称作是线索化：

这么一来所有的空指针域则都被充分的利用，大大提高了效率。

2.1.1 结点结构

其中：

·ltag为0时指向该结点的左孩子，为1时指向该几点的前驱。

·rtag为0时指向该结点的右孩子，为1时指向该结点的后继。

·因此对于图中的二叉链表可以修改为如图：

2.1.2 线索二叉树结构实现

存储结构代码：

/*二叉树的二叉线索存储结构定义*/
typedef enum(Link,Thread) PointerTag;   /*Link == 0 表示指向左右孩子指针*/
                                                                          /*Thread == 1表示指向前驱或后继的线索 */
typedef struct BiThrNode
{
    TElemType data;       /*结点数据*/
    struct BiThrNode *lchild,*rchild;     /*左右孩子指针*/
    PointerTag LTag;
    PointerTag RTag;      /*左右标志*/
}BiThrNode,*BiThrTree;

线索化的过程就是在遍历的过程中修改空指针的过程。

如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构就是不错的选择。

2.2 树，森林与二叉树的转换

2.2.1 树转化为二叉树

·加线，在所有兄弟结点之间加一条连线。

·去线。对树种的每个结点，只保留它与第一个孩子结点的连线，删除与其他孩子结点之间的连线。

·层次调整。以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。注意第一个孩子是二叉树结点的左孩子，兄弟转换过来的孩子结点是右孩子。

2.2.2 森林转换为二叉树

·把每个树转化为二叉树。

·第一棵树不懂，从第二棵二叉树开始，一次把后一棵二叉树的根结点作为前一棵二叉树的根节点的右孩子，用线连接起来。当所有的二叉树连接起来后就得到了由森林转换来的二叉树。

2.2.3 二叉树转换为树

·加线。若某结点的左孩子结点存在，则将这个左孩子的右孩子结点，右孩子的右孩子结点，。。。也就是左孩子的n各右孩子结点都作为此结点的孩子。将该结点与这些右孩子结点用线连接起来。

·去线。删除原二叉树中所有结点与其右孩子结点的连线。

·层次调整。使之结构层次分明。

2.2.4 二叉树转换为森林

·从跟结点开始，若右孩子存在，则把与右孩子结点的连线删除，在查看分离后的二叉树，若右孩子存在，则连线删除。。。，知道所有的右孩子连线都删除为止，得到分离的二叉树。

·再将每棵分离后的二叉树，转换为树即可。

2.3 赫夫曼树及其应用

2.3.1 简单定义

从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称做路径长度。

树的路径长度就是从树根到每一个结点的路径长度之和。

如图：二叉树a的树路径长度为1+1+2+2+3+3+4+4 = 20。二叉树b的树路径长度为 1+2+3+3+2+1+2+2 = 16.

结点的带权的路径长度为从该结点到树根之间的路径长度与结点上的权的乘积。树的带权路径长度为树种的所有叶子结点的带权路径长度之和。假设有n个权值{w1，w2，。。。，wn}，构造一棵有n个叶子结点的二叉树，每个叶子结点带权wk，每个叶子的路径长度为1k，我们通常记作，则其中带权路径长度WPL最小的二叉树称作赫夫曼树。

则上图中这两棵树的WPL值：

二叉树a的WPL = 5*1+15*2+40*3+30*4+10*4 = 315

注意：这里5是A结点的权，1是A结点的路径长度，其他同理。

二叉树b的WPL = 5*3+15*3+40*2+30*2+10*2 = 220

2.3.2 赫夫曼求法

上面的b是否是我们所需要的赫夫曼树呢？下面我们介绍一下赫夫曼树的实例求法：

·先把有权值的叶子结点从小到大的顺序排列成一个有序序列，即：A5，E10，B15，D30，C40。

·取头两个最小权值的结点作为一个新结点N1的两个子结点，注意相对较小的是左孩子，这里就是A为N1的左孩子，E为N1的右孩子，新结点的权值为两个叶子权值的和5+10 = 15.

·将N1替换A与E，插入有序序列中，保持从小到大排序。即：N1 15，B15，D30，C40.

·重复步骤2.将N1与B作为一个新节点N2的两个子结点。N2的权值 = 15+15 = 30.

·将N3替换N2与D，插入有序序列中，保持从小到大排列。即：C40，N2 60.

·重复步骤2.将C与N3作为一个新的结点T的两个子结点，由于T为根结点，完成赫夫曼树的构造。

由图可以得到二叉树的带权路径长度WPL = 40*1+30*2+15*3+10*4+5*4 = 205.则是最优的赫夫曼树。

由上述所述，我们得到了赫夫曼树的赫夫曼算法描述：

·根据给定的n个权值{w1,w2,...,wn}构成n棵二叉树的集合F={T1,T2,...,Tn}，其中每棵树二叉树T1中只有一个带权为w1根结点，其左右子树均为空。

·在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。

·在F中删除这两棵树，同事将新得到的二叉树加入到F中。

·重复2和3步骤，知道F只含一棵树为止。这棵树便是赫夫曼树。

2.3.3 赫夫曼编码

一般地，设需要编码的字符集为{d1,d2,...,dn}，各个字符在电文中出现的次数或频率集合为{w1,w2,...,wn}，以d1,d2,...,dn作为叶子结点，以w1，w2，。。。，wn作为相应叶子结点的权值来构造一棵赫夫曼树。规定赫夫曼树的左分支代表0，右分支代表1，则从根结点到叶子结点所经过分支组成的0和1的序列便为该结点对应字符的编码，这就是赫夫曼编码。

所得结果为：1001010010101001000111100.根据表我们就可以还原出来这棵树了。

3 结语

以上是所有内容，希望对大家有所帮助。