给定一组权值{3,6,9,14,8,5,4,19,25},试设计相应的哈夫曼树,并求其带权路径长
时间: 2023-09-22 11:12:23 浏览: 130
首先,将权值从小到大排序:{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
相关问题
给定一组权值(5,9,11,2,7,16),试设计相应的哈夫曼树,画出并截图提交。
首先,我们需要根据权值构建小根堆(也可以使用大根堆),然后不断取出权值最小的两个节点,合并成一个新节点,直到堆中只剩下一个节点,这个节点即为哈夫曼树的根节点。
具体步骤如下:
1. 将权值构建成小根堆:
<img src="https://img-blog.csdn.net/20180723093623410?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NjaGVtYXMvcXBfc2VhcmNo/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/q/80" width="400" />
2. 取出堆中权值最小的两个节点(2和5),合并成一个新节点,新节点的权值为2+5=7,并将新节点插入堆中:
<img src="https://img-blog.csdn.net/20180723093635353?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NjaGVtYXMvcXBfc2VhcmNo/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/q/80" width="400" />
3. 再次取出堆中权值最小的两个节点(7和7),合并成一个新节点,新节点的权值为7+7=14,并将新节点插入堆中:
<img src="https://img-blog.csdn.net/20180723093648477?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NjaGVtYXMvcXBfc2VhcmNo/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/q/80" width="400" />
4. 再次取出堆中权值最小的两个节点(9和11),合并成一个新节点,新节点的权值为9+11=20,并将新节点插入堆中:
<img src="https://img-blog.csdn.net/20180723093703105?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NjaGVtYXMvcXBfc2VhcmNo/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/q/80" width="400" />
5. 再次取出堆中权值最小的两个节点(14和16),合并成一个新节点,新节点的权值为14+16=30,并将新节点插入堆中:
<img src="https://img-blog.csdn.net/20180723093716684?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NjaGVtYXMvcXBfc2VhcmNo/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/q/80" width="400" />
6. 最后,取出堆中唯一的节点(30),即为哈夫曼树的根节点:
<img src="https://img-blog.csdn.net/20180723093732740?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NjaGVtYXMvcXBfc2VhcmNo/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/q/80" width="400" />
因此,给定权值(5,9,11,2,7,16)的哈夫曼树如下所示:
<img src="https://img-blog.csdn.net/20180723093743808?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NjaGVtYXMvcXBfc2VhcmNo/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/q/80" width="400" />
给定一组权值(5,9,11,2,7,16),设计相应的哈夫曼树,并给出其哈夫曼编码
首先,我们需要根据给定的权值构建哈夫曼树:
1. 将所有的节点按照权值从小到大排序,得到:(2,5,7,9,11,16)
2. 取出权值最小的两个节点(2,5),将它们合并成一个新的节点,权值为它们的和(7)。此时,节点集合变为(7,7,9,11,16)。
3. 再次取出权值最小的两个节点(7,7),将它们合并成一个新的节点,权值为它们的和(14)。此时,节点集合变为(9,11,14,16)。
4. 再次取出权值最小的两个节点(9,11),将它们合并成一个新的节点,权值为它们的和(20)。此时,节点集合变为(14,16,20)。
5. 再次取出权值最小的两个节点(14,16),将它们合并成一个新的节点,权值为它们的和(30)。此时,节点集合变为(30,20)。
6. 最后,将剩下的两个节点(30,20)合并成一个根节点,权值为它们的和(50)。这样就得到了哈夫曼树。
哈夫曼树如下所示:
```
50
/ \
20 30
/ \
14 16
/ \
7 9
/ \ / \
2 5 7 11
```
接下来,我们需要给每个节点(除了根节点)赋予一个编码。我们规定从根节点到左子树的路径为0,从根节点到右子树的路径为1。那么,每个节点的编码就是从根节点到该节点路径上的数字序列。比如节点2的编码为左子树-左子树-左子树,即000。
最后,我们可以得到每个节点的哈夫曼编码:
```
2: 000
5: 001
7: 010
9: 011
11: 100
16: 101
14: 1100
20: 1101
30: 111
50: -
```
其中,根节点没有编码,因为它不需要表示任何字符。