基本概念

要了解节本概念还有些基本概念要了解：

路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径
路径长度：路径上的分支数目称作路径长度
树的路径长度：是从树根到每一节点的路径长度之和。 完全二叉树就是路径最短的二叉树。
结点的带权路径长度：结点的带权路径长度为从该结点到树根之间的路径长度与节点上的权的乘积
树的带权路径长度：树中所有叶子结点的带权路径长度之和
最优二叉树/赫夫曼树：带权路径长度最小的树

赫夫曼树构造算法

最优二叉树算法算是贪心算法，每次选出权值最小的子树构成新的二叉树，权值之和作为新二叉树的权值。

构造算法

叙述如下：

根据给定的n个权值{ w1, w2, ... , wn }构成n棵二叉树的集合F = { T1, T2, ... ,Tn }，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均空。
在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
在F中删除这两棵树，同时将新的到的二叉树加入F中。
重复2和3，直到F只含一棵树为止。即得赫夫曼树。

赫夫曼编码

赫夫曼编码可用于生成前缀编码。 前缀编码是长短不等的编码，而且任何一个字符的编码都不能是另一个字符的编码的前缀。树中没有长度为1的结点称为严格的（strict）/正则的二叉树。由于赫夫曼树都是正则二叉树，则一棵有n个叶子节点的赫夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中。由于编码需要从叶子结点到根，而解码需要从根到叶子结点，为了迎合这种需要，通常存储表示都是采用如下表示：

typedef struct {
	unsigned int    weight;
	unsigned int    parent, lchild, rchild;
} HTNode, *HuffmanTree;    //动态分配数组存储赫夫曼树
typedef char **HuffmanCode;    //动态分配数组存储赫夫曼编码表

编码算法

以下两个算法求赫夫曼编码：先是一个最直接想到的版本：

void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n) {
	//w存放n个字符串的权值（均大于零），构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC。
	if( n<=1 )    return 1;
	m = 2 * n - 1;
	HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode));    //为了方便0号单元未使用
	for( p=HT, i = 1; i<=n; ++i, ++p, ++w)    *p = { *w, 0, 0, 0 };
	for( ; i<=m; ++i, ++p)    *p = { 0, 0, 0, 0};
	for( i = n+1; i<=m; ++i) {
	    //建立赫夫曼树
	    //在HT[1..i-1]中选择parent为0且weight最小的两个结点，其序号分别为s1和s2
	    Select(HT, i-1, s1, s2);
	    HT[s1].parent = i;    HT[s2].parent = i;
	    HT[i].lchild = s1;    HT[i].rchild = s2;
	    HT[i].weight = HT[s1].weight + HT[s2].weight;
	}
	//从叶子结点到根逆向求每个字符的赫夫曼编码
	HC = (HuffmanCode)malloc((n+1) * sizeof(char *));    //分配n个字符编码的头指针向量
	cd = (char *) malloc ( n *sizeof(char));    //分配求编码的工作空间
	cd[n-1] = "\0";    //编码结束符
	//逐个字符求赫夫曼编码
	for( i=1; i<=n; ++i ) {
	    start = n-1;    //编码结束符位置
	    //从叶子到根逆向求编码
	    for( c=i, f=HT[i].parent; f!=0; c=f, f=HT[ f ].parent ) {
	        if( HT[f].lchild == c)    cd[--start] = "0";
	        else    cd[--start] == "1";
	    }
	    HC[i] = (char *)malloc((n-start) * sizeof(char));    //为第i个字符编码分配空间
	    strcpy(HC[i], &cd[start]);    //从cd赋值编码串到HC
	}
	free(cd);    //释放工作空间
}

上面一个是从叶子出发到根求编码，也可以从根出发遍历整棵赫夫曼树求得各个叶子结点所表示的编码，但是从根出发会丢失结点的权重信息，代码如下：

//无栈非递归遍历赫夫曼树，求赫夫曼编码
HC = (HuffmanCode)malloc((n+1) * sizeof(char *));
p = m;    cdlen = 0;
for(i=1; i<=m; ++i)
    HT[i].weight = 0;    //遍历赫夫曼树时用作结点状态标志
while(p) {
	if(HT[p].weight == 0) {    //向左
	    HT[p].weight =1;
	    if(HT[p].lchild != 0) {
	        p=HT[p].lchild;
	        cd[cdlen++] = "0";
	    } else if (HT[p].rchild == 0) {
	        //登记叶子结点的字符编码
	        HC[p] = (char *)malloc((cdlen + 1) * sizeof(char));
	        cd[cdlen] = "\0";
	        strcpy(HC[p], cd);    //复制编码串
	    }
	}  else if(HT[p].weight == 1) {    //向右
	    HT[p].weight = 2;
	    if(HT[p].rchild != 0) {
	        p = HT[p].rchild;
	        cd[cdlen ++] = "1";
	    }
	}  else {    //HT[p].weight == 2，退回
	    HT[p].weight = 0;
	    p=HT[p].parent;
	    --cdlen;    //退到父节点，编码长度减1
	}
}

总结：第一个算法能够保留构造赫夫曼树的时候的权重信息，而且易于理解和实现；第二个算法算法结构描述有点不清楚，其核心思想就是深度优先搜索，搜索到叶子节点保存编码并回退（由于存储结构存储的有parent结点的信息，当然不用栈也不用递归）。

译码算法

译码算法没什么可说的，从根匹配到叶子结点就能求得相应字符，代码表达不再给出。

总结自：《数据结构（C语言版）》清华大学出版社严蔚敏、吴伟民编著