[转载]霍夫曼树的详细说明，实现代码和霍夫曼编码示例

二叉树-霍夫曼树（最佳二叉树）中有一种特殊的树，它通过一些规则（权重）构造霍夫曼二叉树. 在这个二叉树中，只有叶子节点是有效数据节点（非常重要），引入了其他非叶子节点来构造霍夫曼！

霍夫曼编码是由霍夫曼树执行的一种编码. 通常，它由字符“ 0”和“ 1”表示. 编码的实现过程非常简单，只要实现了霍夫曼树，就规定将遍历左子树的节点编码为“ 0”，遍历右子树的节点编码为“ 1”，结束条件遍历到叶节点！因为如上所述: 霍夫曼树的叶子节点是有效的数据节点！

下图是霍夫曼编码示例的程序效果图:

这是逐步实现此过程的步骤:

如前所述，关键是构造霍夫曼树. 只要构造霍夫曼树，编码就非常简单，但是霍夫曼树的构造是基于实际情况，而不是随便构造的！由于它是二叉树，因此我们首先定义一个二叉树结构:

structtree

{

字符日期； //数据

布尔分钟； //叶子节点

int quanzhi; //重量

结构树*左，*您； //左右两个孩子

} * tre;

权重是我们需要关注的最重要的事情，因为我们想通过权重来构造权重，但是权重如何指定？当然要根据实际情况！叶子节点将其标记为叶子节点，方便以后编码！

为简单起见，第一个示例直接定义了多个霍夫曼树节点，然后通过这些节点构造最终的霍夫曼树！

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

tr是一个霍夫曼数组，其中每个元素都是霍夫曼树，我们的任务是“集成”这些元素并将它们连接起来以形成霍夫曼树. 最初，数组的每个元素都是未连接的，我们的任务是通过struct tree * zuo，* you;连接它们. //左右两个孩子，图像将形成二叉树.

我们首先通过语言叙述来构造霍夫曼二叉树:

体重5

b重量2

c体重9

d体重3

e体重6

首先，使用权重值最小的两个节点“集成”一个新节点. 节点的权重是两个最小节点的权重之和. 如下图所示:

然后，将这个新节点的权重与其余元素进行比较，仍然采用两个最小权重的节点来构造一个新节点，并重复此过程直到所有元素都被提取为止，在本例中为霍夫曼树，如下所示:

叶节点（即2、3、5、6、9）是有效的数据节点！节点在构建过程中的左右顺序不影响Ha

Manman树的构造，但是会导致不同的编码，当然，只要不显示前缀代码，编码都是正确的.

实现算法:

算法种类繁多，关键是要了解其构造原理.

通过上面的示例，我们知道要构建霍夫曼树，所需的节点数为有效数据节点的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]的状态变为:

