使用一个有序的遍历方法来遍历霍夫曼树，从而构建这个表。在每次执行build_table的过程中，code 记录当前生成的编码，size保存编码的位数。在遍历树时，每当选择左分支时，将0追加到编码的末尾中；每当选择右分支时，将1追加到编码的末尾中。一旦到达一个叶子结点，就将霍夫曼编码存放到编码表合适的条目中。在存放每个编码的同时，调用函数htons，以确保编码是以大端字节格式存放。这一步非常重要，因为在下一步生成压缩数据时需要用大端格式，同样在解压缩过程中也需要大端格式。
在产生压缩数据的同时，使用ipos来保存原���数据中正在处理的当前字节，并用opos来保存向压缩数据缓冲区写入的当前位。首先，缩写一个头文件，这有助于在huffman_uncompress中重建霍夫曼树。这个头文件包含一个四字节的值，表示待编码的符号个数，后面跟着的是所有256个可能的符号出现的缩放频率，也包括0。最后对数据编码，一次读取一个符号，在表中查找到它的霍夫曼编码，并将每个编码存放到压缩缓冲区中。在压缩缓冲区中为每个字节分配空间。
huffman_compress的时间复杂度为O（n），其中n是原始数据中符号的数量。
huffman_uncompresshuffman_uncompress操作解压缩由huffman_compress压缩的数据。首先，此操作读取追加到压缩数据的头。回想一下，头的前4个字节包含编码符号的数量。这个值存放在size中。接下来的256个字节包含所有符号的缩放频率。
利用存放在头中的信息，调用build_tree重建压缩过程中用到的霍夫曼树。一旦重建了树，接下来就要生成已恢复数据的缓冲区。要做到这一点，从压缩数据中逐位读取数据。从霍夫曼树的根开始，只要遇到位数0，就选择左分支；只要遇到位数1，就选择右分支。一旦到达叶子结点，就获取一个符号的霍夫曼编码。解码符号存储在叶子中。所以， 将此符号写入已恢复数据的缓冲区中。写入数据之后，重新回到根部，然后重复以上过程。使用ipos来保存向压缩数据缓冲区写入的当前位，并用opos来保存写入恢复缓冲区中的当前字节。一旦opos到达size，就从原始数据中生成了所有的符号。
huffman_uncompress的时间复杂度为O(n)。其中n是原始数据中符号的数量。这是因为对每个要解码符号来说，在霍夫曼树中向下寻找的深度是一个有界常量，这个常量依赖于数据中不同符号的数量。在本节的实现中，这个常量是256.建立霍夫曼树的过程不影响huffman_uncompress的复杂度，因为这个过程只依赖于数据中不同符号的个数。
示例：霍夫曼编码的实现文件
/*huffman.c*/
#include <limit.h>
#include <netinet/in.h>
#include <stdlib.h>
#include <string.h>
#include "bit.h"
#include "bitree.h"
#include "compress.h"
#include "pqueue.h"
/*compare_freq 比较树中霍夫曼节点的频率*/
static int compare_freq(const void *tree1,const void *tree2)
{
HuffNode *root1,root2;
/*比较两棵二叉树根结点中所存储的频率大小*/
root1 = (HuffNode *)bitree_data(bitree_root((const BiTree *)tree1));
root2 = (HuffNode *)bitree_data(bitree_root((const BiTree *)tree2));
if(root1->freq < root2->freq)
return 1;
else if(root1->freq > root2->freq)
return -1;
else return 0;
}
/*destroy_tree 消毁二叉树*/
static void destroy_tree(void *tree)
{
/*从优先级队列中消毁并释放一棵二叉树*/
bitree_destroy(tree);
free(tree);
return;
}
/*buile_tree 构建霍夫曼树，每棵树初始只包含一个根结点*/
static int bulid_tree(int *freqs,BiTree **tree)
{
BiTree *init,
*merge,
*left,
*right;
PQueue pqueue;
HuffNode *data;
int size,c;
/*初始化二叉树优先级队列*/
*tree = NULL;
pqueue_init(&pqueue,compare_freq,destroy_tree);
for(c=0; c<=UCHAR_MAX; c++)
{
if(freqs[c] != 0)
{
/*建立当前字符及频率的二叉树*/
if((init = (BiTree *)malloc(sizeof(BiTree))) == NULL)
{
pqueue_destroy(&pqueue);
return -1;
}