最优二叉树&&哈夫曼编码
树的路径长度
树的路径长度是从树根到树中每一结点的路径长度之和。在结点数目相同的二叉树中，完全二叉树的路径长度最短。
树的带权路径长度(weighted path length of tree,wpl)
结点的权值：在一些应用中，赋予树中结点的一个有某种意义的实数、
结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积
树的带权路径长度(wpl)：定义为树中所有结点的带权路径长度之和
最优二叉树
在权为w1,w2,...,wn的n个叶子结点所构成的所有二叉树中，带权路径长度最小(即代价最小)的二叉树成为最优二叉树。
注意：
叶子上的权值均相同时，完全二叉树一定是最优二叉树，否则完全二叉树不一定是最优二叉树。
最优二叉树中，权值越大的叶子结点离根越近
最优二叉树的形态不唯一，wpl最小
构造最优二叉树
哈夫曼算法
根据给定的n个权值w1,w2,...,wn构成n棵二叉树的森林F={T1,T2,..,Tn},其中每棵二叉树Ti中只有一个权值为wi的根节点，其左右子树均为空。
在森林F中选出两棵根结点权值最小的树(当这种的树不止两棵时，可以从中任选两棵)，将这两棵树和并称一棵新树，为了保证新树仍是二叉树，需要增加一个新结点作为新树的根，并将所选的两棵树根分别作为新树的左右孩子，将这两个孩子的权值之和作为新树根的权值
对新的森林F重复2,直到森林F只剩一棵树为止。
注意
初始森林中的n棵二叉树，每棵树都有一个孤立的结点，它们既是根，又是叶子
n个叶子结点的哈夫曼树需要经过n-1次合并，产生n-1个新结点。最终求得的哈夫曼树共有2n-1个结点
哈夫曼树是严格的二叉树，没有度数为1的分支结点
哈夫曼树存储结构
[cpp]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 100
#define MIN_NUM 1000000
struct hfmcode
{
int weight;
int lchild;
int rchild;
int parent;
};
注意：
因此数组下界为0,因此用-1表示空指针。树中某结点的lchild,rchild,parent不等于-1时，它们分别是该结点的左、右孩子和双亲结点在向量中的下标。
parent域的作用：其一是查找双亲结点更为简单。其二是可通过判定parent值是否为-1来区分根和非根结点。
实现代码
（1）初始化，将T[0..m-1]中的2n-1个结点里的三个指针均置空（==-1）,权值置为0.
[cpp]
void initHuffmantree(struct hfmcode *tree, int len)
{
int i;
for(i = 0; i < len; i ++)
{
tree[i].weight = 0;
tree[i].lchild = -1;
tree[i].rchild = -1;
tree[i].parent = -1;
}
}
（2）输入，读入n个叶子的权值存于向量的前n个分量（即T[0..n-1]）中。
[cpp]
int main()
{
int n, m, i;
struct hfmcode hfmtree[MAX_SIZE];
while(scanf("%d", &n) != EOF)
{
/*哈夫曼树总共结点数*/
m = 2 * n - 1;
/*初始化哈夫曼树*/
initHuffmantree(hfmtree, m);
/*权限赋值*/
for(i = 0; i < n; i ++)
{
scanf("%d", &hfmtree[i].weight);
}
/*构造哈夫曼树*/
createHuffmantree(hfmtree, n, m);
printf("%d\n", hfmtree[m - 1].weight);
}
return 0;
}
（3）合并，对森林中的树共进行n-1次合并，所产生的新结点依次放入向量T的第i个分量中(n<=i<=m-1).每次合并分两步：
在当前森林T[0..i-1]的所有结点中，选取权最小和次小的两个根节点T[p1]和T[p2]作为合并对象，这里0<=p1,p2<=i-1
将根为T[p1]和T[p2]的两棵树作为左右子树合并为一棵新的树，新的树根是新节点T[i].具体操作是：将T[p1]和T[p2]的parent置为i,将T[i]的lchild和rchild分别置为p1和p2.新结点T[i]的权值置为T[p1]和T[p2]的权值之和。
合并后，T[p1]和T[p2]在当前森林中已不再是根，因为它们的双亲指针均已指向了T[i],所以下次合并时不会被选中为合并对象。
[cpp]
void createHuffmantree(struct hfmcode *tree, int n, int m)
{
int m1, m2, i, loc1, loc2, k;
for(i = n; i < m; i ++)
{
/*初始化最小值、次小值*/
m1 = m2 = MIN_NUM;
loc1 = loc2 = -1;
/*在尚未构造二叉树的节点中查找权值最小的两棵树*/
for(k = 0; k < i; k ++)
{
if(tree[k].parent == -1)
{
if(tree[k].weight < m1)
{
m2 = m1;
loc2 = loc1;
m1 = tree[k].weight;
loc1 = k;
}else if(tree[k].weight < m2)
{
m2 = tree[k].weight;
loc2 = k;
}
}
}
/*修改2个小权重节点的双亲*/
tree[loc1].parent = i;
tree[loc2].parent = i;
/*修改parent的权重*/
tree[i].weight = tree[loc1].weight + tree[loc2].weight;
/*修改parent的孩子*/
tree[i].lchild = loc1;
tree[i].rchild = loc2;
}
}
补充：软件开发 , C++ ,
