1.哈夫曼树只有结点为0.或者结点为2的值。所以如果叶子结点为n的话，那么整个哈夫曼树的所有结点个数为2n-1；因为结点为2的结点个数n0=n2+1;所以总数n=n0+n2=2n0-1;
过程：<1>由已知的n个权值形成哈夫曼树的初态，即在数组ht[]的前n项中填入相应的权值。
<2>建立哈夫曼树。依次将数组ht[]中的第n+1项到第m项作为当前项，，并进行以下处理：
1.在前已形成的项目中选择两个权值最小且无双亲的项。
2.将当前项的序号填入两个选择的项作为双亲，将两个选择项的序号填入当前项分别作为左右孩子。
3.将两个选择项的权值相加后填入当前项作为当前项的权值。
<3>由已形成的哈夫曼树求哈夫曼编码。对每个叶节点都进行如下处理：
扫描由叶节点到根节点的各条分支，若果分支中的当前结点与双亲关系是左支关系，则生成编码0，若分之中的当前结点与双亲结点是右支关系，则生成编码1，由此生成的二级制码的序列即为该结点的哈夫曼编码。
程序如下：
#include<iostream>using namespace std;#define maxlen 100struct HaffNode{int weight;int parent;int lchild;int rchild;};struct HaffCode{int bit[maxlen];int start;int weight;};void Haffman(int w[],int n,HaffNode ht[], HaffCode hc[]){int i, j, m1, m2, x1, x2;//m1,m2分别表示最小，次小的权值；x1,x2分别表示当前分支结点的左右儿子//步骤1.构造哈夫曼树for (i = 0; i < 2 * n – 1; i++)//哈夫曼树初始化{if (i < n)ht[i].weight = w[i];elseht[i].weight = 0;ht[i].parent = 0;ht[i].lchild = ht[i].rchild = -1;}for (i = 0; i < n – 1; i++)//构造哈夫曼树的n-1个分支结点{m1 = m2 = 1000;x1 = x2 = 0;for (j = 0; j < n + i; j++){if (ht[j].weight < m1 && ht[j].parent == 0){m2 = m1;//最小保存到次小x2 = x1;m1 = ht[j].weight;x1 = j;}else if (ht[j].weight < m2 && ht[j].parent == 0){m2 = ht[j].weight;x2 = j;}}ht[x1].parent = n + i;ht[x2].parent = n + i;ht[n + i].weight = ht[x1].weight + ht[x2].weight;ht[n + i].lchild = x1;ht[n + i].rchild = x2;}//步骤2 由哈夫曼树生成哈夫曼编码HaffCode cd;int child, parent;for (i = 0; i < n; i++)//由哈夫曼树生成哈夫曼编码{cd.start = n – 1;cd.weight = ht[i].weight;child = i;parent = ht[child].parent;while (parent != 0){if (ht[parent].lchild == child)cd.bit[cd.start] = 0;elsecd.bit[cd.start] = 1;cd.start–;child = parent;parent = ht[child].parent;}for (j = cd.start + 1; j < n; j++)hc[i].bit[j] = cd.bit[j];hc[i].start = cd.start;hc[i].weight = cd.weight;}}int main(void){int w[] = { 4, 2, 6, 8, 3, 2, 1 };int n = 7, i, j;HaffNode *ht = new HaffNode[2 * n – 1];HaffCode *hc = new HaffCode[n];Haffman(w, n,ht, hc);for (i = 0; i < n; i++){cout << "weight=" << hc[i].weight << "code=";for (j = hc[i].start + 1; j < n; j++)cout << hc[i].bit[j]; cout << endl;}}
效果图：
而只有在充满了艰辛的人生旅途中，
