哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛，如，JPEG中就应用了哈夫曼编码。 首先介绍什么是哈夫曼树。哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的 路径长度(若根结点为0层，叶结点到根结点的路径长度为叶结点的层数)。下面为大家详细介绍了C语言实现哈夫曼树的构建。

1、路径和路径长度

在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。

2、结点的权及带权路径长度

若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。

3、树的带权路径长度

树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

/* 哈夫曼树的结构体 */

typedef struct stHuNode

{

int data; //权值

struct stHuNode* lchild, *rchild;

}HUNODE;

/*

* 找出权值数组里面,最小的两个权值下标

* 函数请参：HUNODE *pArray[] 存放节点的指针数组

int n 数组里面的元素个数

int* p1 存放最小权值的下标

int* p2 存放第二小权值的下标

*/

int findSmallData(HUNODE *pArray[] ,int n,int* p1, int* p2)

{

int index = 0;

int fir_small = 0xffff, sec_small = 0xffff;

if(pArray == NULL)

{

return 1;

}

for(index = 0; index < n; index++)

{

/* 当前的下标下面是有节点的*/

if(pArray[index] != NULL)

{

if(pArray[index]->data < fir_small)

{

sec_small = fir_small;

fir_small = pArray[index]->data;

*p2 = *p1;

*p1 = index;

}

else if(pArray[index]->data < sec_small)

{

sec_small = pArray[index]->data;

*p2 = index;

}

}

}

return 0;

}

/*

* 函数功能：构建哈夫曼树

* 函数请参：int* a 权值数组

int n 这个数组里面有多少个数据

*/

HUNODE* createHuTree(int* a, int n)

{

int index = 0;

int fir_small = 0, sec_small = 0;

/* 定义一个指针数组,最大是100 */

HUNODE *pArray[100];

HUNODE *pNewNode = NULL;

/* 先创建n个root节点*/

memset(pArray,0,sizeof(HUNODE)*n);

for(index = 0; index < n; index++)

{

pNewNode = (HUNODE*)malloc(sizeof(HUNODE));

memset(pNewNode,0,sizeof(HUNODE));

pNewNode->data = a[index];

pNewNode->lchild = NULL;

pNewNode->rchild = NULL;

/* 把这个节点存放在指针数组中去 */

pArray[index] = pNewNode;

}

/* 构建哈夫曼树 */

for(index = 0; index < n-1; index++)

{

/* fir_small 存放最小权值的下标 sec_small存放第二个小的权值下标*/

findSmallData(pArray,n,&fir_small,&sec_small);

/* 分配节点内存 */

pNewNode = (HUNODE*)malloc(sizeof(HUNODE));

memset(pNewNode,0,sizeof(HUNODE));

pNewNode->data = pArray[fir_small]->data + pArray[sec_small]->data;

/* 最小的是左孩子，第二小的是右孩子 */

pNewNode->lchild = pArray[fir_small];

pNewNode->rchild = pArray[sec_small];

/* 把新的节点放入到指针数组里面去 */

pArray[fir_small] = NULL;

pArray[sec_small] = pNewNode;

}

return pNewNode;

}

/* 前序遍历该二叉树 */

void preOrderHuffMan(HUNODE* root)

{

if(root)

{

printf("%d ",root->data);

preOrderHuffMan(root->lchild);

preOrderHuffMan(root->rchild);

}

}

int main()

{

int a[4] = {7,5,2,4};

HUNODE* root = NULL;

/* 构建哈夫曼树 */

root = createHuTree(a,4);

/* 前序遍历 */

preOrderHuffMan(root);

printf("\n");

return 0;

}

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

文章来源：电子发烧网，版权声明：转载文章来自公开网络，版权归作者本人所有，推送文章除非无法确认，我们都会注明作者和来源。如果出处有误或侵犯到原作者权益，请与我们联系删除或授权事宜。