本文目录
权值序列为:10,16,20,6,30,24,如何构造出一棵哈夫曼树
哈夫曼树构造规则是先从序列中选取两个最小的权值的点来构造树，新的树根的权值是两个左右子节点的权值和，该新的权值然后放回到权值序列中。迭代这个过程直到只有一棵树为止。所以该哈夫曼树是： 106 / \ 44 62 / \ / \20 24 30 32 / \ 16 16 / \ 6 10
2，3，6，7，14，19，22怎么画成哈夫曼树求解
哈夫曼树为：
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的节点数目。
“哈夫曼树”的建立方法是什么
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 k1、k2、?、kn，则哈夫曼树的构造规则为：
(1) 将k1、k2、?，kn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
哈夫曼静态编码：它对需要编码的数据进行两遍扫描：第一遍统计原数据中各字符出现的频率，利用得到的频率值创建哈夫曼树，并必须把树的信息保存起来，即把字符0-255(2^8=256)的频率值以2-4BYTES的长度顺序存储起来，（用4Bytes的长度存储频率值，频率值的表示范围为0--2^32-1，这已足够表示大文件中字符出现的频率了）以便解压时创建同样的哈夫曼树进行解压；第二遍则根据第一遍扫描得到的哈夫曼树进行编码，并把编码后得到的码字存储起来。
哈夫曼动态编码：动态哈夫曼编码使用一棵动态变化的哈夫曼树，对第t+1个字符的编码是根据原始数据中前t个字符得到的哈夫曼树来进行的，编码和解码使用相同的初始哈夫曼树，每处理完一个字符，编码和解码使用相同的方法修改哈夫曼树，所以没有必要为解码而保存哈夫曼树的信息。编码和解码一个字符所需的时间与该字符的编码长度成正比，所以动态哈夫曼编码可实时进行。
哈夫曼树的特点
哈夫曼树的特点
没有度为1的结点；
哈夫曼树的任意非叶节点的左右子树交换后仍是哈夫曼树；
n个叶子结点的哈夫曼树共有2n-1个结点；
对同一组权值{w1 ,w2 , …… , wn}，存在不同构的两棵哈夫曼树
1、什么是哈夫曼树：
哈夫曼树也称最优二叉树，含有n个带权叶子结点带权路径长度最小的二叉树
2、哈夫曼树的构造思路
将n个结点作为n棵仅含有一个根结点的二叉树，构成森林F
生成一个新结点，并从F中找出根结点权值最小的两棵树作为它的左右子树（没有规定左右两边的顺序），且新结点的权值为两棵子树根结点的权值之和
从F中删除这两个树，并将新生成的树加入到F中
重复2,3步骤，直到F中只有一棵树为止
