如何画出哈夫曼树?

~

权值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

---

赤城县13837077637： 假定某系统在通信联络中只可能出现8种字符a,b,c,d,e,f,g,h,各字符出现的概率分别为0.03,0.28.0.06,0.070.14,0.24,0.08,0.10(1)画出哈夫曼树(2)给出每个字... - ？
宫良复方：[答案] a:0110; b:10; c:0111; d:1111; e:110; f:00; g:1110; h:010. WPL=2*0.24+3*0.1+4*0.03+4*0.06+4*0.07+4*0.08+3*0.14+2*0.28=2.72 注:树传不上来,你可以根据编码自己画,谢谢!

赤城县13837077637： 哈夫曼编码树怎么解? - ？
宫良复方： 先编造哈夫曼树,哈夫曼树构造规则: 假设有n个权值,则构造出的哈夫曼树有n个叶子结点. n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为: (1) 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点); (2) ...

赤城县13837077637： 数据结构的哈夫曼图怎么画? - ？
宫良复方： 4,5,6,7,10,12,15,186,7,9,10,12,15,189,10,12,13,15,1812,13,15,18,1915,18,19,2319,232542100 这上面画了也不清楚

赤城县13837077637： 【数据结构】关于画哈夫曼树的问题 - ？
宫良复方： 不一定,但wpl相同你的与书上的方法是不同的吧相同的方法是唯一的只要wpl最小就是最优的吧一般我们总是取当前根节点最小的两棵树合并的2 3 4 7 8 9第一次二三合并为55 4 5 7 8 92 3 第二次4 5 合并为99 7 8 95 4 2 3第三次7 8合并为 15 15 9 9 7 8 5 42 3第四次 9 9合并 18 15 9 9 7 84 52 3第五次 18 15 合并 3118 159 94 52 3吧

赤城县13837077637： 画出以3,4,6,8,12,13,15,18,25,40为结点权值所构造的Huffman树,并对各结点编码 - ？
宫良复方： 这个是我用PPT刚画的.注意点:哈弗曼树没有强制要求某个叶子一定要在左边还是在右边,比如这儿的3和4就可以交换,但是它们的编码的位数(即层次)肯定得是不变的,比如3是00110(从根结点开始走到3的路径上的编码),15是010等等.另外左边是0还是右边是0也是可以变的.我这儿是所有左边的都是0,右边的都是1

赤城县13837077637： 求解赫夫曼树的问题 - ？
宫良复方： ①首先把 n 个叶子结点看做 n 棵树(仅有一个结点的二叉树),把它们看做一个森林.②在森林中把权值最小和次小的两棵树合并成一棵树,该树根结点的权值是两棵子树权值之和.这时森林中还有 n-1 棵树.③重复第②步直到森林中只有一棵为止.很高兴为您解答,祝你学习进步!如果您认可我的回答,请点击下面的【选为满意回答】按钮!有不明白的可以追问!

赤城县13837077637： 给定权值集合:2,5,8,9,15,试画出以权值为叶子结点的哈夫曼树,并计算其带权路径长度及平均长度玩过陈 - ？
宫良复方：[答案] 39 15 24 7 (8) (9) (15) (2) (5) 带权长度:3*2+3*5+2*8+2*9+2*15 平均长度:带权长度/(2+5+8+9+15)

赤城县13837077637： 哈夫曼树和编码 - ？
宫良复方： A出现的概率是1/2,B出现的概率是1/18,C出现的概率是5/18,D出现的概率是3/18. 编码步骤: 1.初始化,根据符号概率的大小按由大到小顺序对符号进行排序. 2.把概率最小的两个符号组成一个节点. 3.重复步骤2,得到得到另外的节点,形成...

赤城县13837077637： 到底什么是哈夫曼树啊,求例子 - ？
宫良复方： 哈夫曼树是给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree).哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近. 例子: 1、将w...

赤城县13837077637： 权值序列为:10,16,20,6,30,24,如何构造出一棵哈夫曼树? - ？
宫良复方：[答案] 哈夫曼树构造规则是先从序列中选取两个最小的权值的点来构造树,新的树根的权值是两个左右子节点的权值和,该新的权值然后放回到权值序列中.迭代这个过程直到只有一棵树为止. 所以该哈夫曼树是: 106 / \ 44 62 / \ / \ 20 24 30 32 / \ 16 16 / \ 6 10