树：哈夫曼树和哈夫曼编码的详细介绍以及代码实现

#pragma once
#ifndef __HUFFQUEUE_H__
#define __HUFFQUEUE_H__
#include "HuffmanTree.h"//哈夫曼结点的队列 结点的数据结构
typedef struct HuffQueueNode
{HuffmanNode* treeNode;//哈夫曼树结点int weightNum;//权值struct HuffQueueNode* next;//指向下一个结点
}HuffQueueNode;//哈夫曼结点组成的队列数据结构&＃xff0c;由于插入数据&＃xff08;根据权值&＃xff09;和删除数据&＃xff08;删除队头的数据&＃xff09;的特性&＃xff0c;需要结点个数 和 头指针
typedef struct HuffQueue
{int size;HuffQueueNode* first;
}HuffQueue;//初始化队列
void InitHuffQueue(HuffQueue** queue);//获取结点&＃xff08;出队操作&＃xff09;&＃xff0c;从队头出队
HuffQueueNode* GetHuffQueueNode(HuffQueue* queue);//插入结点&＃xff08;入队操作&＃xff09;&＃xff0c;特殊插入 根据权值大小进行有序的插入结点 非结尾处插入
void AddHuffQueueNode(HuffQueue* queue, HuffmanNode* treeNode, int weightNum);#endif // !__HUFFQUEUE_H__

BuildHuffmanTree函数

//根据用户提供字符集&＃xff0c;生成对应的哈夫曼树
HuffmanTree BuildHuffmanTree(char* inputString)
{//统计每个字符出现的权值int charWeight[MAX_SZ] &＃61; { 0 };for (int i &＃61; 0; i data &＃61; i;treeNode->lchild &＃61; treeNode->rchild &＃61; NULL;AddHuffQueueNode(queue, treeNode, charWeight[i]);}}//根据哈夫曼树创建原理构建哈夫曼树//核心就是将权值最小的2个结点&＃xff0c;取出作为新创建树结点的孩子结点&＃xff0c;新创建树结点的权值为它们之和&＃xff0c;然后放回树结点队列//一直这样循环进行操作&＃xff0c;直到队列中最后剩一个结点&＃xff0c;它就是树的根结点。while (queue->size !&＃61; 1){HuffQueueNode* node1 &＃61; GetHuffQueueNode(queue);HuffQueueNode* node2 &＃61; GetHuffQueueNode(queue);HuffmanNode* treeNode &＃61; (HuffmanNode*)malloc(sizeof(HuffmanNode));treeNode->data &＃61; &＃39;\0&＃39;;treeNode->lchild &＃61; node1->treeNode;treeNode->rchild &＃61; node2->treeNode;int weightNum &＃61; node1->weightNum &＃43; node2->weightNum;AddHuffQueueNode(queue, treeNode, weightNum);}return queue->first->treeNode;
}

哈夫曼编码

char* encode(HuffmanTable* table,char* src)
{char* encode &＃61; (char*)calloc(sizeof(char)*MAX_ENCODE,1);for (int i &＃61; 0; i front;while (iterator !&＃61; NULL){if (iterator->data &＃61;&＃61; ch){strcat(encode, iterator->encode);break;}iterator &＃61; iterator->next;}if (iterator &＃61;&＃61; NULL){printf("哈夫曼编码表中没有字符%c对应的哈夫曼编码&＃xff01;\n",ch);return NULL;}}return encode;
}

decode函数

//根据用户提供的哈夫曼编码进行解码
char* decode(HuffmanTree root,char* encode)
{char* decode &＃61; (char*)calloc(MAX_SZ, 1);HuffmanTree tree &＃61; root;for (int i &＃61; 0; i lchild;}else//1 往右走{tree &＃61; tree->rchild;}//走到头&＃xff0c;也就是找到相应的 源字符了if (tree->lchild &＃61;&＃61; NULL && tree->rchild &＃61;&＃61; NULL){strncat(decode, &tree->data, 1);//找到字符后&＃xff0c;树节点回到根结点&＃xff0c;继续解码tree &＃61; root;}}return decode;
}

#pragma once
#ifndef __HUFFQUEUE_H__
#define __HUFFQUEUE_H__
#include "HuffmanTree.h"//哈夫曼结点的队列 结点的数据结构
typedef struct HuffQueueNode
{HuffmanNode* treeNode;//哈夫曼树结点int weightNum;//权值struct HuffQueueNode* next;//指向下一个结点
}HuffQueueNode;//哈夫曼结点组成的队列数据结构&＃xff0c;由于插入数据&＃xff08;根据权值&＃xff09;和删除数据&＃xff08;删除队头的数据&＃xff09;的特性&＃xff0c;需要结点个数 和 头指针
typedef struct HuffQueue
{int size;HuffQueueNode* first;
}HuffQueue;//初始化队列
void InitHuffQueue(HuffQueue** queue);//获取结点&＃xff08;出队操作&＃xff09;&＃xff0c;从队头出队
HuffQueueNode* GetHuffQueueNode(HuffQueue* queue);//插入结点&＃xff08;入队操作&＃xff09;&＃xff0c;特殊插入 根据权值大小进行有序的插入结点 非结尾处插入
void AddHuffQueueNode(HuffQueue* queue, HuffmanNode* treeNode, int weightNum);#endif // !__HUFFQUEUE_H__

