本文主要是介绍【算法概论】Huffman树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1、哈夫曼树，又叫最优二叉树：效率最高的判决数。
2、回忆树的相关知识
① 路径长度：路径上的结点数 - 1。
② 结点的权：在许多应用中，常常给树的结点赋予一个有意义的数，称为该结点的权。
③ 结点的带权路径长度：该结点到树根的路径长度 × 该结点的权。
④ 树的带权路径长度：树上所有叶子结点的带权路径长度之和，通常记作 WPL 。
3、哈夫曼树定义
在权为w1, w2, …, wn的 n 个叶子结点的所有二叉树中，带权路径长度 WPL 最小的二叉树称为赫夫曼树或最优二叉树。
4、哈夫曼树的构造(哈夫曼算法)
① 根据给定的 n 个权值 { w1, w2, … , wn } 构成二叉树集合 F = { T1, T2, … , Tn }，其中每棵二叉树 Ti 中只有一个带权为 wi 的根结点，其左右子树为空。
② 在 F 中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为左右子树根结点的权值之和。
③ 在 F 中删除这两棵树，同时将新的二叉树加入 F 中。
④ 重复2、3，直到 F 只含有一棵树为止。(得到哈夫曼树)
5、关于哈夫曼树的注意点
① 满二叉树不一定是哈夫曼树；
② 哈夫曼树中权越大的叶子离根越近（很好理解，WPL最小的二叉树）；
③ 具有相同带权结点的哈夫曼树不惟一；
④ 哈夫曼树的结点的度数为 0 或 2， 没有度为 1 的结点；
⑥ 包含 n 个叶子结点的哈夫曼树中共有 2n – 1 个结点；
⑦ 包含 n 棵树的森林要经过 n–1 次合并才能形成哈夫曼树，共产生 n–1 个新结点。
参考：哈夫曼（huffman）树和哈夫曼编码
这篇关于【算法概论】Huffman树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
