哈夫曼编码数据结构c_数据结构哈夫曼树_数据结构哈夫曼树算法

*zuo,*you;//左右孩子 来连接起来，形象上就是构成一棵二叉树。

我们先通过语言叙述的方法来构造一棵哈夫曼二叉树：

a 权值5

b权值2

c权值9

d权值3

e权值6

首先，取权值最小的两个节点“整合”出一个新的节点，该节点的权值为最小两个节点权值之和。如下图：

然后，将这个新的节点与剩下元素进行权值比较，依旧取最小的两个权值节点构造新的节点，反复这个过程，直到取完所有元素，本例的哈夫曼树如下图：

其中叶子节点（也就是2,3,5,6,9）是有效的数据节点！构造时节点的左右顺序并不影响哈

曼树的构造，但会导致出现不同的编码，当然编码只要不出现前缀码就是正确的编码。

实现算法：

实现算法有很多种，关键是要理解它构造的原理。

通过上面的例子，我们知道构造一个哈夫曼树，需要的节点数数有效数据节点的2*n-1,其中

n是有效数据的个数，如上面例子，有效数据个数有5个，但最终构造出的哈夫曼树有2*5-1=9

个节点，所以根据这个性质就可写出一种算法：

treetr[9]={{'a',true,5},{'b',true,2},{'c',true,9},{'d',true,3},{'e',true,6}};

5个数据所以需要9个空间，其中9-5=4个空间是给那些无效节点使用的（哈夫曼树种非叶

子节点）。

首先，我们遍历这个数组，找到最小的两个元素。

然后，将他们移动到前面，并将权值求和构造出新的节点，新的节点左右子树指向最小的两个元素，将这个新节点插入有效数据后面。

最后，从第2+1个元素(前面两个无需遍历了)开始重新遍历。

重复上述过程，直到数组填满，填满后的最后一个元素就是最终的哈夫曼树。

如第一次遍历后数组tr[9]状态就变为：

tree tr[9]={ {'d',true,3},{'b',true,2},{'c',true,9},{'a',true,5},{'e',true,6},{‘’,false,5,tr[0],tr[1]}}

最小的两个元素移到了前面，有效数据增加了一个,并且新节点左右子树指向前面两个元素。数据结构哈夫曼树

完整哈夫曼实现代码如下;

// hfm.cpp : 定义控制台应用程序的入口点。

//

#include 'stdafx.h'

#include

////////////贵州民族大学///////////////

///////////编译环境vs2010//////////////

static int hfmb=0;

struct tree

{

char date;//数据

bool min;//叶子节点

int quanzhi;//权值

struct tree *zuo,*you;//左右孩子

}*tre;

struct shfm

{

char date;//字符数据

char bianm[11];//哈夫曼编码,最大编码数为11（可根据实际修改！）

}hfm[100];//哈夫曼编码对应真实数据表

void gettree(tree tr[],int shij,intyoux)//构造哈夫曼树,tr树集合，shij集合实际数据个数,youx集合有效数据个数

{

//模拟动态增长数组，每次构造新的树就插入有效数据后面

if (2*youx-1!=shij)

{

printf('参数不符合！');

return;

}

int c=0;

while(youx!=shij)//当有效个数==实际个数时，构造完成！

{

for (int i=c;i

{

//每次循环取两个最小值并将两个最小值放置在当前循环起始两位

if (tr[i].quanzhi

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-27154-1.html