基于Huffman树的译码算法/实现
基于Huffman树的译码算法/实现
提问于 2013-11-27 18:52:35
从如下所示的文本文件开始：
a: 0
b: 100
c: 101
d: 11
0 0 100 100 11 101因此，这将解码：aabbdc
我能用什么解码算法来构建哈夫曼树，然后用它来解码消息呢？示例代码也将受到高度赞赏！
以下是我的想法：
- 创建一个查找表，将每个符号映射到其位。
- 创建根节点
- 若要构建树，请从编码的中读取每一位
- 如果为0，则创建一个左子。如果1，创建一个正确的子
- 如果到达空格，则以某种方式指示叶(空的左指针和右指针)
- 使用我们读到的位，直到那个空格，看看这是什么查找表。
- 在那片叶子上插入字符
然后，我可以再读一遍，让它在树上移动。当它击中一个空格时，我只会在它到达的叶子上返回字符？
回答 1
Stack Overflow用户
回答已采纳
发布于 2013-11-27 18:57:10
输入中没有/不应该有任何空格。你应该得到一些类似0010010011101的东西。
要创建树，对于每个字符，从根开始，对于每个位，如果是0，则向左转，如果是1，则向右转(在需要的地方创建节点)。当您到达某个字符的末尾时，将我们所在节点的值设置为该字符。
然后，遍历输入，从树中的根开始--按照上面的步骤执行，但是，不要创建节点，而是在到达叶子时停止，在该节点输出值，然后返回到根。
示例：
a = 0 --只需为根创建一个左子。
.
/
ab = 100 -右转( 1)，然后左转( 0)，然后再左转( 0)。
.
/ \
a .
/
.
/
bc = 101 -右转，左转，右转。
.
/ \
a .
/
.
/ \
b cd = 11 -右转，然后右转.
.
/ \
a .
/ \
. d
/ \
b c在处理输入00100时..。
从根部开始。
我们得到一个0，所以向左走。
我们得到一个值为a的叶子，所以输出它并返回到根。
我们得到一个0，所以向左走。
我们得到一个值为a的叶子，所以输出它并返回到根。
我们得到一个1，所以向右走。
我们得到一个0，所以向左走。
我们得到一个0，所以向左走。
我们得到一个值为b的叶子，所以输出它并返回到根。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/20250688
复制相关文章
相似问题
腾讯云开发者
