霍夫曼编码树遍历

Question

在Python中编写霍夫曼编码算法。已成功设法基于字符串输入创建一棵树，但在为每个字母生成代码时仍坚持遍历它的最佳方法。

from collections import Counter
    class HuffNode:
        def __init__(self, count, letter=None):
            self.letter = letter
            self.count = count
            self.right = None
            self.left = None

    word = input()
    d = dict(Counter(word))

    Nodes = [HuffNode(d[w], w) for w in sorted(d, key=d.get, reverse=True)]

    while len(Nodes) > 1:
        a = Nodes.pop()
        b = Nodes.pop()
        c = HuffNode(a.count+b.count)
        c.left, c.right = a, b

        Nodes.append(c)
        Nodes.sort(key=lambda x: x.count, reverse=True)

对于像 "hello".

这样的词

d = dict(Counter(word)) 将获取字符串中每个字母的频率并将其转换为字典。因此有 {'e': 1, 'l': 2, 'h': 1, 'o': 1} 每个字母 if 然后转换为 HuffNode 并存储在 Nodes

然后 while 循环继续生成一棵树，直到我们只有一个根

When the loop exits I'll have: 遍历这棵树然后为每个字母生成代码的最佳方法是什么？谢谢

Answer 1

一般来说，您需要一个递归函数，给定 HuffNode h 和前缀 p:

如果 h.letter 不为空（即 h 是一片叶子），产生 (p, h.letter) -> 这是字母
否则，在 h.left 上使用前缀 p + '0' 调用自身，在 h.right 上使用 p + '1'

一个可能的实现（未测试，可能有拼写错误）：

def make_code(node, prefix):
    if node is None:
        return []
    if node.letter is not None:
        return [(prefix, node.letter)]
    else:
        result = []
        result.extend(make_code(h.left, prefix + '0'))
        result.extend(make_code(h.right, prefix + '1'))
        return result

codes = make_code(root, '')

其中root是您在第一步中构建的哈夫曼树。第一个测试（if node is None）是管理不平衡的节点，其中一个children可能是空的。

霍夫曼编码树遍历

Huffman Coding Tree traversal

python

algorithm

compression

huffman-code

对于像 "hello".