Python使用遞歸找到樹的路徑

Question

我一直在試圖實現基於數字的霍夫曼編碼算法。我已經完成了構建霍夫曼樹的部分。但遞歸算法不能按預期工作。它應該返回樹中從根到指定節點的路徑，但它總是返回錯誤的路徑。

奇怪的是，代碼似乎在做什麼是正確的，它可以找到真正的路徑。但它返回的結果總是別的東西。

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: 

這就是我想要的函數返回，但它只在所有五次迭代中返回我「11」。我不得不使用全局變量來「截取」正確的編碼，我對此並不滿意......我認爲問題在於迴歸。我嘗試了很多返回的方法，但都沒有工作。

有人能告訴我遞歸有什麼問題嗎？非常感謝！

Answer 1

另一種方法（從我的第一個答案）是將生成路徑與停止邏輯分開。

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 

Answer 2

在一棵樹上搜索一個項目有點棘手。遞歸執行，返回需要表示成功（再次返回）或失敗（再次遞歸）。迭代完成後，返回很容易，但需要一個明確的可能的搜索位置堆棧。前者利用了樹的二進制結構。注1：我使用的名稱使me更容易正確寫入。他們不一定「更好」。注2：我在測試中添加了一個「未找到」的情況。

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