樹遍歷遞歸

Question

我是編程新手。我的工作我的樹項目

我的樹看起來像這樣 tree structure

我已經寫代碼來遍歷整個樹。目前我traversel將打印整個樹這樣 A，B，E，F，C，d，G，H，I，J，K

def tree_traversal(self, node): 
    if(node != None): 
     print node.name 
     for child_nodes in node.children: 
      self.tree_traversal(child_nodes) 

不過，我想這樣的輸出。

[[A,B,E],[A,B,F],[A,C],[A,D,G,H],[A,D,G,I],[A,D,G,J],[A,D,G,K]] 

Answer 1

既然你沒有給任何樹/節點類，我製作了一個帶有測試：

：

class Node: 
    def __init__(self, data, children=None): 
     if children is None: 
      children = [] 
     self.data = data 
     self.children = children 

    def __str__(self): 
     return str(self.data) 

    __repr__ = __str__ 

從圖像中提取的樹

tree = Node("A", [ 
    Node("B", [ 
     Node("E"), 
     Node("F"), 
    ]), 
    Node("C"), 
    Node("D", [ 
     Node("G", [ 
      Node("H"), 
      Node("I"), 
      Node("J"), 
      Node("K"), 
     ]) 
    ]) 
]) 

你想要的是一種算法，它可以獲得所有可能的根葉路徑。

def get_all_paths(node, path=None): 
    paths = [] 
    if path is None: 
     path = [] 
    path.append(node) 
    if node.children: 
     for child in node.children: 
      paths.extend(get_all_paths(child, path[:])) 
    else: 
     paths.append(path) 
    return paths 

測試它得到你希望的輸出：

paths = get_all_paths(tree) 
print(paths) 
# Prints: 
# [[A, B, E], [A, B, F], [A, C], [A, D, G, H], [A, D, G, I], [A, D, G, J], [A, D, G, K]] 

但是請注意，[A,B,E,F]是不是一個有效的路徑，如F不是E一個孩子。所以我認爲這是一個錯誤。

Answer 2

您基本上想要打印根目錄中的所有路徑。您可以通過傳遞當前路徑來遞歸地執行此操作。

基本情況是當遍歷命中葉節點，將葉節點連接到路徑並打印或做任何你想做的事。

presudo代碼：

def traverse(node, path): 
    if node is None: 
     return 
    if node.left == None and node.right == None: 
     doStuff(path + node.data) 
     return 
    else: 
     traverse(node.left, path + node.data) 
     traverse(node.right, path + node.data)