文章目录
1.基本概念
1.1.路径和路径长度
若在一棵树中存在着一个结点序列k1,k2,k3,kj,使得ki是kj的双亲( 1≤i<j)，则称此结点序列是从k1~kj的路径。因树中每个结点只有一个双亲结点，所以它也是这两个结点之间的唯一路径。
从k1~kj,所经过的分支数称为这两点之间的路径长度，它等于路径上的结点数减1。在图6.24( a )所示的二叉树中，从树根结点A到叶子结点H的路径为结点序列A，B，E，H，路径长度为3。
1.2.数的路径长度
树的路径长度是从树的根结点到树的各个结点的路径长度之和，记作PL。如图6.24（a）中二棵树的路径长度为3。
由于二叉树中第k层的结点最多为2^(k-1)个，而树的根到第k层的结点的路径长度为k - 1，换句话说，二叉树中路径长度为k -1这样的结点最多有2^(k-1)个 。
显然，在n个结点的各二叉树中，完全二叉树具有最少的路径长度。如图6.24( b)所示为完全二叉树，其路径长度为13。但具有最小路径长度的不一定是完全二叉树，例如图6.24( a)所示的为非完全二叉树，它也具有最少的路径长度。
一般来说，若深度为k的n个结点的二叉树具有最小路径长度，那么从根结点到第k -1层具有最多的结点数2^(k-1) -1，余下的n - (2^(k-1) -1)个结点在第k层的任一位置上。
1.3.结点的权和带权二叉树
在许多应用中，常常将树中的结点赋上一个有着某种意义的实数，称此实数为该结点的权。
假如给定一个有n个权值的集合{w1,w2,…,wn}，其中w,≥0( 1≤i≤n)。若BT是一棵有n个叶子的二叉树，而且将权︰{w1,w2,…,wn}分别赋给BT的叶子，称BT是带权二叉树。
1.4.结点的带权路径长度和树的带权路径长度
结点的带权路径长度规定为从树根结点到该结点之间的路径长度与该结点上权的乘积。树的带权路径长度定义为树中所有叶子结点的带权路径长度之和。
1.5哈夫曼树
对于一组带有确定权值的叶子节点，构造出的不同的二叉树的带权路径长度并不相同，把其中具有最小带权路径长度为二叉树为最优二叉树，最优二叉树也称为哈夫曼树。
例子如下图所示：
2.算法实现
根据哈夫曼树的定义，一棵二叉树要使其WPL值最小，必须使权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。根据这种思想，哈夫曼提出了一种构造最优树的算法，即哈夫曼算法。
算法思想:
-
根据给定的n个权值︰{w1,w2,…,wn}构成n棵二叉树的森林F={T1,T2, … ,Tn}，其中每棵二叉树T中只有一个带权为wn的根结点，且其左右子树为空
-
在森林F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和
-
同时将新得到的二叉树加入森林F中。
-
重复2和3,直到F中只含一棵树为止。这棵树便是哈夫曼树。
用哈夫曼算法构造出来的二叉树一定是最优树。
因为从构造过程看，权值最大的叶子离根最近，权值最小的叶子离根最远。例如，对于一组给定的叶子结点，它们的权值集合为W ={ 4，2，1，7，3},由此集合构造哈夫曼树的过程如下图所示。在构造哈夫曼树的过程中，当每次由两棵权值最小的树生成一棵新树时，新树的左子树和右子树的顺序可以任意安排，这样将会得到具有不同结构的多个哈夫曼树，但它们都具有相同的带权路径长度。为了使得构造的哈夫曼树的结构尽量唯一，通常规定生成的哈夫曼树中每个结点的左子树根结点的权值小于等于右子树根结点的权值。上述哈夫曼树的构造过程和下面的算法描述就是依照这一规定进行的。、
3.存储结构
根据哈夫曼算法思想可知，哈夫曼树的构造过程，实际上是将由n棵二叉树组成的森林逐渐变成一棵二叉树的过程，因为每次是由两棵二叉树合并成为一棵新的二叉树，n棵二叉树的森林经过n -1次合并后产生n-1个分支结点和n个叶子结点，因而一棵有n个叶子结点的哈夫曼树*有2n -1个结点。
二叉树的存储结构可以选择顺序存储，也可以选择链式存储。当然，选择不同的存储结构，其哈夫曼算法的实现也不同。鉴于哈夫曼树的结点总数是确定的，所以，下面的算法采用双亲孩子数组表示法。
4.代码实现
4.1.算法实现
void select(HuffmanTree T, int n, int *s1, int *s2)
{
int m1, m2;
m1 = m2 = maxValue;
*s1 = *s2 = 0;
for (int i = 0; i < n; i++)
{
if (T[i].weight<m1&&T[i].parent==-1)
{
m2 = m1;
*s2 = *s1;
m1 = T[i].weight;
*s1 = i;
}
else if(T[i].weight < m2 && T[i].parent == -1)
{
m2 = T[i].weight;
*s2 = i;
}
}
}
void HuffmanCreate(HuffmanTree T, int* w, int n)
{
int s1 = NULL, s2 = NULL;
printf("\nthe length of tree is %d\n", n);
for (int i = 0; i < 2*n-1; i++)
{
if (i < n) T[i].weight = w[i];
else T[i].weight = 0;
T[i].parent = -1;
T[i].lchild = -1;
T[i].rchild = -1;
}//初始化T
printf("initilization of the tree\n:");
for (int i = 0; i < 2 * n - 1; i++)
{
printf("%d ", T[i].weight);
}
int j = 0;//控制打印输出的次数
for (int i = n; i < 2*n-1; i++)
{
select(T, i, &s1, &s2);
T[i].lchild = s1;
T[i].rchild = s2;//右节点略大于左节点
T[s1].parent = T[s2].parent = i;
T[i].weight = T[s1].weight + T[s2].weight;
printf("\n s1 = %d,s2 = %d\n", s1, s2);
printf("********************%d********************\n", ++j);
for (int i = 0; i < 2 * n - 1; i++)
{
printf("%d ", T[i].weight);
}
}
}
4.2.测试程序
#include <stdio.h>
#include <stdlib.h>
#define treeNodeLength 5
typedef struct MyStruct
{
int weight;
int parent, lchild, rchild;
}HTNode;
typedef HTNode* HuffmanTree;
int maxValue = 0;
void main()
{
int weight[] = {4,2,1,7,3};
int n = sizeof(weight)/sizeof(*weight);
for (int i = 0; i < n; i++)
{
maxValue += weight[i];
}
HuffmanTree T = (HuffmanTree)malloc(sizeof(HTNode) * (2 * n - 1));
HuffmanCreate(T, weight, treeNodeLength);
printf("\nfinal of the tree\n:");
for (int i = 0; i < 2*n-1; i++)
{
printf("%d ", T[i].weight);
}
printf("\n");
system("pause");
}