本文实例为大家分享了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);//从叶节点回溯打印编码codevoid 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;}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。