前言

在数据结构树的这章中，常常有题目，是这样的“给定一组权值…，试设计相应的哈夫曼树”，有的还要求其带权路径长度，还有的是给定字符以及其使用频率，要求设计一个哈夫曼编码，同时要求设计哈夫曼树等等。

为此这种题的步骤解法，我将做详细的讲解，本文介绍两种题型，分别是求哈夫曼树以及设计哈夫曼编码，希望对阅读本博客以及有需要的小伙伴有用，如有错误不当之处，欢迎大佬们指正！

（😊😊😊）

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

一、涉及到的知识点

哈夫曼树：给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树，可以说，哈夫曼树是一种特殊的二叉树，这种树的所有的叶子结点都有权值，从而构造出带权路径长度最短的二叉树，其中权值较大的结点离根较近。

路径长度：树中路径上的分支数目。

树的路径长度：根结点到树中每个结点的路径长度之和。

叶子结点的权值：权值是人们根据需要为每个叶子结点赋予的一个数值。

叶子结点的带权路径长度：树根到一个叶子结点之间的路径长度与该结点权值的乘积。

树的带权路径长度：树中所有叶子结点的权值乘以该结点的路径长度之和，公式如下：

其中，Wk为第k个叶子结点的权值，Lk是从根结点到第k个叶子结点的路径长度。

哈夫曼编码：树中从根到每个叶子都有一条路径， 对路径上的各分枝约定指向左子树根的分枝表示“ 0 ” 码， 指向右子树的分枝表示“ 1 ” 码， 取每条路径上的“ 0 ” 或“ 1 ” 的序列作为和各个叶子对应的字符的编码， 这就是哈夫曼编码。

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

e.g.

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

解：结果如下：

WPL=2×2+3×2+4×2+6×2=30

2、写出下图哈夫曼树中D和F的哈夫曼编码（提示：哈夫曼树的每个左分支设为0，右分支设为1）

解：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。

则哈夫曼树如下:

带权路径长度：

（5+10+12+15）×3+（30+40）×2=266

提示：哈夫曼树中黄荧光笔标记处，画图中不用标出，为读者方便理解特注，即算这些所标记的叶子。

具体步骤图例：

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}停止

则哈夫曼树如下:

由哈夫曼树得到哈夫曼编码为(由上至下编码)：

A：0101

B: 10

C: 1100

D: 1101

E:111

F: 00

G:011

H:0100

总结

以上就是全部内容，本文简单介绍了哈夫曼树的一些基本知识和如何求哈夫曼树以及如何设计哈夫曼编码的方法，希望能给读者带来帮助。