路径：在一棵树中，一个结点到另一个结点之间的通路，称为路径。图 1 中，从根结点到结点 a 之间的通路就是一条路径。
路径长度：在一条路径中，每经过一个结点，路径长度都要加 1 。例如在一棵树中，规定根结点所在层数为1层，那么从根结点到第 i 层结点的路径长度为 i - 1 。图 1 中从根结点到结点 c 的路径长度为 3。
结点的权：给每一个结点赋予一个新的数值，被称为这个结点的权。例如，图 1 中结点 a 的权为 7，结点 b 的权为 5。
结点的带权路径长度：指的是从根结点到该结点之间的路径长度与该结点的权的乘积。例如，图 1 中结点 b 的带权路径长度为 2 * 5 = 10 。
树的带权路径长度为树中所有叶子结点的带权路径长度之和。通常记作 “WPL” 。例如图 1 中所示的这颗树的带权路径长度为：
构建哈夫曼树的过程WPL = 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3
对于给定的有各自权值的 n 个结点，构建哈夫曼树有一个行之有效的办法：
- 在 n 个权值中选出两个最小的权值，对应的两个结点组成一个新的二叉树，且新二叉树的根结点的权值为左右孩子权值的和；
- 在原有的 n 个权值中删除那两个最小的权值，同时将新的权值加入到 n–2 个权值的行列中，以此类推；
- 重复 1 和 2 ，直到所以的结点构建成了一棵二叉树为止，这棵树就是哈夫曼树。
图 2 中，（A）给定了四个结点a，b，c，d，权值分别为7，5，2，4；第一步如（B）所示，找出现有权值中最小的两个，2 和 4 ，相应的结点 c 和 d 构建一个新的二叉树，树根的权值为 2 + 4 = 6，同时将原有权值中的 2 和 4 删掉，将新的权值 6 加入；进入（C），重复之前的步骤。直到（D）中，所有的结点构建成了一个全新的二叉树，这就是哈夫曼树。
全部代码：
#include#include #include #define MAXSIZE 1024 // 读入文件的上限 #define OK 1 #define ERROR 0 typedef int Status; typedef struct wordcnt { char ch; int cnt = 0; } Count; typedef struct NumCount { Count count[MAXSIZE]; int length = 0; } NumCount; typedef struct HTree { char data; int weight; int parent, leftChild, rightChild; } HTNode, * HuffmanTree; typedef struct HCode { char data; char* str; } *HuffmanCode, HCode; Status ReadData(char* source) { char ch; int i = 0; FILE* pFile; pFile = fopen("myfile.txt", "r"); printf("正在读取文件n"); ch = fgetc(pFile); if (ch == EOF) { printf("文件为空n"); fclose(pFile); return ERROR; } fclose(pFile); pFile = fopen("myfile.txt", "r"); printf("文件内容是："); while ((ch = fgetc(pFile)) != EOF) { source[i++] = ch; } source[i] = ' '; printf("%sn", source); fclose(pFile); return OK; } Status WordCount(char* data, NumCount* tempCnt) { int flag; //判断是否已经记录 int len = strlen(data); for (int i = 0; i < len; ++i) { flag = 0; for (int j = 0; j < tempCnt->length; ++j) { if (tempCnt->count[j].ch == data[i]) //若已有记录，直接++ { ++tempCnt->count[j].cnt; flag = 1; break; } } if (!flag) //若未记录，则新增 { tempCnt->count[tempCnt->length].ch = data[i]; ++tempCnt->count[tempCnt->length].cnt; ++tempCnt->length; } } return OK; } Status Show(NumCount* tempCnt) { printf("长度为%dn", tempCnt->length); for (int i = 0; i < tempCnt->length; ++i) { printf("字符%c出现%d次n", tempCnt->count[i].ch, tempCnt->count[i].cnt); } printf("n"); return OK; } Status select(HuffmanTree HT, int top, int* s1, int* s2) { int min = INT_MAX; for (int i = 1; i <= top; ++i) //选择没有双亲的结点中，权重最小的结点 { if (HT[i].weight < min && HT[i].parent == 0) { min = HT[i].weight; *s1 = i; } } min = INT_MAX; for (int i = 0; i <= top; ++i) //选择没有双亲的结点中，权重次小的结点 { if (HT[i].weight < min && i != *s1 && HT[i].parent == 0) { min = HT[i].weight; *s2 = i; } } return OK; } Status CreateHuffmanTree(HuffmanTree& HT, int length, NumCount cntarray) { if (length <= 1) return ERROR; int s1, s2; int m = length * 2 - 1; //没有度为1的结点，则总结点数是2 * 叶子结点数 - 1个 HT = (HuffmanTree)malloc(sizeof(HTNode) * (m + 1)); for (int i = 1; i <= m; ++i) //初始化 { HT[i].parent = 0; HT[i].leftChild = 0; HT[i].rightChild = 0; } for (int i = 1; i <= length; ++i) { HT[i].data = cntarray.count[i - 1].ch; HT[i].weight = cntarray.count[i - 1].cnt; } for (int i = length + 1; i <= m; ++i) { select(HT, i - 1, &s1, &s2); //从前面的范围里选中权重最小的两个结点 HT[s1].parent = i; HT[s2].parent = i; HT[i].leftChild = s1; HT[i].rightChild = s2; HT[i].weight = HT[s1].weight + HT[s2].weight; //得到一个新结点 } return OK; } Status CreateHuffmanCode(HuffmanTree HT, HuffmanCode& HC, int length) { HC = (HuffmanCode)malloc(sizeof(HCode) * (length + 1)); char* cd = (char*)malloc(sizeof(char) * length); //存储代码的临时空间 cd[length - 1] = ' '; //方便之后调用strcpy函数 int c, f, start; for (int i = 1; i <= length; ++i) { start = length - 1; //start表示编码在临时空间内的起始下标，由于是从叶子节点回溯，所以是从最后开始 c = i; f = HT[c].parent; while (f != 0) { --start; //由于是回溯，所以从临时空间的最后往回计 if (HT[f].leftChild == c) cd[start] = '0'; else cd[start] = '1'; c = f; f = HT[c].parent; } HC[i].str = (char*)malloc(sizeof(char) * (length - start)); // 最后，实际使用的编码空间大小是length-start HC[i].data = HT[i].data; strcpy(HC[i].str, &cd[start]); // 从实际起始地址开始，拷贝到编码结构中 } free(cd); } Status Encode(char* data, HuffmanCode HC, int length) { FILE* pFile; pFile = fopen("mycode.txt", "w"); for (int i = 0; i < strlen(data); ++i) //依次读入数据，查找对应的编码，写入编码文件 { for (int j = 1; j <= length; ++j) { if (data[i] == HC[j].data) { fputs(HC[j].str, pFile); } } } fclose(pFile); printf("编码文件已写入n"); return OK; } Status Decode(HuffmanTree HT, int length) { char* codetxt = (char*)malloc(sizeof(char) * (MAXSIZE * length)); FILE* pFile; pFile = fopen("mycode.txt", "r"); fgets(codetxt, MAXSIZE * length, pFile); fclose(pFile); FILE* outfile; outfile = fopen("mytxt.txt", "w"); int root = 2 * length - 1; //从根结点开始遍历 for (int i = 0; i < strlen(codetxt); ++i) { if (codetxt[i] == '0') root = HT[root].leftChild; //为0表示向左遍历 else if (codetxt[i] == '1') root = HT[root].rightChild; //为1表示向右遍历 if (HT[root].leftChild == 0 && HT[root].rightChild == 0) //如果已经是叶子结点，输出到文件中，然后重新返回到根结点 { putc(HT[root].data, outfile); root = 2 * length - 1; } } fclose(outfile); printf("输出文件已写入n"); return OK; } void test() { char data[MAXSIZE]; NumCount Cntarray; ReadData(data); //读入数据 WordCount(data, &Cntarray); //统计次数 //Show(&Cntarray); //查看每个单词出现的次数 HuffmanTree tree; CreateHuffmanTree(tree, Cntarray.length, Cntarray); //建树 HuffmanCode code; CreateHuffmanCode(tree, code, Cntarray.length); //创建编码 Encode(data, code, Cntarray.length); //生成编码文件 Decode(tree, Cntarray.length); //解码 printf("请查看生成的TXT文件以检查结果n"); return; } int main() { test(); return 0; }
