本文实例为大家分享了C语言实现哈夫曼树的具体代码，供大家参考，具体内容如下
//哈夫曼树C语言实现
#include <stdio.h>
#include <stdlib.h>
typedef struct HuffmanNode
{
char letter;//存储的字符，叶节点为字母，非叶节点为#
struct HuffmanNode *parent;//父亲结点
int code;//如果为父亲结点的左孩子，则为0，右孩子为1
}HuffmanNode;
typedef struct HeapNode
{
int rate;//出现频率
HuffmanNode *node;//对应于哈夫曼树中的结点
}HeapNode;
/*------------------全局变量----------------------*/
int heapSize;//堆大小
int num;//记录字符数量
HeapNode *heap;//堆数组
char *letter;//字符数组
int *rate;//字符出现频率
HuffmanNode **array; //记录叶节点的数组，打印编码的时候可以从叶结点回溯向上
char ch;
/*----------------------函数声明-------------------------*/
void init(int numOfLetters);//初始化变量
void input();//输入数组
int parent(int i);//求父节点
int left(int i);//求左孩子
int right(int i);//求右孩子
void swap(int i,int j);//交换函数
void heapIfy(int i,int localHeapSize);//维持堆性质函数，使用前提为左右子树均为最小堆
void buildHeap();//初始化堆
HeapNode* extractMin();//去掉并返回堆中最小的元素
void heapInsert(int rate,HuffmanNode *p);//向堆中插入数据（前提：堆已经初始化）
HuffmanNode* buildTree();//构造哈夫曼树
void display();//显示函数
void backPrint(HuffmanNode *p,HuffmanNode *root);//从叶节点回溯打印编码code
/*----------------------函数实现-------------------------*/
void init(int numOfLetters)
{
heapSize=numOfLetters;//堆大小初始化为字母数
num=numOfLetters;//记录字符数量
heap=(HeapNode*)malloc((numOfLetters+1)*sizeof(HeapNode));//分配堆空间，最多只需要字符的个数，因为合并过程中删除两个，插入一个
letter=(char*)malloc((numOfLetters+1)*sizeof(char));//用于存储字符
rate=(int *)malloc((numOfLetters+1)*sizeof(int));//用于存储字符出现频率
array=(HuffmanNode **)malloc((numOfLetters+1)*sizeof(HuffmanNode));//记录叶节点的数组，打印编码的时候可以从叶结点回溯向上
}
void input()
{
int i=1;
while(i<=heapSize)
{
printf("输入第%d个字符n",i);
scanf("%c",&letter[i]);ch=getchar();
printf("输入第%d个字符的频度n",i);
scanf("%d",&rate[i]);ch=getchar();
//向堆中插入各个结点
heap[i].rate=rate[i];
heap[i].node=(HuffmanNode *)malloc(sizeof(HuffmanNode));
array[i]=heap[i].node;
heap[i].node->parent=NULL;
heap[i].node->letter=letter[i];
i++;
}
}
int parent(int i)
{
return i/2;
}
int left(int i)
{
return 2*i;
}
int right(int i)
{
return 2*i+1;
}
void swap(int i,int j) //交换结构体数组，需要交换结构体内数据
{
int rate;
HuffmanNode *p;
rate=heap[i].rate;
p=heap[i].node;
heap[i].rate=heap[j].rate;
heap[i].node=heap[j].node;
heap[j].rate=rate;
heap[j].node=p;
}
void heapIfy(int i,int localHeapSize)//维持堆性质函数，使用前提为左右子树均为最小堆
{
int l=left(i);
int r=right(i);
int least=i;
//找出heap成员rate 的i,left(i),right(i)的最小值
if(l<=localHeapSize&&heap[least].rate>heap[l].rate)
{
least=l;
}
if(r<=localHeapSize&&heap[least].rate>heap[r].rate)
{
least=r;
}
if(least!=i)
{
swap(i,least);
heapIfy(least,localHeapSize);
}
}
void buildHeap()//初始化堆
{
int i=0;
for(i=heapSize/2;i>=1;i--)
{
heapIfy(i,heapSize);
}
}
HeapNode* extractMin()
{
if(heapSize>=1)
{
HeapNode *min;
swap(1,heapSize);
min=&heap[heapSize];
--heapSize;
heapIfy(1,heapSize);
return min;
}
else
{
printf("堆中没有元素");
return NULL;
}
}
void heapInsert(int rate,HuffmanNode *p)
{
++heapSize;
int i=heapSize;
while(i>1&&heap[parent(i)].rate>rate)
{
heap[i].rate=heap[parent(i)].rate;
heap[i].node=heap[parent(i)].node;
i=parent(i);
}
heap[i].rate=rate;
heap[i].node=p;
}
HuffmanNode* buildTree()
{
buildHeap();//初始化堆
HeapNode *p;//用于临时存储最小堆结点
HeapNode *q;//用于临时存储次小堆结点
int count=heapSize;
int i;
for(i=1;i<=count-1;i++)
{
HuffmanNode *tree=(HuffmanNode*)malloc(sizeof(HuffmanNode));//生成内结点
tree->letter='#';//内结点的字符记作#，没有实际意义
p=extractMin();
q=extractMin();
p->node->parent=tree;
p->node->code=0;
q->node->parent=tree;
q->node->code=1;
//printf("%c:%d",p->node->letter,p->node->code);
//printf("n"); printf("%c:%d",q->node->letter,q->node->code); printf("n");//测试
heapInsert(p->rate+q->rate,tree);//插入堆中
}
return extractMin()->node;
}
void display()
{
HuffmanNode*p=buildTree();////哈夫曼树的根节点地址
int i=1;
while(i<=num)
{
printf("%c:",array[i]->letter);
backPrint(array[i],p);
printf("n");
i++;
}
}
void backPrint(HuffmanNode *p,HuffmanNode *root)
{
if(p!=root)
{
backPrint(p->parent,root);
printf("%d",p->code);//printf("++++");//测试
}
}
int mAIn(int argc ,char* argv[])
{
int number;
printf("输入的字符个数为：n");
scanf("%d",&number);
ch=getchar();
init(number);
input();
display();
system("PAUSE");
return 0;
}
