ツリートラバーサル再帰

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

あなたが任意のツリー/ノードクラスを与えていないので、私がテストするために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]] 

しかしFがEの子ではないよう[A,B,E,F]は、有効なパスではないことに注意してください。だから私はこれが間違いだと思う。

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)