我正在嘗試使用 Python 列印嵌套串列，以便我們可以擁有它們的多個副本。
我的問題是：如何在 DFS 中以x[0]父級和x[1:]子級的身份正確遞回地列印它？
例如，我有這個輸入
['1', ['2', ['3', ['4', ['5', ['6', ['7']], ['8', ['9']]]]]]]
它可以擴展為以這種結構可視化：
['1',
['2',
['3',
['4',
['5',
['6',
['7']
],
['8',
['9']
]
]
]
]
]
]
我正在嘗試以遞回方式列印并期望得到一個看起來像這樣的結果，并列印出整個路徑。
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
1 -> 2 -> 3 -> 4 -> 5 -> 8 -> 9
但實際上最終得到了這個
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
5 -> 8 -> 9
這是我的代碼片段
def __print(chains: List):
"""
Assuming the input list where index 0 is the source, and index 1 is its
children paths.
"""
if (len(chains) == 0):
return
elif (len(chains) == 1):
# reaching the end
print("{0}".format(chains[0]))
return
else:
# everything after index 0 is considered children
children = chains[1:]
# has children
for child in children:
print("{0} -> ".format(chains[0]), end='')
__print(child)
uj5u.com熱心網友回復：
您的方法在理論上看起來很棒，因為您不需要保留額外的狀態。但是不保持狀態存在問題。假設您位于父節點。沒有辦法知道你應該列印多少次這個節點的值，因為你必須遍歷樹才能確定它最終是多少葉節點的根。缺少換行符使事情進一步復雜化。
因此，我看不到將路徑傳遞到子呼叫的明顯方法。當您點擊終端節點時，只需列印將您帶到這里的路徑。否則，將當前節點推送到路徑上并將其傳遞給遞回呼叫，然后在探索完所有子節點后將其彈出。
我不喜歡print函式。這禁止呼叫者對結果做任何有用的事情。最好回傳一個生成器，讓呼叫者用它做他們想做的事。
作為一種優化，您可以在整個程序中使用一個串列，僅在需要時復制到yield路徑。
def find_paths(chains, path=None):
if path is None:
path = []
if not chains:
return
path.append(chains[0])
if len(chains) == 1:
yield tuple(path)
else:
for child in chains[1:]:
yield from find_paths(child, path)
path.pop()
if __name__ == "__main__":
tree = ["1", ["2", ["3", ["4", ["5", ["6", ["7"]], ["8", ["9"]]]]]]]
for path in find_paths(tree):
print(" -> ".join(path))
這里的額外空間成本是 O(tree depth)。
另一件事：混合型別的資料結構很難使用。在以下使用字典將節點有效負載與子節點分開的典型樹格式中，此結構將更容易處理：
{
"value": "1",
"children": [
{
"value": "2",
"children": [...],
},
],
}
這樣可以很容易地吸引孩子；不需要切片，這是浪費時間和空間，或者必須做type()/isinstance()呼叫來弄清楚是什么（在你的情況下，第一個元素是一個字串，其余的是串列，避免型別檢查，但它得到了靠近骯臟的領土......）。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/495653.html
標籤：Python python-3.x 递归 深度优先搜索
上一篇：立即回傳遞回呼叫
下一篇：嵌套物件遞回問題