HuffQueue.c

#include "HuffQueue.h"
#include //初始化队列
void InitHuffQueue(HuffQueue** queue)
{*queue &＃61; (HuffQueue*)malloc(sizeof(HuffQueue));(*queue)->size &＃61; 0;(*queue)->first &＃61; NULL;
}//获取结点&＃xff08;出队操作&＃xff09;&＃xff0c;只需要树节点的数据&＃xff0c;故只返回树节点数据
HuffQueueNode* GetHuffQueueNode(HuffQueue* queue)
{if (NULL &＃61;&＃61; queue || 0 &＃61;&＃61; queue->size || NULL &＃61;&＃61; queue->first){return NULL;}HuffQueueNode* queueNode &＃61; queue->first;queue->first &＃61; queue->first->next;queue->size--;return queueNode;}//插入结点&＃xff08;入队操作&＃xff09;&＃xff0c;特殊插入 根据权值大小进行有序的插入结点 非队尾处插入
void AddHuffQueueNode(HuffQueue* queue, HuffmanNode* treeNode, int weightNum)
{HuffQueueNode *queueNode &＃61; (HuffQueueNode*)malloc(sizeof(HuffQueueNode));queueNode->weightNum &＃61; weightNum;queueNode->treeNode &＃61; treeNode;queueNode->next &＃61; NULL;//队列为空if (0 &＃61;&＃61; queue->size){queue->first &＃61; queueNode;queue->size&＃43;&＃43;;return;}else{//比第一个结点权值都小if (weightNum first->weightNum){queueNode->next &＃61; queue->first;queue->first &＃61; queueNode;queue->size&＃43;&＃43;;return;}HuffQueueNode* iterator &＃61; queue->first;HuffQueueNode* pre &＃61; NULL;while (iterator !&＃61; NULL && weightNum > iterator->weightNum){pre &＃61; iterator;iterator &＃61; iterator->next;}//在队列中找到自己位置&＃xff0c;将其插入其中if (NULL !&＃61; iterator){queueNode->next &＃61; iterator->next;iterator->next &＃61; queueNode;}//没找到&＃xff0c;说明自己权值最大&＃xff0c;插入到末尾else{pre->next &＃61; queueNode;}queue->size&＃43;&＃43;;return;}return;
}

HuffmanTree.h

#pragma once
#ifndef __HUFFMANTREE_H__
#define __HUFFMANTREE_H__//创建哈夫曼树提供的字符的最大长度
#define MAX_SZ 256
//哈夫曼编码字符串最大长度
#define MAX_ENCODE 1024
//哈夫曼树结点数据结构
typedef struct HuffmanNode
{char data;struct HuffmanNode *lchild, *rchild;
}HuffmanNode,*HuffmanTree;//哈夫曼编码表结点数据结构
typedef struct HuffmanTableNode
{char data; //字符char *encode; //字符对应的哈夫曼编码struct HuffmanTableNode *next;
}HuffmanTableNode;
//哈夫曼编码表数据结构
typedef struct HuffmanTable
{HuffmanTableNode* front;//指向队头元素HuffmanTableNode* tail; //指向队尾元素
}HuffmanTable;//根据用户提供原始数据&＃xff0c;生成对应的哈夫曼树
HuffmanTree BuildHuffmanTree(char* inputString);//根据哈夫曼树 生成对应的哈夫曼编码表
HuffmanTable* BuildHuffmanTable(HuffmanTree tree);//对用户提供的源字符进行哈夫曼编码
char* encode(HuffmanTable* table, char* src);//根据用户提供的哈夫曼编码进行解码
char* decode(HuffmanTree root, char* encode);//遍历哈夫曼编码表
void TraverseHuffmanTable(HuffmanTable* table);
#endif // !__HUFFMANTREE_H__


