哈夫曼树的构造算法
先看一下哈夫曼树的构造规则是:
假设有n个权值,则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为:
(1) 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点);
(2) 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;
(3)从森林中删除选取的两棵树,并将新树加入森林;
(4)重复(2)、(3)步,直到森林中只剩一棵树为止,该树即为所求得的哈夫曼树。
用数据表示哈夫曼树的话,首先有n个权值点,其初始化就是从 0 到 n -1,先从这里面查找两个权值最小的结点,就是遍历一遍,把最小的值取出来。X1 和X2 要记录着两个权值在哪个位置。
然后把这两个权值加起来的和放回到数组n的位置,然后继续遍历这个数据,现在是从0 到n了,当然原来X1 和X2位置的两个点不用管,已经有父节点了。继续上述过程直到只有一个节点位置。
如 1 2 3 4 5 6构造哈夫曼树,先初始化parent 为 -1
1 2 3 4 5 6
parent -1 -1 -1 -1 -1 -1
先从上述中选取两个权值最小的节点 1 和 2,构造树变为3,放到数组6的位置,原权值序列变为:
1 2 3 4 5 6 3
parent 6 6 -1 -1 -1 -1 -1
继续选取 两个最小权值且parent为-1的点。找到3 和 3,放到数组7的位置,权值序列变为:
1 2 3 4 5 6 3 6
parent 6 6 7 -1 -1 -1 7 -1
继续选取 两个最小权值且parent为-1的点。找到4 和5,到数组8的位置,权值序列变为:
1 2 3 4 5 6 3 6 9
parent 6 6 7 8 8 -1 7 -1 -1
继续选取 两个最小权值且parent为-1的点。找到6 和6,到数组9的位置,权值序列变为:
1 2 3 4 5 6 3 6 9 12
parent 6 6 7 8 8 9 7 9 -1 -1
继续选取 两个最小权值且parent为-1的点。找到9 和12,到数组10的位置,权值序列变为:
1 2 3 4 5 6 3 6 9 12 21
parent 6 6 7 8 8 9 7 9 10 10 -1
结束
所以你说的j < n + i,由于每次选取两个权值的点权值和做为新的节点放在数组后面,当然下一次循环的时候要多一次循环。
X1 和X2要记录下选择两个权值,将其父节点的位置设置为新的权值点位置。
1. 根据给定的n个权值{w1,w2,…wn}构成n棵二叉树的集合F={T1,T2,..,Tn},其中每棵二叉树Ti中只有一个带权wi的根结点,左右子树均空。
2. 在F中选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
3. 在F中删除这两棵树,并将新的二叉树加入F中。
4. 重复前两步(2和3),直到F中只含有一棵树为止。该树即为哈夫曼树
帮你贴过来了,百度百科
这东西实际用法是可以减少树的访问次数,因为他把频率高的点放在比较靠近根节点的地方,频率低的在下面,这样访问速度快。举个例子,比如四个点,他们的使用频率分别是1,2,3,4,然后构成的树就是
4
0 3
0 2
0 1
补:打不出树形结构...
/*-------------------------------------------------------------------------
* Name: 哈夫曼编码源代码。
* Date: 2011.04.16
* Author: Jeffrey Hill+Jezze(解码部分)
* 在 Win-TC 下测试通过
* 实现过程:着先通过 HuffmanTree() 函数构造哈夫曼树,然后在主函数 main()中
* 自底向上开始(也就是从数组序号为零的结点开始)向上层层判断,若在
* 父结点左侧,则置码为 0,若在右侧,则置码为 1。最后输出生成的编码。
*------------------------------------------------------------------------*/
#include <stdio.h>
#include<stdlib.h>
#define MAXBIT 100
#define MAXVALUE 10000
#define MAXLEAF 30
#define MAXNODE MAXLEAF*2 -1
typedef struct
{
int bit[MAXBIT];
int start;
} HCodeType; /* 编码结构体 */
typedef struct
{
int weight;
int parent;
int lchild;
int rchild;
int value;
} HNodeType; /* 结点结构体 */
/* 构造一颗哈夫曼树 */
void HuffmanTree (HNodeType HuffNode[MAXNODE], int n)
{
/* i、j: 循环变量,m1、m2:构造哈夫曼树不同过程中两个最小权值结点的权值,
x1、x2:构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。*/
int i, j, m1, m2, x1, x2;
/* 初始化存放哈夫曼树数组 HuffNode[] 中的结点 */
for (i=0; i<2*n-1; i++)
{
HuffNode[i].weight = 0;//权值
HuffNode[i].parent =-1;
HuffNode[i].lchild =-1;
HuffNode[i].rchild =-1;
HuffNode[i].value=i; //实际值,可根据情况替换为字母
} /* end for */
/* 输入 n 个叶子结点的权值 */
for (i=0; i<n; i++)
{
printf ("Please input weight of leaf node %d:
", i);
scanf ("%d", &HuffNode[i].weight);
} /* end for */
/* 循环构造 Huffman 树 */
for (i=0; i<n-1; i++)
{
m1=m2=MAXVALUE; /* m1、m2中存放两个无父结点且结点权值最小的两个结点 */
x1=x2=0;
/* 找出所有结点中权值最小、无父结点的两个结点,并合并之为一颗二叉树 */
for (j=0; j<n+i; j++)
{
if (HuffNode[j].weight < m1 && HuffNode[j].parent==-1)
{
m2=m1;
x2=x1;
m1=HuffNode[j].weight;
x1=j;
}
else if (HuffNode[j].weight < m2 && HuffNode[j].parent==-1)
{
m2=HuffNode[j].weight;
x2=j;
}
} /* end for */
/* 设置找到的两个子结点 x1、x2 的父结点信息 */
HuffNode[x1].parent = n+i;
HuffNode[x2].parent = n+i;
HuffNode[n+i].weight = HuffNode[x1].weight + HuffNode[x2].weight;
HuffNode[n+i].lchild = x1;
HuffNode[n+i].rchild = x2;
printf ("x1.weight and x2.weight in round %d: %d, %d
", i+1, HuffNode[x1].weight, HuffNode[x2].weight); /* 用于测试 */
printf ("
");
} /* end for */
/* for(i=0;i<n+2;i++)
{
printf(" Parents:%d,lchild:%d,rchild:%d,value:%d,weight:%d
",HuffNode[i].parent,HuffNode[i].lchild,HuffNode[i].rchild,HuffNode[i].value,HuffNode[i].weight);
}*///测试
} /* end HuffmanTree */
//解码
void decodeing(char string[],HNodeType Buf[],int Num)
{
int i,tmp=0,code[1024];
int m=2*Num-1;
char *nump;
char num[1024];
for(i=0;i<strlen(string);i++)
{
if(string[i]=='0')
num[i]=0;
else
num[i]=1;
}
i=0;
nump=&num[0];
while(nump<(&num[strlen(string)]))
{tmp=m-1;
while((Buf[tmp].lchild!=-1)&&(Buf[tmp].rchild!=-1))
{
if(*nump==0)
{
tmp=Buf[tmp].lchild ;
}
else tmp=Buf[tmp].rchild;
nump++;
}
printf("%d",Buf[tmp].value);
}
}
int main(void)
{
HNodeType HuffNode[MAXNODE]; /* 定义一个结点结构体数组 */
HCodeType HuffCode[MAXLEAF], cd; /* 定义一个编码结构体数组, 同时定义一个临时变量来存放求解编码时的信息 */
int i, j, c, p, n;
char pp[100];
printf ("Please input n:
");
scanf ("%d", &n);
HuffmanTree (HuffNode, n);
for (i=0; i < n; i++)
{
cd.start = n-1;
c = i;
p = HuffNode[c].parent;
while (p != -1) /* 父结点存在 */
{
if (HuffNode[p].lchild == c)
cd.bit[cd.start] = 0;
else
cd.bit[cd.start] = 1;
cd.start--; /* 求编码的低一位 */
c=p;
p=HuffNode[c].parent; /* 设置下一循环条件 */
} /* end while */
/* 保存求出的每个叶结点的哈夫曼编码和编码的起始位 */
for (j=cd.start+1; j<n; j++)
{ HuffCode[i].bit[j] = cd.bit[j];}
HuffCode[i].start = cd.start;
} /* end for */
/* 输出已保存好的所有存在编码的哈夫曼编码 */
for (i=0; i<n; i++)
{
printf ("%d 's Huffman code is: ", i);
for (j=HuffCode[i].start+1; j < n; j++)
{
printf ("%d", HuffCode[i].bit[j]);
}
printf(" start:%d",HuffCode[i].start);
printf ("
");
}
/* for(i=0;i<n;i++){
for(j=0;j<n;j++)
{
printf ("%d", HuffCode[i].bit[j]);
}
printf("
");
}*/
printf("Decoding?Please Enter code:
");
scanf("%s",&pp);
decodeing(pp,HuffNode,n);
getch();
return 0;
}
http://www.cnblogs.com/Jezze/archive/2011/12/23/2299884.html
设计程序以实现构造哈夫曼树的哈夫曼算法(C++),要求如下:
\/* ---初始化完毕!对应算法步骤1---*\/ for(i=n+1;i<=m;i++) \/*创建非叶子结点,建哈夫曼树*\/ { \/*在(*ht)[1]~(*ht)[i-1]的范围内选择两个parent为0且weight最小的结点,其序号分别赋值给s1、s2返回*\/ select(ht,i-1,&s1,&s2);(*ht)[s1].parent=i;(*ht)[s2]....
树- 哈夫曼树及其应用 - 哈夫曼编码 (二)
( )字符集编码的存储结构及其算法描述 typedef struct { char ch; \/\/存储字符 char bits[n+ ]; \/\/存放编码位串 }CodeNode;typedef CodeNode HuffmanCode[n];void CharSetHuffmanEncoding(HuffmanTree T HuffmanCode H){\/\/根据哈夫曼树T求哈夫曼编码表H int c p i;\/\/c和p分别指示T中孩子和...
用huffman算法求带权为2,3,5,7,8的最优2元树,要求画出中间过程?_百度...
7\/8应该一起作为同一父的叶这样才是最优,权为55 把最小的两个数2、3放在最下面作为左右叶子节点,得出他们的父节点权值5,然后它和剩余里最小的数5做成左右兄弟节点,得出父节点10,以此类推啊,10和7得出17,17和8,得到跟节点25完成。例如:先将所有的权值选出最小的两个值,为1,4,这两...
最优二叉树算法编码中的应用
其中叶节点的编码由从根节点到叶子节点的路径决定。编码算法分为两部分:构建哈夫曼树,然后从叶节点开始回溯获取编码,存储在HuffCode数组中。具体实现中,如需了解生成哈夫曼编码的详细步骤和代码,可以参考上述伪代码片段,它展示了如何初始化数据结构,构建哈夫曼树,并计算和存储每个字符的哈夫曼编码。
哈夫曼编码的算法是怎样的?
Faller等人提出了动态哈夫曼编码方法,它对数据编码的依据是动态变化的哈夫曼树,也就是说,对第t+1个字符编码是根据原始数据中前t个字符得到的哈夫曼树来进行的。压缩和解压子程序具有相同的初始化树,每处理完一个字符,压缩和解压方使用相同的算法修改哈夫曼树,因而该方法不需要为解压而保存树的有...
...3,5,7,9,11),要求根据给定的权值集合构造一棵哈夫曼树
2.设给定一个权值集合W=(3,5,7,9,11),要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度WPL。 4.设一组初始记录关键字集合为(25,10,8,27,32,68),散列表的长度为8,散列函数H(k)=k mod 7,要求分别用线性探测和链地址法作为解... 展开 沫...
最小生成树和哈夫曼树有什么区别?
,必然可以去掉某些边,使得最终剩下n-1条边,并且n个结点仍然是连通的,这n个结点和n-1条边组成了原图的一个生成树,而最小生成树就是所有可能的生成树中n-1条边的权值总和最小的那一个(或多个).最短路径常用算法有:floyd,dijkstra,SPFA,A*等 最小生成树常用算法有:prim,kruskal ...
怎样证明:一棵有n个叶子的哈夫曼树共有2n-1 个结点?
以后每次由1叶子与新结点产生新结点,故n个叶子共有2n-1个结点。2.剩下的叶子中又有2个叶子(比第1次产生的新结点权小)结合产生新结点,其它类似,那么必然会由2个都是新结点再产生新结点,所以实际上数量与第1种一样,共有2n-1个。具体证明用一个构造哈夫曼树的算法。
哈夫曼编码算法是什么?
哈夫曼编码是一种将字符编码为可变长度二进制数的压缩算法,由David A. Huffman在1952年提出。哈夫曼编码是一种可变长度编码,它能够将字符集中出现频率较高的字符用较短的编码表示,从而实现对数据的压缩。相对于固定长度编码(如 ASCII 编码),哈夫曼编码能够更好地适应数据的特点,从而实现更高效的...
最优二叉树
( )哈夫曼算法的求精 void CreateHuffmanTree(HuffmanTree T) {\/\/构造哈夫曼树 T[m ]为其根结点 int i p p InitHuffmanTree(T) \/\/将T初始化 InputWeight(T) \/\/输入叶子权值至T[ ..n ]的weight域 for(i=n i<m i++){\/\/共进行n 次合并 新结点依次存于T[i]...
人肤复方:[答案] 哈夫曼树是一种树形结构,用哈夫曼树的方法解编程题的算法就叫做哈夫曼算法.最简哈夫曼树是由德国数学家冯.哈夫曼 发现的,此树的特点就是引出的路程最短. 概念理1.路径 从树中一个节点到另一个节点之间的分支构成这两...
隆昌县13585652625: 哈夫曼树怎样构造编码? - ?
人肤复方: 先编造哈夫曼树,哈夫曼树构造规则: 假设有n个权值,则构造出的哈夫曼树有n个叶子结点. n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为: (1) 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点); (2) ...
隆昌县13585652625: 怎样构造合适的哈夫曼树? - ?
人肤复方: 来自百度百科:哈夫曼树构造方法: 假设有n个权值,则构造出的哈夫曼树有n个叶子结点. n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为: (1) 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点); (2) 在森...
隆昌县13585652625: 数据结构哈夫曼树的算法 - ?
人肤复方: 每次取最小的2个合并后的值继续加入集合进行比较,直到集合里只有一个数为止,这样就可以达到权值最小的路径越长,权值越大的路径越短,即可以找到最小权值路径
隆昌县13585652625: 请描述哈夫曼算法,并用图描述构造哈夫曼树的过程. - ?
人肤复方: 1. 根据给定的n个权值{w1,w2,…wn}构成n棵二叉树的集合F={T1,T2,..,Tn},其中每棵二叉树Ti中只有一个带权wi的根结点,左右子树均空. 2. 在F中选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值...
隆昌县13585652625: 怎样构造哈夫曼树及其带权路径的求法 - ?
人肤复方: 其中每颗二叉树TI中只有一个带权WI的根节点,其左右子树为空.(2)在F中选取两颗根节点的权值最小的树作为左右子树构造一颗新的二叉树.parent=i;HT[i].lchild=s2;HT[i].rchild=s1;HT[i].weight=HT[s1].weight+HT[s2].weight.这棵树就是哈弗曼...
隆昌县13585652625: 哈夫曼树的构造,关键字如图 - ?
人肤复方: 哈夫曼树构造规则:假设有n个权值,则构造出的哈夫曼树有n个叶子结点. n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为:(1) 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点);(2) 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;(3)从森林中删除选取的两棵树,并将新树加入森林;(4)重复(2)、(3)步,直到森林中只剩一棵树为止 根据上述步骤得到的哈夫曼数是 (100) / \ (43) 57 / \ / \ (20) 23 (27) 30 / \ / \9 (11) 11 16 / \ 4 7
隆昌县13585652625: 构造哈夫曼树 - ?
人肤复方: 第一步排序 2 3 6 7 10 19 21 32 构图如下 谢谢提醒 我粗心了…… 字符版 复制到记事本里看********o********** *******/*\********* *****o*****o******* ****/*\***/*\****** ***19*21**o**32**** *********/*\******* ********o***o****** *******/*\*/*\***** *******o*6*7*10**** ******/*\********** ******2*3**********
隆昌县13585652625: 哈夫曼树的建立?
人肤复方: 在一般的数据结构的书中,树的那章后面,著者一般都会介绍一下哈夫曼(HUFFMAN)树和哈夫曼编码.哈夫曼编码是哈夫曼树的一个应用.哈夫曼编码应用广泛,如JPEG中就应用了哈夫曼编码. 首先介绍什么是哈夫曼树.哈夫曼树又称最...
隆昌县13585652625: 哈夫曼树算法?
人肤复方: 题目的阐述:以N进制编码方式对一个英文字串中的字符进行编码,每个不同的字符其编码不同.使得由新的编码替代原串后总码长最小,且输入0,1,2,...,N-1构成的数字串后,依照该编码方式可以正确的对译出唯一的英文原串.如: N=3 英文原...