treetr [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 ///////////////

静态inthfmb = 0;

structtree

{

字符日期； //数据

布尔分钟； //叶子节点

int quanzhi; //重量

结构树*左，*您； //左右两个孩子

} * tre;

structshfm

{

字符日期； //字符数据

char bianm [11]； //霍夫曼编码，最大编码为11（可以根据实际情况修改！）

} hfm [100]; //与霍夫曼编码相对应的真实数据表

voidgettree（tree tr []，int shij哈夫曼树节点，int youx）//构造霍夫曼树，tr树集合，shij集合的实际数据编号，youx集合的有效数据编号

{

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

如果（2 * youx-1！= shij）

{

printf（“参数不匹配！”）；

返回；

}

int c = 0;

while（youx！= shij）// //有效数字==实际数字时，构造完成！

{

for（int i = c; i

{

//每个周期取两个最小值并将这两个最小值放在当前周期的前两位

if（tr [i] .quanzhi

{

树p = tr [i];

tr [i] = tr [c];

tr [c] = p;

}

if（tr [i] .quanzhi

{

树p = tr [i];

tr [i] = tr [c + 1];

tr [c +1] = p;

}

}

//以下是由最小值构造的新树

tr [youx] .quanzhi = tr [c] .quanzhi + tr [c + 1] .quanzhi;

tr [youx] .you =＆tr [c]; //新树的右子节点指向当前循环的最小值之一

tr [youx] .zuo =＆tr [c +1]; //新树的左子节点指向当前循环的最小值之一

youx ++; //将新树插入到当前有效数据号之后，并使有效数据号+1

c = c + 2;

}

}

voidbianltree（tree * tr，char ch []）//霍夫曼编码

{

//通过遍历树，获取每个节点的代码

static int i = 0;

if（！tr-> min）//叶子节点

{

ch [i] ='0';

i ++;

bianltree（tr-> zuo，ch）; //左侧节点编码为“ 0”

ch [i] ='1';

i ++;

bianltree（tr-> you，ch）; //右节点编码为“ 1”

}

如果（tr->分钟）

{

ch [i] =''; //结束标记（）

printf（“％c％sn”，tr->日期，ch）；

hfm [hfmb] .date = tr->日期；

int j = 0;

同时（j！= i || i> 10）

{

hfm [hfmb] .bianm [j] = ch [j];

j ++;

} //保存编码映射表

hfmb ++;

}

i-; //递归进入右叶子节点时，取消当前分配（当前必须是左叶子节点）

}

int_tmain（int argc，_TCHAR * argv []）

{

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

// printf（“％dn”，sizeof（tr）/ sizeof（tree））;

gettree（tr，9,5）;

char ch [100];

// printf（“％sn”，ch）;

bianltree（＆tr [8]，ch）;

返回0；

}

效果:

gettree（）函数是构造霍夫曼树的过程，bianltree（）是编码霍夫曼树struct shfm的过程

结构是一个映射表，用于存储字符数据及其霍夫曼编码. 是否可以使用. 在这里使用它的原因是它可以通过一次遍历获得所有元素的编码. 就是这样，争取时间空间.

以下是霍夫曼的一些应用示例:

通过以上介绍，下面将介绍霍夫曼的实际应用.

此示例的模拟效果是: 通过传入字符串字符串，将返回字符串的编码. 并通过传递有效的编码来获取字符串！

完整的代码如下. 在上面的代码的基础上修改了代码，并对上面的代码进行了优化.

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

//

#include“ stdafx.h”

#include

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

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

静态inthfmb = 0;

structtree

{

字符日期； //数据

布尔分钟； //叶子节点

int quanzhi; //重量

结构树*左，*您； //左右两个孩子

} * tre;

structshfm

{

字符日期； //字符数据

int len; //代码长度

char bianm [11]； //霍夫曼编码，最大编码为11（可以根据实际情况修改！）

} hfm [100]; //与霍夫曼编码相对应的真实数据表

voidgettree（tree tr []，int shij，int youx）//构造霍夫曼树，tr树集合，shij集合的实际数据编号，youx集合的有效数据编号

{

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

如果（2 * youx-1！= shij）

{

printf（“参数不匹配！”）；

返回；

}

int c = 0;

while（youx！= shij）// //有效数字==实际数字时，构造完成！

{

for（int i = c; i

{

//每个周期取两个最小值并将这两个最小值放在当前周期的前两位

if（tr [i] .quanzhi

{

树p = tr [i];

tr [i] = tr [c];

tr [c] = p;

}

if（tr [i] .quanzhi

{

树p = tr [i];

tr [i] = tr [c + 1];

tr [c +1] = p;

}

}

//以下是由最小值构造的新树

tr [youx] .quanzhi = tr [c] .quanzhi + tr [c + 1] .quanzhi;

tr [youx] .you =＆tr [c]; //新树的右子节点指向当前循环的最小值之一

tr [youx] .zuo =＆tr [c +1]; //新树的左子节点指向当前循环的最小值之一

youx ++; //将新树插入到当前有效数据号之后，并使有效数据号+1

c = c + 2;

}

返回；

}

voidbianltree（tree * tr）//霍夫曼编码

{

//通过遍历树，获取每个节点的代码

静态字符[100];

static int i = 0;

if（！tr-> min）//叶子节点

{

ch [i] ='0';

i ++;

bianltree（tr-> zuo）; //左侧节点编码为“ 0”

ch [i] ='1';

i ++;

bianltree（tr->您）； //右节点编码为“ 1”

}

如果（tr->分钟）

{

ch [i] =''; //结束标记（）

printf（“％c％sn”，tr->日期，ch）；

hfm [hfmb] .date = tr->日期；

hfm [hfmb] .len = i;

int j = 0;

同时（j！= i || i> 10）

{

hfm [hfmb] .bianm [j] = ch [j];

j ++;

} //保存编码映射表

hfmb ++;

}

i-; //递归进入右节点时，取消当前分配（当前必须是左叶节点）

}

voidchushihuahmf（树* hfmtree，char * str，int i）

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