树遍历递归

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)