构建哈夫曼树算法的实现可以分为两大部分。
（1）初始化：首先动态申请2n个单元；然后循环2n-1次，从1号单元开始，依次将1至2n-1所有单元中的双亲、左孩子、右孩子的下标都初始化为0；最后再循环n次，输入前n个单元中叶子结点的权值。完成初始化的状态图为图中的（a）。
（2）创建树：循环n-1次，通过n-1次的选择、删除与合并来创建哈夫曼树。选择是从当前森林中选择双亲为0且权值最小的两个树根结点s1和s2；删除是指将结点s1和s2的双亲改为非0；合并就是将sl和s2的权值和作为一个新结点的权值依次存人到数组的第n+1之后的单元中，同时记录这个新结点左孩子的下标为s1，右孩子的下标为s2。完成此步骤的状态图为图中的（b）。
完整代码如下：
#include <stdio.h> #include <stdlib.h> typedef struct { int weight;//结点的权值 int parent,lchild,rchild;//结点的双亲，左孩子，右孩子的下标 }HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树 void InitTree(HuffmanTree &H,int &n)//初始化哈夫曼树 { int i,a; printf("请输入结点个数： "); scanf("%d",&n);//结点个数 H = (HTNode*)malloc(sizeof(HTNode)*(2*n));//申请一个2*n的空间 for(i=0;i<2*n;i++)//利用循环对申请的空间进行初始化 H[i].weight = H[i].parent = H[i].lchild = H[i].rchild = 0; printf("分别为： "); for(i=0;i<n;i++)//利用循环对n个结点权值赋值 { scanf("%d",&a); H[i+1].weight = a; } } void Select(HuffmanTree H,int n,int &s1,int &s2)//选择函数 ，输入要循环的总次数n，并返回其权值最小的两个数的结点序号s1和s2 { int i,//循环次数i a,//权值赋值变量 b;//结点序号赋值变量 for(i=0;i<n;i++)//循环赋值 { if(H[i+1].parent == 0)//找出第一个parent是0的结点，对变量a,b进行赋值 { a = H[i+1].weight; b = i+1; break;//循环终止条件 } } for(i=0;i<n;i++)//利用循环找出最小值 { if(a>H[i+1].weight && H[i+1].parent == 0)// parent为0的结点的中的最小值， 赋值给a和b,b为序号 { a = H[i+1].weight; b = i+1; } } s1 = b; for(i=0;i<n;i++) { if(H[i+1].parent == 0 && (i+1)!= s1)//找出第一个parent是0且不是最小权值的结点，对变量a,b进行赋值 { a = H[i+1].weight; b = i+1; break; } } for(i=0;i<n;i++)//利用循环找出除s1的最小值 { if(a>H[i+1].weight && H[i+1].parent == 0 && (i+1)!=s1) { a = H[i+1].weight; b = i+1; } } s2 = b; } void CreateHuffmanTree(HuffmanTree &H,int n)//哈夫曼树的创建 { int s1,s2;//申请变量，方便接挑选函数返回的值 int i; for(i=n+1;i<2*n;i++)//通过n-1次的选择，删除，合并来构建哈夫曼树 { Select(H,i-1,s1,s2);//选出最小的两个数 H[s1].parent = i; H[s2].parent = i;//得到新结点i，从森林中删除s1，s2，并将s1,s2的双亲域由0改成i H[i].lchild = s1; H[i].rchild = s2;//s1和s2分别作为i的左右孩子 H[i].weight = H[s1].weight+H[s2].weight;//i的权值为左右孩子的权值之和 } } void CreatHuffmanCode(HuffmanTree H,int n)//哈夫曼编码的输出，递归实现 { if(H[n].parent == 0)//递归终止条件 return ; CreatHuffmanCode(H,H[n].parent);//递归双亲结点 if(H[H[n].parent].lchild == n)//如果n的双亲的左孩子等于n，则输出0，否则输出1 printf("0"); else printf("1"); } //书上的例子：8个结点分别为 5 29 7 8 14 23 3 11 int main() { int n,i; HuffmanTree H; InitTree(H,n);//初始化 CreateHuffmanTree(H,n);//构建哈夫曼树 for(i=1;i<2*n;i++)//利用循环分别打印权值，双亲，左孩子，右孩子 { printf( "%d ",H[i].weight); printf("%d ",H[i].parent); printf("%d ",H[i].lchild); printf("%d\n",H[i].rchild); } printf("哈夫曼编码：\n"); for(i=1;i<=n;i++) //利用循环打印各个结点的哈夫曼编码 { printf("%d: ",i); CreatHuffmanCode(H,i);//哈夫曼编码 printf("\n"); } return 0; }结果图展示： 前两行为输入的数据。 （完）
