给定一组权值{3,6,9,14,8,5,4,19,25},试设计相应的哈夫曼树,并求其带权路径长

首先，将权值从小到大排序：{3,4,5,6,8,9,14,19,25}。

接着，选取权值最小的两个节点3和4，构建一棵新的二叉树，令3为左孩子，4为右孩子，其权值为3+4=7。

接着，在剩余的节点中，选取权值最小的两个节点5和6，构建一棵新的二叉树，令5为左孩子，6为右孩子，其权值为5+6=11。

重复上述步骤，直到所有的节点都被构建成一棵二叉树。最终得到的哈夫曼树如下所示：

       78
     /    \
   33      45
  /  \    /  \
19  14   25   20
  \  /    \
   8  11   5
      / \
     3   4

带权路径长为：

(3+4)*2 + (5+6)*2 + (8+11)*2 + 14*2 + 19*3 + 20*3 + 25*3 = 221

相关问题

给定一组数列(10,18,16,25,6,9,16)分别代表字符A,B,C,D,E,F,G出现的频率 1. 画出对应的哈夫曼树(要求左孩子权值尽可能小，哈夫曼树的高度尽可能小) 2. 给出个字符的哈夫曼编码

1. 哈夫曼树的构造过程如下：
首先将所有节点按照权值从小到大排序，得到节点顺序为E、F、G、A、C、B、D。
然后选取权值最小的两个节点E和F，构造新节点EF，权值为10+9=19，将E和F分别作为EF的左右子节点。
得到节点顺序为G、A、C、B、D、EF。
再次选取权值最小的两个节点G和A，构造新节点GA，权值为16+16=32，将G和A分别作为GA的左右子节点。
得到节点顺序为GA、C、B、D、EF。
继续选取权值最小的两个节点GA和C，构造新节点GAC，权值为32+16=48，将GA和C分别作为GAC的左右子节点。
得到节点顺序为B、D、EF、GAC。
继续选取权值最小的两个节点B和D，构造新节点BD，权值为6+16=22，将B和D分别作为BD的左右子节点。
得到节点顺序为EF、GAC、BD。
最后选取权值最小的两个节点EF和GAC，构造新节点EFGAC，权值为19+48=67，将EF和GAC分别作为EFGAC的左右子节点，构造出哈夫曼树。
哈夫曼树如下图所示：

                                 EFGAC
                                 /     \
                              EF(19)  GAC(48)
                              /   \    /   \
                             E(10) F(9) GA(32) C(16)
                                            /    \
                                          G(16)  A(16)
                                                  
                            /   \              
                          B(6)  D(16)

2. 根据哈夫曼树，可以得到每个字符的哈夫曼编码如下：
A：01
B：000
C：11
D：001
E：10
F：110
G：111
因此，字符A的哈夫曼编码为01，字符B的哈夫曼编码为000，字符C的哈夫曼编码为11，字符D的哈夫曼编码为001，字符E的哈夫曼编码为10，字符F的哈夫曼编码为110，字符G的哈夫曼编码为111。

设有一组关键字序列为（31,23,17,27,19,11,13,91,61,41)，要求： (1）采用哈希函数： H ( key )= key mod 7。用链地址法解决冲突，试在0~6的散列地址空间对关键字序列构造哈希表。并计算出在等概率情况下查找成功的平均查找长度；(2）以该关键字序列中的各关键字为叶子构造一棵哈夫曼树，并计算出它的带权路径长度 WPL ; (3）按各关键字在该关键字序列中的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。

好的，以下是对应的题解：

1. 哈希表构建

采用哈希函数 $H(key) = key \ mod \ 7$，对于每个关键字，计算出其散列地址并插入哈希表中。若发生冲突，则采用链地址法解决，即在对应散列地址的链表中插入该关键字。

关键字序列为（31,23,17,27,19,11,13,91,61,41），哈希表构建的过程如下：

| 地址 | 关键字 |
| --- | --- |
| 0 | 41 |
| 1 | 31，17 |
| 2 | 23，13 |
| 3 | 27，91 |
| 4 | 19 |
| 5 | 11 |
| 6 | 61 |

在等概率情况下查找成功的平均查找长度为：

$$ASL = \frac{1}{n}\sum_{i=1}^nL_i$$

其中 $n$ 为关键字数，$L_i$ 为查找第 $i$ 个关键字时的查找长度。由于采用链地址法解决冲突，所以每个地址上的关键字出现的概率相等，即 $p_i = \frac{1}{n}$。而查找第 $i$ 个关键字时的查找长度与该关键字所在地址上的链表长度 $k_i$ 有关，即 $L_i = k_i + 1$。因此，可以得到：

$$ASL = \frac{1}{n}\sum_{i=1}^n(k_i + 1) = \frac{1}{n}\sum_{i=0}^6(k_i + 1)$$

其中 $k_i$ 表示地址 $i$ 上链表的长度。

2. 哈夫曼树构建

按照哈夫曼树构建的方法，可以得到如下哈夫曼树：

         289
       /     \
     125      164
    /   \    /   \
  53    72  82   82
 / \   /  \
27 26 30  42

其中，每个叶子节点的权值即为对应的关键字，带权路径长度 WPL 为：

$$WPL = 27 \times 1 + 26 \times 2 + 30 \times 2 + 42 \times 2 + 53 \times 3 + 72 \times 3 + 82 \times 3 + 82 \times 3 = 707$$

3. 二叉排序树构建

按照给定的关键字序列，依次插入一棵初始为空的二叉排序树中，可以得到以下二叉排序树：

          31
         /  \
       23   91
      /  \    \
    17   27   41
         /      \
        19      61
           \
           13

在等概率的情况下查找成功的平均查找长度为：

$$ASL = \frac{1}{n}\sum_{i=1}^nL_i$$

其中 $n$ 为关键字数，$L_i$ 为查找第 $i$ 个关键字时的查找长度。由于二叉排序树中各节点的结构与关键字的插入顺序有关，因此 $L_i$ 的值也与插入顺序有关，无法通过概率论的方法进行计算。在一般情况下，二叉排序树的查找成功时间复杂度为 $O(h)$，其中 $h$ 为树的高度。因此，二叉排序树的平均查找长度与树的高度有关，即：

$$ASL = O(h)$$

由于一棵 $n$ 个节点的随机构造的二叉排序树的平均高度为 $O(\log n)$，因此在等概率情况下，该二叉排序树的平均查找长度为 $O(\log n)$。