画哈夫曼树的规律,16 28 12 6 14 24怎么画成哈夫曼树求解？

画哈夫曼树的规律,16 28 12 6 14 24怎么画成哈夫曼树求解？详细介绍

本文目录一览： 哈夫曼树的构造规则

哈夫曼树的构造规则是若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。
哈夫曼树的数据为使不等长编码为前缀编码(即要求一个字符的编码不能是另一个字符编码的前缀)，可用字符集中的每个字符作为叶子结点生成一棵编码二叉树，为了获得传送报文的最短长度，可将每个字符的出现频率作为字符结点的权值赋予该结点上，显然字使用频率越小权值越小，权值越小叶子就越靠下。
于是频率码长，频率高编码短，这样就保证了此树的最小带权路径长度效果上就是传送报文的最短长度。
因此，求传送报文的最短长度问题转化为求由字符集中的所有字符作为叶子结点，由字符出现频率作为其权值所产生的哈夫曼树的问题。利用哈夫曼树来设计二进制的前缀编码，既满足前缀编码的条件，又保证报文编码总长最短。

2，3，6，7，14，19，22怎么画成哈夫曼树求解？

画成哈夫曼树：
假设有n个值，则构造出的哈夫曼树有n个叶子结点。 n个值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：
(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的值最小的树合并，作为一棵新树的左、右子树，且新树的根结点值为其左、右子树根结点值之和；
扩展资料
哈夫曼树也可以是k叉的，只是在构造k叉哈夫曼树时需要先进行一些调整。构造哈夫曼树的思想是每次选k个权重最小的元素来合成一个新的元素，该元素权重为k个元素权重之和。但是当k大于2时，按照这个步骤做下去可能到最后剩下的元素少于k个。
解决这个问题的办法是假设已经有了一棵哈夫曼树(且为一棵满k叉树)，则可以计算出其叶节点数目为(k-1)nk+1,式子中的nk表示子节点数目为k的节点数目。
如图。
如有帮助，望采纳
哈夫曼树为：
100
/ \
60 40
/ \ / \
28 32 19 21
/ \
11 17
/ \ / \
5 6 7 10
/ \
2 3
编码左子树/为0 右子树\为1
a:0010,b10 c 00000，其他自己看一下
哈夫曼树为：
100
/ \
60 40
/ \ / \
28 32 19 21
/ \
11 17
/ \ / \
5 6 7 10
/ \
2 3
编码左子树/为0 右子树\为1
假设有n个值，则构造出的哈夫曼树有n个叶子结点。 n个值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：
(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的值最小的树合并，作为一棵新树的左、右子树，且新树的根结点值为其左、右子树根结点值之和；
扩展资料：
哈夫曼树也可以是k叉的，只是在构造k叉哈夫曼树时需要先进行一些调整。构造哈夫曼树的思想是每次选k个权重最小的元素来合成一个新的元素，该元素权重为k个元素权重之和。但是当k大于2时，按照这个步骤做下去可能到最后剩下的元素少于k个。
解决这个问题的办法是假设已经有了一棵哈夫曼树(且为一棵满k叉树)，则可以计算出其叶节点数目为(k-1)nk+1,式子中的nk表示子节点数目为k的节点数目。
参考资料来源：百度百科-哈夫曼树

16 28 12 6 14 24怎么画成哈夫曼树求解？

哈夫曼树是一种带权路径长度最短的树，可以用来压缩数据，其中权值越大的节点离根节点越近。
下面是将16 28 12 6 14 24这些权值画成哈夫曼树的步骤：
将这些权值从小到大排序，得到6 12 14 16 24 28。
把权值最小的两个节点（6和12）合并为一个节点，它们的权值之和作为新节点的权值，得到18。把这个新节点作为一棵树的根节点，它的两个子节点分别是之前合并的两个节点。
把权值次小的节点（14）加入这棵树中，与之前合并的节点合并，得到新的节点权值为32。
重复上述步骤，将16和18合并为34，24和28合并为52。
最后再将32和34合并为66，得到完整的哈夫曼树。
下面是6 12 14 16 24 28这些权值画成哈夫曼树的示意图：
66
/ \
32 34
/ \ / \
14 18 16 24
/ \
6 12

权值w={5，29,7,8,14,23,3,11}，画出哈夫曼树

先最小的两个，5和3 变成权值为8一棵树
再选最小的两个为7 和8，这个8也可以是5和3的那个组成两个8选一个，变成权值15的一棵树
按这个规律
①首先把 n 个叶子结点看做 n 棵树（仅有一个结点的二叉树），把它们看做一个森林。
②在森林中把权值最小和次小的两棵树合并成一棵树，该树根结点的权值是两棵子树权值之和。这时森林中还有 n-1 棵树。
③重复第②步直到森林中只有一棵为止。

字符集{A,B,C,D,E,F} ,各字符使用频率对应为{2,4,5,13,9,18},试画出哈夫曼树

假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：
(1)将w1、w2、…，wn看成是有n棵树的森林(每棵树仅有一个结点)；
(2)在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

权值w={5,29,7,8,14,23,3,11},画出哈夫曼树。

我觉得你的是对的，哈夫曼树是不唯一的，只要得到的带权路径长度是最小的就没问题，答案是100，你的也是100，我个人认为是正确的。如果我说的不对还请帮忙纠正，一起进步
权值w={5,29,7,8,14,23,3,11},画出哈夫曼树.个人认为, 图2的画法有不妥的地方.问题点就是:结点3和结点5组成新结点N8,那么新结点N8应该排在原有结点8的后面,还是前面?个人认为,应该按照图1的做法,将新结点N8排在原有结点8的后面.分析过程如下:八个权值从小到大排序是: 3 5 7 8 11 14 23 29图1 : 哈夫曼树 N100 / \ N42 N58 / \ / \ 23 N19 29 N29 / \ / \ 11 N8 14 N15 / \ / \ 3 5 7 8根结点N100到结点29的路径长度是2,结点29的带权路径长度是29*2根结点N100到结点3的路径长度是4,结点3的带权路径长度是3*4如此类推,哈夫曼树的带权路径长度(WPL)等于29*2 + 23*2 + 14*3 + 11*3 + 8*4 + 7*4 + 5*4 + 3*4 = 271哈夫曼编码:规定哈夫曼树的左分支代表0,右分支代表1.权值29: 10权值23: 00权值14: 110权值11: 010权值8 : 1111权值7 : 1110权值5 : 0111权值3 : 0110图2 : 哈夫曼树 N100 / \ N58 N42 / \ / \ N29 29 N19 23 / \ / \ 14 N15 8 11 / \ 7 N8 / \ 3 5根结点N100到结点29的路径长度是2,结点29的带权路径长度是29*2根结点N100到结点3的路径长度是5,结点3的带权路径长度是3*5如此类推,哈夫曼树的带权路径长度(WPL)等于29*2 +23*2 +14*3 +11*3 +8*3 +7*4 +5*5 +3*5 = 271哈夫曼编码:规定哈夫曼树的左分支代表0,右分支代表1.权值29: 01权值23: 11权值14: 000权值11: 101权值8 : 100权值7 : 0010权值5 : 00111权值3 : 00110从 WPL 的角度看,图1和图2的WPL都是等于271.从 哈夫曼编码 的角度看:图1, 权值29的编码是10, 权值3的编码是0110 图2, 权值29的编码是01, 权值3的编码是00110图2的权值29和权值3的编码长度相差大了一点.相比下,图1的方案更加合适,所以优先选择图1的哈夫曼树.图1和图2出现编码差异大的主要原因是:结点3和结点5组成新结点N8,那么新结点N8应该排在原有结点8的后面,还是前面?图1的做法是将新结点N8排在原有结点8的后面,所以结点7与原有结点8先合并.而图2的做法是新结点将N8排在原有结点8的前面,所以结点7和新结点N8先合并了.个人认为,应该按照图1的做法,将新结点N8排在原有结点8的后面.另外,个人认为,图1的结点11和N8的左右位置互换一下,结点23和N19左右位置互换一下,这样会更加合适,保证从左到右,结点是从小到大,让最后编码的时候,更加统一.以下是详细的构建过程:(1) 从小到大排序 3 5 7 8 11 14 23 29 (这是有序序列)(2) 每次提取最小的两个结点,取结点3和结点5,组成新结点N8,其权值=3+5=8, 取数值较小的结点作为左分支,结点3作为左分支,而结点5就作为右分支.(3) 将新结点N8放入有序序列,保持从小到大排序: 7 8 N8 11 14 23 29 [注意,新结点N8排在原结点8的后面](4) 重复步骤(2),提取最小的两个结点,结点7与结点8组成新结点N15,其权值=7+8=15, 结点7的数值较小,将结点7作为左分支,结点8就作为右分支.(5) 将新结点N15放入有序序列,保持从小到大排序: N8 11 14 N15 23 29(6) 重复步骤(2),提取最小的两个结点,N8与结点11组成新结点N19,其权值=8+11=19, N8的数值较小,作为左分支,结点11就作为右分支.(7) 将新结点N19放入有序序列,保持从小到大排序: 14 N15 N19 23 29(8) 重复步骤(2),提取最小的两个结点,结点14与N15组成新结点N29,其权值=14+15=29, 结点14的数值较小,作为左分支,N15就作为右分支.(9) 将新结点N29放入有序序列,保持从小到大排序: N19 23 29 N29 [注意,新结点N29排在原结点29的后面](10)重复步骤(2),提取最小的两个结点,N19与结点23组成新结点N42,其权值=19+23=42, N19的数值较小,作为左分支,结点23就作为右分支.(11)将新结点N42放入有序序列,保持从小到大排序: 29 N29 N42(12)重复步骤(2),提取最小的两个结点,结点29与N29组成新结点N58,其权值=29+29=58, 结点29与N29的数值相同,将原结点29作为左分支,N29就作为右分支.(13)将新结点N58放入有序序列,保持从小到大排序: N42 N58(14)重复步骤(2),提取剩下的两个结点,N42与N58组成新结点N100,其权值=42+58=100, 数值较小的N42作为左分支,N58就作为右分支. 最后得到"哈夫曼树": N100 / \ N42 N58 / \ / \ N19 23 29 N29 / \ / \ N8 11 14 N15 / \ / \ 3 5 7 8带权路径长度(WPL):根结点N100到结点29的路径长度是2,结点29的带权路径长度是29*2根结点N100到结点23的路径长度是2,结点23的带权路径长度是23*2根结点N100到结点14的路径长度是3,结点14的带权路径长度是14*3根结点N100到结点11的路径长度是3,结点11的带权路径长度是11*3根结点N100到结点8的路径长度是4,结点8的带权路径长度是8*4根结点N100到结点7的路径长度是4,结点7的带权路径长度是7*4根结点N100到结点5的路径长度是4,结点5的带权路径长度是5*4根结点N100到结点3的路径长度是4,结点3的带权路径长度是3*4所以,哈夫曼树的带权路径长度(WPL)等于29*2 + 23*2 + 14*3 + 11*3 + 8*4 + 7*4 + 5*4 + 3*4 = 271哈夫曼编码:规定哈夫曼树的左分支代表0,右分支代表1.从根结点N100到结点29,先经历右分支,再经历左分支,结点29的编码就是10从根结点N100到结点23,先经历左分支,再经历右分支,结点23的编码就是01从根结点N100到结点14,经历两次右分支,再经历左分支,结点14的编码就是110如此类推,得出所有结点的"哈夫曼编码":权值29: 10权值23: 01权值14: 110权值11: 001权值8 : 1111权值7 : 1110权值5 : 0001权值3 : 0000

哈夫曼树频率和不是100

哈夫曼树
给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
树节点间的边相关的数叫做权。
从树中的一个节点到另一个节点之间的分支构成两个点之间的路径，路径上的分支数目称作路径长度。
图中二叉树a中，跟节点到D的路径长度就是4，b中根节点到D的路径长度为2。
树的路径长度就是从树根到每一个节点的路径长度之和。二叉树a的路径长度就为1+1+2+2+3+3+4+4=20。二叉树b的树路径长度就为1+2+3+3+2+1+2+2=16。
如果考虑带权的节点，节点的带权的路径长度就是从该节点到树根之间的路径长度乘该节点的权。
数的带权路径长度就是所有叶子节点的带权路径长度之和。
带权路径长度（WPL）最小的二叉树称作哈夫曼树。
如何构造哈夫曼树
下面我们以【5、8、4、11、9、13】为例来画出哈夫曼树（数字大小代表权重大小，越大的权重越大）
第一步：按从小到大排序。
【5、8、4、11、9、13】→【4、5、8、9、11、13】
第二步：选最小两个数画出一个树，最小数为4和5。
给定的4、5、8、9、11、13为白色， 红色的9为4+5，与给定的白9无关，新序列为：【红9（含子节点4、5）、8、9、11、13】
取两个最小数8和9：
排序：
重复该过程直到最后的结果
给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
哈夫曼树频率和必须是100，假设字符集4个字符A，B，C，D的频率分别为45，10,10，35，合起来是100%，那么，我们可以按照哈夫曼树来规划它们。这就是哈夫曼树的定义，望采纳。

请描述哈夫曼算法，并用图描述构造哈夫曼树的过程。

这个讲的相当清楚。
首先介绍什么是哈夫曼树。哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。
哈夫曼在上世纪五十年代初就提出这种编码时，根据字符出现的概率来构造平均长度最短的编码。它是一种变长的编码。在编码中，若各码字长度严格按照码字所对应符号出现概率的大小的逆序排列，则编码的平均长度是最小的。（注：码字即为符号经哈夫曼编码后得到的编码，其长度是因符号出现的概率而不同，所以说哈夫曼编码是变长的编码。）
然而怎样构造一棵哈夫曼树呢？最具有一般规律的构造方法就是哈夫曼算法。一般的数据结构的书中都可以找到其描述：
一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。（为方便在计算机上实现算法，一般还要求以Ti的权值Wi的升序排列。）
二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。
三、从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。
四、重复二和三两步，直到集合F中只有一棵二叉树为止。
用C语言实现上述算法，可用静态的二叉树或动态的二叉树。若用动态的二叉树可用以下数据结构： struct tree{
float weight; /*权值*/
union{
char leaf; /*叶结点信息字符*/
struct tree *left; /*树的左结点*/
};
struct tree *right; /*树的右结点*/
};
struct forest{ /*F集合，以链表形式表示*/
struct tree *ti; /* F中的树*/
struct forest *next; /* 下一个结点*/
};
例：若字母A，B，Z，C出现的概率为：0.75,0.54,0.28,0.43；则相应的权值为：75，54，28，43。
构造好哈夫曼树后，就可根据哈夫曼树进行编码。例如：上面的字符根据其出现的概率作为权值构造一棵哈夫曼树后，经哈夫曼编码得到的对应的码值。只要使用同一棵哈夫曼树，就可把编码还原成原来那组字符。显然哈夫曼编码是前缀编码，即任一个字符的编码都不是另一个字符的编码的前缀，否则，编码就不能进行翻译。例如：a,b,c,d的编码为：0，10，101，11，对于编码串：1010就可翻译为bb或ca，因为b的编码是c的编码的前缀。刚才进行哈夫曼编码的规则是从根结点到叶结点（包含原信息）的路径，向左孩子前进编码为0，向右孩子前进编码为1，当然你也可以反过来规定。
这种编码方法是静态的哈夫曼编码，它对需要编码的数据进行两遍扫描：第一遍统计原数据中各字符出现的频率，利用得到的频率值创建哈夫曼树，并必须把树的信息保存起来，即把字符0-255(2^8=256)的频率值以2-4BYTES的长度顺序存储起来，（用4Bytes的长度存储频率值，频率值的表示范围为0--2^32-1，这已足够表示大文件中字符出现的频率了）以便解压时创建同样的哈夫曼树进行解压；第二遍则根据第一遍扫描得到的哈夫曼树进行编码，并把编码后得到的码字存储起来。 静态哈夫曼编码方法有一些缺点：一、对于过短的文件进行编码的意义不大，因为光以4BYTES的长度存储哈夫曼树的信息就需1024Bytes的存储空间；二、进行哈夫曼编码，存储编码信息时，若用与通讯网络，就会引起较大的延时；三、对较大的文件进行编码时，频繁的磁盘读写访问会降低数据编码的速度。
因此，后来有人提出了一种动态的哈夫曼编码方法。动态哈夫曼编码使用一棵动态变化的哈夫曼树，对第t+1个字符的编码是根据原始数据中前t个字符得到的哈夫曼树来进行的，编码和解码使用相同的初始哈夫曼树，每处理完一个字符，编码和解码使用相同的方法修改哈夫曼树，所以没有必要为解码而保存哈夫曼树的信息。编码和解码一个字符所需的时间与该字符的编码长度成正比，所以动态哈夫曼编码可实时进行。动态哈夫曼编码比静态哈夫曼编码复杂的多，有兴趣的读者可参考有关数据结构与算法的书籍。
前面提到的JPEG中用到了哈夫曼编码，并不是说JPEG就只用哈夫曼编码就可以了，而是一幅图片经过多个步骤后得到它的一列数值，对这些数值进行哈夫曼编码，以便存储或传输。哈夫曼编码方法比较易懂，大家可以根据它的编码方法，自己编写哈夫曼编码和解码的程序。

哈夫曼树的构造

前序遍历:ABDECFG
中序遍历:DBEAFCG
后序遍历:DEBFGCA
前序遍历:1 2 4 3 5 7 6
中序遍历:2 4 1 5 7 3 6
后序遍历:4 2 7 5 6 3 1
做类似的题目，你可以先由两个遍历画出二叉树。通过形象的二叉树来写出另一个遍历，写的方法如上（递归）。画出二叉树的方法如下：
已知一棵二叉树的前序序列和中序序列，构造该二叉树的过程如下：
1. 根据前序序列的第一个元素建立根结点；
2. 在中序序列中找到该元素，确定根结点的左右子树的中序序列；
3. 在前序序列中确定左右子树的前序序列；
4. 由左子树的前序序列和中序序列建立左子树；
5. 由右子树的前序序列和中序序列建立右子树。
已知一棵二叉树的后序序列和中序序列，构造该二叉树的过程如下：
1. 根据后序序列的最后一个元素建立根结点；
2. 在中序序列中找到该元素，确定根结点的左右子树的中序序列；
3. 在后序序列中确定左右子树的后序序列；
4. 由左子树的后序序列和中序序列建立左子树；
5. 由右子树的后序序列和中序序列建立右子树。
第一步排序
2 3 6 7 10 19 21 32
构图如下 谢谢提醒 我粗心了……
字符版 复制到记事本里看
********o**********
*******/*\*********
*****o*****o*******
****/*\***/*\******
***19*21**o**32****
*********/*\*******
********o***o******
*******/*\*/*\*****
*******o*6*7*10****
******/*\**********
******2*3**********
第一步：排序 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+6=37
例题：6、13、18、30、7、16
排序 6 7 13 16 18 30
13
6 7
26 26大于16或18 =》分支生长
13 13
6 7
26 34
13 13 16 18
6 7
此时最小的2个数为 26 30 得出
56 34
26 30 16 18
13 13
6 7
最后得出 90
56 34
26 30 16 18
13 13
6 7 权值 219
90+56+26+13+34 or 6*4+7*4+13*3+30*2+16*2+18*2