本文目录
设权值集合w=，以w为基础，建立一棵霍夫曼树，并求其带权路径长度wpl的值
首先需要构造哈夫曼树，其构造规则是选择两个权值最小的结点，作为左右结点构造成一颗树，这颗树的根权值为左右子树权值大小的和，这个新的权值放入到原有的权值集合中，左右子树权值删除掉 循环上述过程，直到只有一棵树为止。
追加200分！！数据结构的简单问题
(1) 0.90 0.37 0.53 0.18 0.19b 0.21g 0.32e0.07a 0.11 0.05 0.06d 0.02c 0.03f wpl=(c+f)*5+d*4+a*3+(b+f+e)*2=2.14(2)01-》118-》142-》756-》273-》55-》164-》175-》836-》^7-》208-》219-》6110-》^11-》2412-》^(3)1. 751 222 57 129 97 86 42 94 076 48 e 751 42 94 076 97 48 129 222 086 57 f(对头)751 222 42 94 086 076 57 97 48 129 (上面是对个位)同理对十位排序:129 48 57 97 222 42 751 076 86 94222 129 42 48 751 076 86 94 97 百位:097094086076057048042 129 222 751(百位:)42 48 57 76 86 94 97 129 222 7512.快速排序 (以第一个数为主)751 222 57 129 97 86 42 94 076 48 第一次:(751找正确位置)48 222 57 129 97 86 42 94 076 751第二次:(222找正确位置)48 57 129 97 86 42 94 76 222 751第三次:(48)42 48 129 97 86 57 94 76 222 751第五次:12942 48 76 57 86 94 97 129 222 751第六次:7642 48 57 76 86 94 97 129 222 7513.(按照1.2.3.....写成二叉树) 751 222 57 129 97 80 4294 76 48 排一下就ok: 751 222 80 129 97 57 42 94 76 48
一组权值集合W={6,5,4,32}构建的哈夫曼树的WPL是多少
哈夫曼编码步骤：
一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。（为方便在计算机上实现算 法，一般还要求以Ti的权值Wi的升序排列。）二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。三、从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。四、重复二和三两步，直到集合F中只有一棵二叉树为止。
树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL
WPL=∑Wi*Li (i=1到n)
WPL=(4+5)*3+6*2+32*1
=71
