霍夫曼树图

霍夫曼编码可以压缩文件.

路径

下图中从节点A到节点C的黑线是一条路径.

节点的路径长度

以下节点A到D总共经过两条黑线，并且路径长度为2.

节点的右侧

下图中a节点左侧的值表示该节点的权重.

节点的加权路径长度=节点的路径长度*节点的权重

下图中a节点的路径长度为2，该节点的权重为7，因此该节点的加权路径长度为14.

树的加权路径长度=树的所有节点的加权路径长度之和

下图中整棵树的加权路径长度

7 * 2 + 5 * 2 + 2 * 2 + 4 * 2 = 36

霍夫曼树，也称为最佳二叉树，是加权路径长度最短的树. 下图中的四棵树的下层中的两棵树是霍夫曼树，因为其加权路径长度最短，您可以将其计数. 我们发现，在霍夫曼树上，权重较大的叶子更靠近根节点.

贪婪方法: 构造一个具有较小的首选权重节点的霍夫曼树

构造步骤可以通过配方记忆.

构造森林都是根

选择两棵小树来制作一棵新树

删除两棵小树并添加新树

重复剩下23个单根

例如，存在四个权重分别为7、5、2、4的节点a，b，c，d. 构造霍夫曼树的步骤如下.

首先，将所有节点放入根中，选择权重最小的两个节点2 4 4构造一棵新树，并从原始根中删除它哈夫曼树节点，并将此新树添加到原始中. 在根中，注意应该添加一个新的节点6. 再次重复该操作，选择权重5 6最小的两个节点以构建新树，并从原始根中删除它，然后将此新树添加到原始根中. 注意，应添加一个新节点11. 再次重复该操作，选择权重7 11最小的两个节点以构建新树哈夫曼树节点，并从原始根目录中删除它，然后将此新树添加到原始根目录中. 注意，应该添加一个新节点18. 此时，发现根中只有一个节点，并且构建已完成.

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-212388-1.html