#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include "HuffmanTree.h"
#include "HuffQueue.h"//根据用户提供字符集&＃xff0c;生成对应的哈夫曼树
HuffmanTree BuildHuffmanTree(char* inputString)
{//统计每个字符出现的权值int charWeight[MAX_SZ] &＃61; { 0 };for (int i &＃61; 0; i data &＃61; i;treeNode->lchild &＃61; treeNode->rchild &＃61; NULL;AddHuffQueueNode(queue, treeNode, charWeight[i]);}}//根据哈夫曼树创建原理构建哈夫曼树//核心就是将权值最小的2个结点&＃xff0c;取出作为新创建树结点的孩子结点&＃xff0c;新创建树结点的权值为它们之和&＃xff0c;然后放回树结点队列//一直这样循环进行操作&＃xff0c;直到队列中最后剩一个结点&＃xff0c;它就是树的根结点。while (queue->size !&＃61; 1){HuffQueueNode* node1 &＃61; GetHuffQueueNode(queue);HuffQueueNode* node2 &＃61; GetHuffQueueNode(queue);HuffmanNode* treeNode &＃61; (HuffmanNode*)malloc(sizeof(HuffmanNode));treeNode->data &＃61; &＃39;\0&＃39;;treeNode->lchild &＃61; node1->treeNode;treeNode->rchild &＃61; node2->treeNode;int weightNum &＃61; node1->weightNum &＃43; node2->weightNum;AddHuffQueueNode(queue, treeNode, weightNum);}return queue->first->treeNode;
}
/*
递归遍历哈夫曼树
depth 树的深度
tree 哈夫曼树
hTable 哈夫曼编码表
encode 字符对应的哈夫曼编码
*/
void traverseHuffTree(HuffmanTable* hTable,HuffmanTree tree,char* encode,int depth)
{if (NULL &＃61;&＃61; tree->lchild && NULL &＃61;&＃61; tree->rchild){HuffmanTableNode* tableNode &＃61; (HuffmanTableNode*)malloc(sizeof(HuffmanTableNode));tableNode->data &＃61; tree->data;tableNode->next &＃61; NULL;encode[depth] &＃61; &＃39;\0&＃39;;tableNode->encode &＃61; (char*)malloc(depth&＃43;1);strcpy(tableNode->encode, encode);if (hTable->front &＃61;&＃61; NULL){hTable->front &＃61; hTable->tail &＃61; tableNode;}else{hTable->tail->next &＃61; tableNode;hTable->tail &＃61; tableNode;}}if (NULL !&＃61; tree->lchild){encode[depth] &＃61; &＃39;0&＃39;;//左分支代表0traverseHuffTree(hTable, tree->lchild, encode, depth&＃43;1);}if (NULL !&＃61; tree->rchild){encode[depth] &＃61; &＃39;1&＃39;;//右分支代表1traverseHuffTree(hTable, tree->rchild, encode, depth&＃43;1);}return;
}//根据哈夫曼树生成哈夫曼编码表
HuffmanTable * BuildHuffmanTable(HuffmanTree tree)
{HuffmanTable* hTable &＃61; (HuffmanTable*)malloc(sizeof(HuffmanTable));hTable->front &＃61; hTable->tail &＃61; NULL;char encode[MAX_SZ] &＃61; { 0 };traverseHuffTree(hTable, tree, encode, 0);return hTable;
}//对用户提供的源字符进行哈夫曼编码
char* encode(HuffmanTable* table,char* src)
{char* encode &＃61; (char*)calloc(sizeof(char)*MAX_ENCODE,1);for (int i &＃61; 0; i front;while (iterator !&＃61; NULL){if (iterator->data &＃61;&＃61; ch){strcat(encode, iterator->encode);break;}iterator &＃61; iterator->next;}if (iterator &＃61;&＃61; NULL){printf("哈夫曼编码表中没有字符%c对应的哈夫曼编码&＃xff01;\n",ch);return NULL;}}return encode;
}//根据用户提供的哈夫曼编码进行解码
char* decode(HuffmanTree root,char* encode)
{char* decode &＃61; (char*)calloc(MAX_SZ, 1);HuffmanTree tree &＃61; root;for (int i &＃61; 0; i lchild;}else//1 往右走{tree &＃61; tree->rchild;}//走到头&＃xff0c;也就是找到相应的 源字符了if (tree->lchild &＃61;&＃61; NULL && tree->rchild &＃61;&＃61; NULL){strncat(decode, &tree->data, 1);//找到字符后&＃xff0c;树节点回到根结点&＃xff0c;继续解码tree &＃61; root;}}return decode;
}//打印哈夫曼编码表
void TraverseHuffmanTable(HuffmanTable* table)
{HuffmanTableNode* node &＃61; table->front;while (node !&＃61; NULL){printf("源字符:%c ->哈夫曼编码:%s\n", node->data, node->encode);node &＃61; node->next;}
}int main(int argc, char *argv[])
{HuffmanTree tree &＃61; BuildHuffmanTree("aabbccc");HuffmanTable* table &＃61; BuildHuffmanTable(tree);TraverseHuffmanTable(table);char *src &＃61; "abc";char* dest &＃61; "10110101101";char* encode_str &＃61; encode(table, src);char* decode_str &＃61; decode(tree, dest);printf("原始字符串:%s ->哈夫曼编码:%s\n", src, encode_str);printf("哈夫曼编码:%s ->解码为:%s\n", dest, decode_str);return 0;
}

图解和运行测试

图解

int main(int argc, char *argv[])
{HuffmanTree tree &＃61; BuildHuffmanTree("aabbccc");HuffmanTable* table &＃61; BuildHuffmanTable(tree);TraverseHuffmanTable(table);char *src &＃61; "abc";char* dest &＃61; "10110101101";char* encode_str &＃61; encode(table, src);char* decode_str &＃61; decode(tree, dest);printf("原始字符串:%s ->哈夫曼编码:%s\n", src, encode_str);printf("哈夫曼编码:%s ->解码为:%s\n", dest, decode_str);return 0;
}