a律13折线pcm编码例题_数据结构题：根据所给权值设计相应的哈夫曼树,并设计哈夫曼编码...

╰+攻爆jí腚メ 2023-01-01 12:58 49阅读 0赞

# 前言 #

在数据结构树的这章中，常常有题目，是这样的“给定一组权值…，试设计相应的哈夫曼树”，有的还要求其带权路径长度，还有的是给定字符以及其使用频率，要求设计一个哈夫曼编码，同时要求设计哈夫曼树等等。  
为此这种题的步骤解法，我将做详细的讲解，本文介绍两种题型，分别是求哈夫曼树以及设计哈夫曼编码，希望对阅读本博客以及有需要的小伙伴有用，如有错误不当之处，欢迎大佬们指正！  
(???)

--------------------

提示：以下是本篇文章正文内容，下面案例可供参考。

# 一、涉及到的知识点 #

哈夫曼树：给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树，可以说，哈夫曼树是一种特殊的二叉树，这种树的所有的叶子结点都有权值，从而构造出带权路径长度最短的二叉树，其中权值较大的结点离根较近。路径长度：树中路径上的分支数目。树的路径长度：根结点到树中每个结点的路径长度之和。叶子结点的权值：权值是人们根据需要为每个叶子结点赋予的一个数值。叶子结点的带权路径长度：树根到一个叶子结点之间的路径长度与该结点权值的乘积。树的带权路径长度：树中所有叶子结点的权值乘以该结点的路径长度之和，公式如下：![af85381d3fbf7254bc1c42c9166008b8.png][]  
其中，Wk为第k个叶子结点的权值，Lk是从根结点到第k个叶子结点的路径长度。哈夫曼编码：树中从根到每个叶子都有一条路径， 对路径上的各分枝约定指向左子树根的分枝表示“ 0 ” 码， 指向右子树的分枝表示“ 1 ” 码， 取每条路径上的“ 0 ” 或“ 1 ” 的序列作为和各个叶子对应的字符的编码， 这就是哈夫曼编码。

--------------------

好接下来，我们了解了基本知识后，来看看这两道题简单的巩固一下

e.g.  
1、求下图中二叉树的带权路径长度

![a699e381e37b7bc2a6f9aa8c4c9ece55.png][]  
解：结果如下：  
WPL=2×2+3×2+4×2+6×2=30  
2、写出下图哈夫曼树中D和F的哈夫曼编码(提示：哈夫曼树的每个左分支设为0，右分支设为1)![8877ab9d75fb8236008831b80a3bb167.png][]  
解：D和F的哈夫曼编码为  
D:00  
F:10

--------------------

接下来，我们一起进入正题部分，两道例题了解一下?

# 二、例题讲解 #

## 1、例题1 ##

给定权值\{5,10,12,15,30,40\}，构造相应的哈夫曼树(要求写出构造步骤)，并求出该树的带权路径长度。(提示：哈夫曼树的每个左分支设为0，右分支设为1，要求同层中叶子结点权值从左到右，从小到大)。

解：注：只要将最小的两个权值合并, 合并后的值再入列中(最小的两个出列), 直至列中只有一个值结束。  
按权值大小排列后得： \{5,10,12,15,30,40\}，  
取5和10，得到5+10=15，  
从\{12，15，15，30，40\}找两个最小的12+15=27  
\{15，27，30，40\}中取15+27=42  
\{30，40，42\}中取30+40=70  
\{42，70\}中取42+70=112  
\{112\}停止。

因为要求同层中叶子结点权值从左到右，从小到大，即分别建立左右分支，不懂的小伙伴可以仔细看一下上述过程以及画的图，另题目要求在哈夫曼树的每个左分支设为0，右分支设为1。则哈夫曼树如下:![91285ec0c3456d92a61bbc7faacd78e8.png][]  
带权路径长度：  
(5+10+12+15)×3+(15+30+40)×2=166提示：哈夫曼树中黄荧光笔标记处，画图中不用标出，为读者方便理解特注，即算这些所标记的叶子。

--------------------

具体步骤图例：![524176cec52833c3ce8f5e717a139167.png][]![e83cdb45cf69b018d9c887047a4ba865.png][]![0beb5f19a8c49e0381137f6372a4a33c.png][]![966fe5f4f38efe810425e693d96d1f81.png][]

--------------------

## 2、例题2 ##

已知一个电文字符集中有8个字符\{A,B,C,D,E,F,G,H\}，它们使用的频率为\{0.04，0.21，0.06，0.07，0.15，0.18，0.12，0.03\}，设计一个哈夫曼编码。(提示：哈夫曼树的每个分支左分支设为0，右分支设为1，要求同层中叶子结点权值从左到右，从小到大)。解：将使用的频率乘以100，得到它们的权值  
乘以100，得：\{4，21，6，7，15，18，12，3\}，  
按大小排序后，\{3，4，6，7，12，15，18，21\}  
取3和4，得3+4=7，  
从\{6，7，7，12，15，18，21\}中取6+7=13  
\{7，12，13，15，18，21\}中取7+12=19  
\{13，15，18，19，21\}中取13+15=28  
\{18，19，21，28\}中取18+19=37  
\{21，28，37\}中取21+28=49  
\{37，49\}中取37+49=86  
\{86\}停止则哈夫曼树如下:![00fab944d5cc6fb10c200e3ffbf81281.png][]  
由哈夫曼树得到哈夫曼编码为(由上至下编码)：  
A：0101  
B: 10  
C: 1100  
D: 1101  
E:111  
F: 00  
G:011  
H:0100

[af85381d3fbf7254bc1c42c9166008b8.png]: /images/20221120/8c09f1bce03d4565863b4ec0463b8315.png
[a699e381e37b7bc2a6f9aa8c4c9ece55.png]: /images/20221120/2127cc6ae2c946ef9baf12a6a545e2e5.png
[8877ab9d75fb8236008831b80a3bb167.png]: /images/20221120/f33c31bead54470c8dad9f762136aa19.png
[91285ec0c3456d92a61bbc7faacd78e8.png]: /images/20221120/839027342dfb441a952311054e0f7680.png
[524176cec52833c3ce8f5e717a139167.png]: https://img-blog.csdnimg.cn/img_convert/524176cec52833c3ce8f5e717a139167.png
[e83cdb45cf69b018d9c887047a4ba865.png]: https://img-blog.csdnimg.cn/img_convert/e83cdb45cf69b018d9c887047a4ba865.png
[0beb5f19a8c49e0381137f6372a4a33c.png]: https://img-blog.csdnimg.cn/img_convert/0beb5f19a8c49e0381137f6372a4a33c.png
[966fe5f4f38efe810425e693d96d1f81.png]: /images/20221120/0f48b352226144f88175462e6f568fa6.png
[00fab944d5cc6fb10c200e3ffbf81281.png]: /images/20221120/493f81e1235f44f08705d31e7e3d028f.png