怎样构造哈夫曼树及其带权路径的求法
首先需要构造哈夫曼树，其构造规则是选择两个权值最小的结点，作为左右结点构造成一颗树，这颗树的根权值为左右子树权值大小的和，这个新的权值放入到原有的权值集合中，左右子树权值删除掉
循环上述过程，直到只有一棵树为止。
带权路径长度就是权值结点所在的高度 * 权值大小
带权路径长度之和就是将所有上面的所有求知结果汇总
//你是指哈夫曼树的改造吧
//只要你把树构造出来，其他的操作都简单了，你自己看看，这是一个哈夫曼树的构造
#include
#include
#define MAXVALUE 1000
typedef struct
{
int weight;
int parent,lchild,rchild;
}HTNode,*HuffmanCode;
typedef struct
{
char cd[100];
int start;
}HCode;
void create_HuffmanTree(HTNode HFMTree[],int n)
{
int m1,x1,m2,x2;
int i,j,t;
for(i=0;i<2*n-1;i++)
{
HFMTree[i].weight=0;
HFMTree[i].parent=-1;
HFMTree[i].rchild=-1;
HFMTree[i].lchild=-1;
}
//for(i=0;i<n;i++)
//scanf("%d",&HFMTree[i].weight);
//HFMTree[].weight={5,29,7,8,14,23,3,11};
HFMTree[0].weight=5;
HFMTree[1].weight=29;
HFMTree[2].weight=7;
HFMTree[3].weight=8;
HFMTree[4].weight=14;
HFMTree[5].weight=23;
HFMTree[6].weight=3;
HFMTree[7].weight=11;
for(i=n;i<2*n-1;i++)
{
x1=x2=MAXVALUE;
m1=m2=0;
for(j=0;j<2*n-1;j++)
{
if(HFMTree[j].parent==-1&&HFMTree[j].weight<x1&&HFMTree[j].weight!=0)
{
x1=HFMTree[j].weight;
m1=j;
}
}
printf("x1= %d
",x1);
HFMTree[m1].parent=i;
for(j=0;j<2*n-1;j++)
{
if(HFMTree[j].parent==-1&&HFMTree[j].weight<x2&&HFMTree[j].weight!=0)
{
x2=HFMTree[j].weight;
m2=j;
}
}
printf("x2= %d
",x2);
HFMTree[m2].parent=i;
if(m1>n&&m2<n)
{
t=m1;
m1=m2;
m2=t;
}
HFMTree[i].lchild=m1;
HFMTree[i].rchild=m2;
HFMTree[i].weight=x1+x2;
}
}
void play(HTNode HFMTree[],int n)//
{
int i;
for(i=0;i<2*n-1;i++)
{
printf("%5d %5d %5d %5d
",HFMTree[i].weight,HFMTree[i].parent,HFMTree[i].lchild,HFMTree[i].rchild);
}
}
int main()
{
int n=8;
HTNode T[100];//={5,29,7,8,14,23,3,11}
//scanf("%d",&n);
create_HuffmanTree(T,n);
play(T,n);
return 0;
}
/*打出来是一个数组，分别是每一个元素的权值、父结点、左孩子、右孩子*/
(2)在F中选取两颗根节点的权值最小的树作为左右子树构造一颗新的二叉树，且置新的二叉树的根节点的权值为左右子树上根节点的权值之和。
（3)在F中删除这两颗树，同时将新得到的二叉树加入F中。
（4）重复（2）（3），直到F只含一棵树为止。这棵树就是哈弗曼树。
如果有N个叶子节点，则哈弗曼树有M=2*N-1个节点。
核心代码
for(i=n+1;i<=m;++i)
{
Choose(i-1,s1,s2);//求出两个有最小权值的节点
HT[s1].parent=i;HT[s2].parent=i;
HT[i].lchild=s2;HT[i].rchild=s1;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
“哈夫曼树”的构造是什么?
第一步：排序 2 4 5 9 第二步：挑出2个最小的 2 4 为叶子构造出 6 2 4 第三步：判断 6 不大于 5或9（剩余叶子中最小的2个）=》 同方向生长，得出：11 6 5 2 4 第四步：继续生长 20 11 9 6 5 2 4 权值为 2*3+4*3+5*2+9*1=37 也可以20+11+...
哈夫曼树的构建过程
哈夫曼树的构造：假设给定的权值如下：3,5,7,8,10,15；首先取集合中最小的两个数：3+5=8，再删除集合中3和5的值，把8放入原集合,原集合变成:7,8,8,10,15；8 \/ \\ 3 5 再从7,8,8,10,15中再取2个最小的数构成一个树 15 \/ \\ 8 7 \/ \\ 3 5 再从8,10,15,15中...
树- 哈夫曼树及其应用 - 哈夫曼编码 (二)
根据最优二叉树构造哈夫曼编码 利用哈夫曼树很容易求出给定字符集及其概率(或频度)分布的最优前缀码 哈夫曼编码正是一种应用广泛且非常有效的数据压缩 技术 该技术一般可将数据文件压缩掉 %至 % 其压缩效率取决于被压缩文件的特征 具体做法 ( )用字符c i 作为叶子 p i 或f i 做为叶子c i 的...
...3, 6, 7, 11, 12, 16},构造相应的哈夫曼树并计算带权路径长度_百度...
哈夫曼树构造方法 假设有n个权值，则构造出的哈夫曼树有n个叶子结点。n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：(1)将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；(2)在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根...
“哈夫曼树”的建立方法是什么?
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 k1、k2、…、kn，则哈夫曼树的构造规则为：(1) 将k1、k2、…，kn看成是有n 棵树的森林(每棵树仅有一个结点)；(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其...
到底什么是哈夫曼树啊,求例子
哈夫曼树是给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。例子：1、将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；2、...
哈夫曼树的构造是什么?
哈夫曼树构造：结构化的Huffman算法生成的Huffman树子树都是有序的，所以一般生成Huffman树时都为节点排序，即使这样结果也不唯一。哈夫曼静态编码：它对需要编码的数据进行两遍扫描：第一遍统计原数据中各字符出现的频率，利用得到的频率值创建哈夫曼树，并必须把树的信息保存起来，即把字符0-255(2^8=...
哈夫曼树及哈夫曼编码的C程序实现(数据结构题)
\/\/ w存放n个字符的权值(均>0)，构造哈夫曼树HT，\/\/ 并求出n个字符的哈夫曼编码HC int i, j;char *cd;int p;int cdlen;if (n<=1) return;m = 2 * n - 1;HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); \/\/ 0号单元未用 for (i=1; i<=n; i++) { \/\/初始化...
哈夫曼树的构造算法
* Date: 2011.04.16 * Author: Jeffrey Hill+Jezze(解码部分) * 在 Win-TC 下测试通过 * 实现过程：着先通过 HuffmanTree() 函数构造哈夫曼树，然后在主函数 main()中 * 自底向上开始(也就是从数组序号为零的结点开始)向上层层判断，若在 * 父结点左侧，则置码为 0,若在右侧,...
构造哈夫曼树?
详情请查看视频回答
严阎全威： 其中每颗二叉树TI中只有一个带权WI的根节点,其左右子树为空.(2)在F中选取两颗根节点的权值最小的树作为左右子树构造一颗新的二叉树.parent=i;HT[i].lchild=s2;HT[i].rchild=s1;HT[i].weight=HT[s1].weight+HT[s2].weight.这棵树就是哈弗曼...
宜宾市13211502506： 数据结构,构造哈夫曼树,求树的带权路径长度用6个权值分别为6、13、18、30、7和16的结点构造一棵哈夫曼(Huffman)树,该树的带权路径长度为答... - ？
严阎全威：[答案] =6*4+7*4+13*3+30*2+16*2+18*2=219吧,根结点的值不对哦
宜宾市13211502506： 设给定一个权值集合W=(9,4,10,6,3,10,8,15,12,16,2,11),构造一个哈夫曼树并计算哈夫曼树的带权路径长度WPL - ？
严阎全威：[答案] 哈夫曼树如下: 106 / \ 63 43 / \ / \ 29 34 20 23 / \ / \ / \ / \ 14 15 16 18 10 10 11 12 / \ / \ 6 8 9 9 / \ 4 5 / \ 2 3 WPL=361
宜宾市13211502506： 怎样构造合适的哈夫曼树? - ？
严阎全威： 来自百度百科:哈夫曼树构造方法: 假设有n个权值,则构造出的哈夫曼树有n个叶子结点. n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为: (1) 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点); (2) 在森...
宜宾市13211502506： 用5个权值{3,2,4,5,1}构造的哈夫曼树的带权路径长度 用5个权值{3,2,4,5,1}构造的哈夫曼树的带权路径长度 - ？
严阎全威：[答案] 先构造哈夫曼树,其构造规则如下:假设有n个权值,则构造出的哈夫曼树有n个叶子结点. n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为:(1) 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点);(2) 在...
宜宾市13211502506： 由分别带权为9,2,5,7的4个叶节点构造一棵哈夫曼树,该树的带权路径长度为()?何为“权”?这题如何算?树的构造我会.“带权路径长度”这个指什么? - ？
严阎全威：[答案] 简单的认为就是叶子节点的值.之所以叫权是因为它将用来构造树. 构造方法太长,你还是参考baidu知道吧.哈夫曼树 树: 25 14 9 7 7 5 2 带权路径长度=5*3+2*3+7*2+9*1=44
宜宾市13211502506： 给定一组权值3.3.7.7.11,13.17试构造一棵哈夫曼树并计算出带权路径长度 - ？
严阎全威：[答案] 哈夫曼树是: 61 / \ 26 35 / \ / \ 13 13 17 18 / \ / \ 6 7 7 11 / \3 3树带权路径长度 = 3 * 4 + 3 * 4 + 7*3 + 13 * 2 ...
宜宾市13211502506： 数据结构画Huffman树和计算带权路径长度 - ？
严阎全威： 首先选择最小的4,5 得到9 则在{6,7,9,10,12,18}中选出最小的6,7得到13,继续在{9,10,12,13,18}选出最小的两个9,10,最后可以得到的树就是下面的树 62 25 37 12 13 18 19 6 7 9 10 4 5 两个叶子节点加起来就是根节点 这里不能画图 不是很清楚,但是应该也能明白, WPL=(4+5)*4+(6+7+10)*3+(12+18)*2=165 需要代码的话给邮箱,如果问题已解决,请采纳
宜宾市13211502506： 给定一组权值W=(14.15.7.3.20.4)请构造出相应的哈夫曼树,并计算其带权的路径长度WPL? - ？
严阎全威：[答案] 带权的路径长度WPL=3*4+4*4+7*3+14*2+15*2+20*2
宜宾市13211502506： 数据结构中哈夫曼树的问题用5个权值{3,2,4,5,1}构造的哈夫曼树的带权路径长度是? - ？
严阎全威：[答案] 哈夫曼树为: 15 / \ 6 9 / \ / \ 3 【3】【4】 【5】 / \ 【1】 【2】 树的带权路径长度为树中所有叶子结点的带权路径长度之和,而结点的带权路径长度为结点到根节点之间的路径长度与该节点上权的乘积. WPL=3*(1+2)+2*3+2*(4+5)=33
