如何"walk"这棵由列表、元组和字符串组成的树？

Question

树结构：

T
|__A1
|   |__B1
|   |__B2
|       |__D1
|__A2
    |__C1
    |__C2
    |__C3
        |__E1
            |__F1
           E2
            |__G1
            |__G2

解析为：

[('T',
  [('A1', ['B1', ('B2', ['D1'])]),
   ('A2', ['C1', 'C2', ('C3', [('E1', ['F1']), ('E2', ['G1', 'G2'])])])])]

或（同样的事情）：

[('T',
  [('A1',
    [
     'B1',
     ('B2', ['D1'])
    ]
   ),
   ('A2',
    [
     'C1',
     'C2',
     ('C3',
      [
       ('E1', ['F1']),
       ('E2', ['G1', 'G2'])
      ]
     )
    ]
   )
  ]
)]

一个 iterate/traverse/walk 一棵树怎么能以这种方式格式化？我知道这是一个相当具体的问题，但我真的被困在这一点上。预期目标是输出 从根到每个端节点的所有可能路由 ，像这样（类型不重要，但可以是例如：字符串列表）：

T A1 B1
T A1 B2 D1
T A2 C1
T A2 C2
T A2 C3 E1 F1
T A2 C3 E2 G1
T A2 C3 E2 G2

该代码远不能正常工作，但它可能显示出一般倾向：

formatted_tree = [('T',[('A1', ['B1', ('B2', ['D1'])]),('A2', ['C1', 'C2', ('C3', [('E1', ['F1']), ('E2', ['G1', 'G2'])])])])]

def walk(n):
    if isinstance(n, basestring):
        yield n # end-branches
    else:
        if isinstance(n, tuple): # root,[bra,nch,es]
            yield n[0]
            walk(n[1])
        elif isinstance(n, list): # LIST=branches (can be tuples or string)
            for branch in n:
                walk(branch)

[path for path in walk(formatted_tree)]

Answer 1

此代码应该有效

tree = [('T',
  [('A1', ['B1', ('B2', ['D1'])]),
   ('A2', ['C1', 'C2', ('C3', [('E1', ['F1']), ('E2', ['G1', 'G2'])])])])]


def print_node(header, tree):
    if isinstance(tree,str):
        return [header+' '+str(tree)]
    else:
        head, tail = tree
        return reduce(lambda a,b:a+b,[print_node(header + ' ' + head,t_element) for t_element in tail])

def print_tree(tree):
    children = tree[0]
    print '\n'.join(print_node('',children))

print_tree(tree)

它将结果列表保存在内存中并执行简单的递归。 print_tree 只是将输入以正确形式放置的包装器。希望对您有所帮助！

如何"walk"这棵由列表、元组和字符串组成的树？

How to "walk" this tree consisting of lists, tuples and strings?

python

tree

python-2.7