如何用C语言编写哈夫曼树代码？

本文共计1804个文字，预计阅读时间需要8分钟。

本文以家庭分享为例，展示了使用C语言实现哈伯曼树的完整代码。代码内容如下：

c#include #include

#define MAX_TREE_HT 100

// 哈伯曼树节点struct MinHeapNode { char data; unsigned freq; struct MinHeapNode *left, *right;};

// 哈伯曼树struct MinHeap { unsigned size; unsigned capacity; struct MinHeapNode** array;};

// 创建一个新节点struct MinHeapNode* newNode(char data, unsigned freq) { struct MinHeapNode* temp=(struct MinHeapNode*)malloc(sizeof(struct MinHeapNode)); temp->left=temp->right=NULL; temp->data=data; temp->freq=freq; return temp;}

// 创建一个哈伯曼树struct MinHeap* createMinHeap(unsigned capacity) { struct MinHeap* minHeap=(struct MinHeap*)malloc(sizeof(struct MinHeap)); minHeap->size=0; minHeap->capacity=capacity; minHeap->array=(struct MinHeapNode**)malloc(minHeap->capacity * sizeof(struct MinHeapNode*)); return minHeap;}

// 交换两个哈伯曼树节点void swapMinHeapNode(struct MinHeapNode a, struct MinHeapNode b) { struct MinHeapNode* t=*a; *a=*b; *b=t;}

// 最小堆化void minHeapify(struct MinHeap* minHeap, int idx) { int smallest=idx; int left=2 * idx + 1; int right=2 * idx + 2;

if (left size && minHeap->array[left]->freq array[smallest]->freq) smallest=left;

if (right size && minHeap->array[right]->freq array[smallest]->freq) smallest=right;

if (smallest !=idx) { swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]); minHeapify(minHeap, smallest); }}

// 检查堆是否为空int isEmpty(struct MinHeap* minHeap) { return minHeap->size==0;}

// 提取最小频率节点struct MinHeapNode* extractMin(struct MinHeap* minHeap) { struct MinHeapNode* temp=minHeap->array[0]; minHeap->array[0]=minHeap->array[minHeap->size - 1]; --minHeap->size; minHeapify(minHeap, 0); return temp;}

// 插入一个新节点到最小堆void insertMinHeap(struct MinHeap* minHeap, struct MinHeapNode* minHeapNode) { ++minHeap->size; int i=minHeap->size - 1;

while (i && minHeapNode->freq array[(i - 1) / 2]->freq) { minHeap->array[i]=minHeap->array[(i - 1) / 2]; i=(i - 1) / 2; } minHeap->array[i]=minHeapNode;}

// 构建最小堆void buildMinHeap(struct MinHeap* minHeap) { int n=minHeap->size - 1; int i;

for (i=(n - 1) / 2; i >=0; --i) minHeapify(minHeap, i);}

// 判断是否是叶子节点int isLeaf(struct MinHeapNode* root) { return !(root->left) && !(root->right);}

// 创建一个最小堆struct MinHeap* createAndBuildMinHeap(char data[], int freq[], int size) { struct MinHeap* minHeap=createMinHeap(size);

for (int i=0; i array[i]=newNode(data[i], freq[i]);

minHeap->size=size; buildMinHeap(minHeap);

return minHeap;}

// 创建哈伯曼树struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top;

// 创建一个最小堆 struct MinHeap* minHeap=createAndBuildMinHeap(data, freq, size);

while (!isEmpty(minHeap)) { // 提取两个最小频率的节点 left=extractMin(minHeap); right=extractMin(minHeap);

// 创建一个新的内部节点，频率为两个节点的频率之和 top=newNode('$', left->freq + right->freq);

top->left=left; top->right=right;

// 将新节点插入最小堆 insertMinHeap(minHeap, top); }

// 返回哈伯曼树的根节点 return extractMin(minHeap);}

// 打印哈伯曼编码void printCodes(struct MinHeapNode* root, int arr[], int top) { if (root->left) { arr[top]=0; printCodes(root->left, arr, top + 1); }

if (root->right) { arr[top]=1; printCodes(root->right, arr, top + 1); }

if (isLeaf(root)) { printf(%c: , root->data); for (int i=0; i

// 主函数int main() { char arr[]={ 'a', 'b', 'c', 'd', 'e', 'f' }; int freq[]={ 5, 9, 12, 13, 16, 45 }; int size=sizeof(arr) / sizeof(arr[0]);

struct MinHeapNode* root=buildHuffmanTree(arr, freq, size);

int arr1[MAX_TREE_HT], top=0; printCodes(root, arr1, top);

return 0;}

本文实例为大家分享了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; }

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