Python 使用递归查找树的路径

Question

我一直在尝试实现基于数字的霍夫曼编码算法。我已经完成了构建霍夫曼树的部分。但是递归算法没有按预期工作。它应该 return 树中从根到指定节点的路径，但它总是 return 错误的路径。

奇怪的是，代码似乎在做正确的事情，而且它可以找到真正的路径。但它 returns 的结果总是不同的。

def get_encoding_for(symbol_p, node, encoding):
    global encoded_string
    result = encoding
    if not isinstance(node, list):
        if symbol_p == node:
            encoded_string = result
            return result
    else:
        for n in node:
            index = str(node.index(n))
            # print("Node {} with index {}".format(n, index))
            result = get_encoding_for(symbol_p, n, encoding + index)

    return result

树结构仅使用列表。

The huffman tree looks like: [[3.0, [1.0, 2.0]], [4.0, 5.0]]

这是使用元素 1、2、3、4、5 的简单树的示例输出。

Loop 1.0. Node 1.0 -> Coding 010:
Loop 2.0. Node 2.0 -> Coding 011:
Loop 3.0. Node 3.0 -> Coding 00:
Loop 4.0. Node 4.0 -> Coding 10:
Loop 5.0. Node 5.0 -> Coding 11:

这就是我想要函数 return 的结果，但在所有五次迭代中它只 return 将我设为“11”。我不得不使用一个全局变量来 "intercept" 正确的编码，我对此并不满意...我认为问题出在 returning 上。我尝试了很多 returning 方法，但其中 none 有效。

有人能告诉我递归有什么问题吗？非常感谢！

Answer 1

在树中搜索一项有点棘手。递归完成后，return 需要表示成功（再次 return）或失败（再次递归）。迭代完成，return 很容易，但需要一个可能的搜索位置的显式堆栈。下面是前者，利用了树的二进制结构。注 1：我使用的名称使我更容易正确地编写它。他们不一定是'better'。注2：我在测试中添加了一个'not found'案例。

def encoding(char, bintree, path):
    if isinstance(bintree, list):
        p = encoding(char, bintree[0], path+'0')
        if p:
            return p
        return encoding(char, bintree[1], path+'1')
    else:
        return path if char == bintree else ''

# Test
hufftree = [[3, [1, 2]], [4, 5]]
for i in range(6):
    print(encoding(i, hufftree, ''))
# Prints

010
011
00
10
11

Answer 2

另一种方法（与我第一个回答中的方法不同）是将生成路径与停止逻辑分开。

def paths(bintree):
    if isinstance(bintree, list):
        for i, p in ((0,'0'), (1,'1')):
            for val, path in paths(bintree[i]):
                yield (val, p + path)
    else:
        yield (bintree, '')

def encoding2(i, bintree):
    for val, path in paths(hufftree):
        if i == val:
            return path
    return ''

# Test
hufftree = [[3, [1, 2]], [4, 5]]
for v in paths(hufftree): print(v)
for i in range(6):
    print(encoding2(i, hufftree))
# Prints

010
011
00
10
11

此时，人们可能会考虑创建一个将值映射到编码的字典。

huffdict = dict(paths(hufftree))
for i in range(6):
    print(huffdict.get(i, ''))
# Prints same as above

Python 使用递归查找树的路径

Python finding paths of trees using recursion

python

recursion

tree

return

path-finding