霍夫曼树怎么画,为什么99个结点的哈夫曼树，用二叉链表，它的空指针域会是51个？
为什么99个结点的哈夫曼树，用二叉链表，它的空指针域会是51个？
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
为什么99个结点的哈夫曼树，用二叉链表，它的空指针域会是51个？
二叉链表构造方法是左孩子右兄弟，根节点无兄弟、存在一个空指针域。
50个叶子结点，51个空指针。
因为是二叉链表，就是孩子兄弟表示法，不是一般的二叉树那样画，要转化一下。
在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码。
扩展资料：
树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。
树的路径长度是从树根到每一结点的路径长度之和，记为WPL=（W1*L1+W2*L2+W3*L3+...+Wn*Ln），N个权值Wi（i=1,2,...n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,...n）。
可以证明哈夫曼树的WPL是最小的。
参考资料来源：百度百科-哈夫曼树
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的节点数目。
参考资料来源：
