一、哈夫曼树的基本概念
哈夫曼树称为最优树，是一类带权外路径长度最小的树。
相关概念：
（1）扩充二叉树：只存在度为0或2的二叉树。
（2）树的内路径长度：从根节点到所有非叶子节点的路径之和。
（3）树的外路径长度：从根节点到所有叶子节点的路径之和。
（4）权：给树中所有的节点赋予一定的权值。
（5）树的带权路径长度（WPL）：树中所有叶子节点的带权路径长度（根节点到改节点的路径与该点的权值的乘积）之和。
哈夫曼树是带权路径长度最小的树。
二、哈夫曼算法
给定n个权值，步骤如下：
（1）用给定的权值构建n个左右子树均为空的二叉树。每个权值即为二叉树的根节点。
（2）在（1）中构成的森林中选取权值最小和次小的权值构建新的二叉树，新二叉树的左孩子为最小权值的节点，右孩子为次小权值的节点。新的根节点为两个孩子节点的和。
（3）将（2）中两个节点在（1）中的森林中删除。并将（2）中新生成的二叉树插入到（1）的森林中。
（4）重复执行（2）和（3），直到森林中只剩一颗二叉树时算法结束。这一颗树即为哈夫曼树。
三、哈夫曼编码
背景：
在数据进行传输时，为了提高传输的效率，通常要堆文件进行压缩操作。早期的哈夫曼编码就是利用哈夫曼树的特性对文件进行压缩。哈夫曼树中的每个节点都对应一个数据元。根节点的左孩子指定为0，有孩子指定为1。因为数据由数据元组成，我们可以将数据分割为数据元，再将数据源用0 1 序列表示。以此实现了哈夫曼编码。
网友评论