前言
本篇章主要介绍哈夫曼树及哈夫曼编码,包括哈夫曼树的一些基本概念、构造、代码实现以及哈夫曼编码,并用Python实现。
1. 基本概念
哈夫曼树(Huffman(Huffman(Huffman Tree)Tree)Tree),又称为最优二叉树,指的是带权路径长度最小的二叉树。树的带权路径常记作:
其中,nnn为树中叶子结点的数目,wkw_kwk为第kkk个叶子结点的权值,lkl_klk为第kkk个叶子结点与根结点的路径长度。
带权路径长度是带权结点和根结点之间的路径长度与该结点的权值的乘积。有关带权结点、路径长度的概念请参阅这篇博客。
对于含有nnn个叶子结点的哈夫曼树,其共有
1