1.算法说明
就是建造哈夫曼树树,从而使得构造出的树带权路径长度最小
2.步骤
输入叶子结点个数n;
创建长度为2*n-1的数组并初始化;
while(i<n) 循环输入n个叶子结点的权值;
while(n-1次循环建立树){
在parent==-1的元素中查找权最小的两个结点;
合并两个叶子结点,并加入新结点到数组;
}
3.代码
//构造haffman树
#include <iostream>
using namespace std;
const int MAX = 10000;
struct Node{
int weight; //权值
int parent; //双亲
int lchild;
int rchild;
};
//创建一个haffman树
void createHaffman(Node* &a, int n){
int m1,m2, x1, x2;//m1,m2是最小的两个值,x1,x2是他们的位置
//n个结点,只需要n-1次就可以构造好
for(int i=0; i<n-1; i++){
m1 = m2 = MAX;
x1 = x2 = 0;
//查找最小值,在查找到最小的两个值后,构造新的节点,并加入到a中(数组的n+i个节点之后),长度加1,故而查找过程中长度不断增加n+i
for(int j=0; j<n+i; j++){
//首先必须满足,还没有双亲的孤立节点,查找m1,m2都是最小
if(a[j].parent == -1 && a[j].weight < m1){
m1 = a[j].weight;
x1 = j;
}else if(a[j].parent == -1 && a[j].weight < m2){
m2 = a[j].weight;
x2 = j;
}
}
//新的节点存入n+i,并设置x1, x2的双亲
a[x1].parent = n+i;
a[x2].parent = n+i;
a[n+i].weight = a[x1].weight + a[x2].weight;
a[n+i].parent = -1;
a[n+i].lchild = x1;
a[n+i].rchild = x2;
}
}
//测试得到最小和次小的值
void test(){
int a[] = {3,4,7,0,79,9,12,1,4};
int m = MAX,k = MAX;
for(int i=0; i<9; i++){
if(a[i]<m){
m = a[i];
}else if(a[i]<k){
k = a[i];
}
}
cout<<m<<" "<<k<<endl;
}
int main(){
int n;
cout<<"输入叶子节点个数:";
cin>>n;
Node* a = new Node[2*n - 1];
for(int i=0; i<2*n-1; i++){//初始化
a[i].weight = 0;
a[i].parent = -1;
a[i].lchild = -1;
a[i].rchild = -1;
}
cout<<"输入前n个叶子结点的权值"<<endl;
for(int i=0; i<n; i++){
cin>>a[i].weight;
}
cout<<"输出构造好的haffman树"<<endl;
createHaffman(a, n);
for(int i=0; i<2*n-1; i++){
cout<<"["<<a[i].weight<<","<<a[i].parent<<","<<a[i].lchild<<","<<a[i].rchild<<"]"<<endl;
}
delete[] a;
return 0;
}
分享到:
相关推荐
构造哈夫曼树,并生成编码 构造哈夫曼树,并生成编码
讲解构造哈夫曼树的过程,超详细。 对于不理解哈夫曼树的过程构造的新人来讲,十分有用!
给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。
哈夫曼编码实现哈夫曼编码,构造哈夫曼树C语言.zip实现哈夫曼编码,构造哈夫曼树C语言.zip实现哈夫曼编码,构造哈夫曼树C语言.zip实现哈夫曼编码,构造哈夫曼树C语言.zip实现哈夫曼编码,构造哈夫曼树C语言.zip
②在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树,且置其根结点的权值为其左右子树权值之和; ③在F中删除这两棵树,同时将新得到的二叉树加入F中; ④重复②、③直到F只含一棵树为止。
实现构造哈夫曼树的哈夫曼算法。 求解出所构造的哈夫曼 使用树的带权路径长度。
哈夫曼树是最优二叉树的另一种说法。本程序测试已通过。而且还有范例。供广大学子学习非常棒哦。
构造哈夫曼树的算法模拟。数据结构有个重要的算法。共同学习
构造哈夫曼树过程.swf
首先根据给定的n个字符的权值构造哈夫曼树。通过遍历此二叉树完成各字符的哈夫曼编码,另输入一组‘0’、‘1’代码构成的报文将其翻译成对应的字符信息。
从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式(比如树)显示在终端上; 2.利用已经建好的哈夫曼树(如不在内存,则从文件htmTree中读入...
C语言哈夫曼编码,压缩率,构造哈夫曼树
构造哈夫曼树的算法模拟.zip
构造哈夫曼树并求哈夫曼编码的算法实现.doc
数据结构课程中构造哈夫曼树的代码,可用正确
实现哈夫曼算法的前提是要考虑用什么样的存储结构来存储一棵哈夫曼树。在哈夫曼树中,没有度为1的结点,结点总数是n0+n2(其中n0表示二叉树中度为0的结点数,n2表示度为2的结点数),而由二叉树的性质知道n0=n2+1,...
《算法概论》习题5.18构造的哈夫曼树,vsd格式的,利用visio可轻松修改。
数据结构实验实现中序线索化二叉树构造哈夫曼树.doc
构造一棵哈夫曼树,输出对应的哈夫曼编码证