哈夫曼树又称最优树,是一类带权路径长度最短的树。在本例中我们用它对字符进行编码。首先先创建一个哈夫曼树,然后从叶子节点开始往根上寻找路线,是左子树则编码为0,右子树编码为1. 有一个步骤我们需要将最小的两个权值的叶子结点合并成一个节点,同时还要删除这两个节点,我用的是优先队列,优先队列出来的是权值最小的点,我们把他们合并之后可以很容易的删除。同时要注意哈夫曼树并不唯一,但是他们都具有最小的WPL(树的带权路径长度)。
1 |
|
云腾致雨,露结为霜
哈夫曼树又称最优树,是一类带权路径长度最短的树。在本例中我们用它对字符进行编码。首先先创建一个哈夫曼树,然后从叶子节点开始往根上寻找路线,是左子树则编码为0,右子树编码为1. 有一个步骤我们需要将最小的两个权值的叶子结点合并成一个节点,同时还要删除这两个节点,我用的是优先队列,优先队列出来的是权值最小的点,我们把他们合并之后可以很容易的删除。同时要注意哈夫曼树并不唯一,但是他们都具有最小的WPL(树的带权路径长度)。
1 | #include <bits/stdc++.h> |