数据结构：霍夫曼树与霍夫曼编码（Huffman Tree）

霍夫曼树与霍夫曼编码（Huffman Tree）

在这样的情况下，如果大多数人都是90分以上，那么大多数人需要进行4次判断才能有结果，造成时间的浪费。

【引申：判断的时候要把最常发生、最可能发生的情况放在前面】

—>如何根据节点不同的查找频率构造更有效的搜索树？

霍夫曼树的定义

带权路径长度（WPL）

设二叉树有n个叶子结点，每个叶子结点带有权值$w_k$wk​，从根节点到每个叶子结点的长度为$I_k$Ik​（这个$I_k$Ik​不是边的长度，而是从根节点到这个节点的边长+1，即根节点为1，往下数依次加一（假设边权为1）），则每个叶子结点的带权路径长度之和就是：$WPL = \sum\limits_{k-1}^{n}w_kI_k$WPL=k−1∑n​wk​Ik​

最优二叉树 或 霍夫曼树

WPL最小的二叉树。

霍夫曼树的构造

核心：每次把权值最小的两颗二叉树合并

合并后，即出现一颗新的树，该树的节点为两个子树的权值的和，把这个和去与其他的权值比较，再选出两个最小的合并，以此类推，知道最后只剩下两个节点（子树），将他们合并。

“选取两个最小的”：用**最小堆**实现

霍夫曼树的特点

1、没有度为1的节点。构造的时候始终是两两合并。

2、n个叶子结点的霍夫曼树共有2n-1个节点。

（此时n1=0，故总数为n0+n2 = 2n）

3、霍夫曼树的任意非叶节点的左右子树交换后仍是霍夫曼树。

4、对同一组权值{w1，w2，……}，存在不同构的霍夫曼树。但是他们**具有相同的WPL值**！

霍夫曼编码

二叉树用于编码【前缀码】：当所有字符节点都在叶节点上时，就是前缀码，没问题，不会有二意性。

->怎么构造一棵编码代价最小的二叉树？

霍夫曼树