赫夫曼树

发表于 | 分类于

树-赫夫曼树

基本概念

  • 结点路径：从树中一个结点到另一个结点的之间的分支构成这两个结点之间的路径。
  • 路径长度：结点路径上的分支数目。
  • 树的路径长度：从树根到每一个结点的路径长度之后。
  • 带权路径长度(WPL)：设二叉树有n个叶子结点，每个叶子结点带有权值wi,从根结点到每个叶子结点的长度为li,则每个叶子结点的带权路径长度之和就是: equation
  • Huffman树：具有n个叶子结点的二叉树不止一棵，但在所有的这些二叉树中，必定存在一颗WPL值最小的树。

构造哈夫曼树

哈夫曼树的特点

  • 没有度为1的结点；

  • 哈夫曼树的任意分支结点的左右子树交换后仍是哈夫曼树；

  • n个叶子结点的哈夫曼树共有2n-1个结点。

基本运用

  • (1)修理牧场：农夫要修理牧场的一段栅栏，他测量了栅栏，发现需要N块木头，每块木头长度为整数Li个长度单位，于是他购买了一条很长的、能锯成N块的木头，即该木头的长度是Li的总和。但是农夫自己没有锯子，请人锯木头的酬金跟这段木头的长度成正比。为简单起见，不妨就设酬金等于所锯木头的长度。例如，要将长度为20的木头锯成长度为8、7和5的三段，第一次锯木头花费20，将木头锯成12和8；第二次锯木头花费12，将长度为12的木头锯成7和5，总花费为32。如果第一次将木头锯成15和5，则第二次锯木头花费15，总花费为35（大于32）。请编写程序帮助农夫计算将木头锯成N块的最少花费。首先输入一个正整数N（N≤104），表示要将木头锯成N块。接着给出N个正整数L（Li≤50），表示每段木块的长度。输出一个整数，即将木头锯成N块的最少花费。

  • (2)压缩软件：给定一篇文章，只含有英文大小写字母和空格，以.txt格式存储，统计该文件中各种字符的频率，对各字符进行Huffman编码，将该文件翻译成Huffman编码文件，再将Huffman编码文件翻译成源文件。