python - 如何打印所有可能的树python

Question

我有一棵树，其中一个节点可能以两种或多种方式分支:

    A
   /  \
  B    C
 / \
D   E
   /  \
  F    G


    A
   / \
  B   C
 / \
X   Y

这里节点 B 可以有分支 D 和 E ，或分支机构 X 和 Y .
每个节点在python中表示为一个字典。例如。节点 B = {0:以 D 和 E 为分支的节点，1:以 X 和 Y 为分支的节点}。

我的问题是:如何打印两棵树？

到目前为止，我的程序首先打印 A 和 B，然后打印 D、E、F、G，然后是 X、Y，最后是 C。

我希望它完全打印第一棵树，如: A B D E F G C ，然后从头开始打印另一棵树 A B X Y C .谁能帮我这个？我已经玩了一整天了，没有任何进展。任何帮助是极大的赞赏。

这是我的测试代码:

'''
print all the possible trees
'''

class Tree():
    '''each node is a dict of Nodes, because there can be multiple parses'''
    def __init__(self, root=None):
        self.root = self.build(root)
        self.printTrees(root)

    def build(self, p):
        # p is a dict as in A = {0: ('a', B, C, False), 'terminal':False}
        if p['terminal']: # if terminal
            node = {}
            for key in p.keys():
                if key != 'terminal':
                    node[key] = Node(p[key][0], None, None, True)
            return node

        node = {}
        for key in p.keys():
            if key != 'terminal':
                node[key] = Node(p[key][0], # type
                    self.build(p[key][1]), # left
                    self.build(p[key][2])) # right
        return node

    def printTrees(self, p):
        '''TODO complete print one tree and then go to another tree!'''
        if p['terminal']: # if terminal
            for key in p.keys():
                if key != 'terminal':
                    print(p[key][0], end='  ')
            return

        for key in p.keys():
            if key != 'terminal':
                print(p[key][0])
                self.printTrees(p[key][1]) # left
                self.printTrees(p[key][2]) # right

class Node():
    def __init__(self, typ=None, left=None, right=None, terminal=False):
        self.type = typ
        self.left = left
        self.right = right
        self.terminal = terminal

    def __str__(self):
        return "Node: "+self.type

def main():
    X = {0: ('x', None, None), 'terminal':True}
    Y = {0: ('y', None, None), 'terminal':True}

    G = {0: ('g', None, None), 'terminal':True}
    F = {0: ('f', None, None), 'terminal':True}
    D = {0: ('d', None, None), 'terminal':True}
    C = {0: ('c', None, None), 'terminal':True}

    E = {0: ('e', F, G, False), 'terminal':False}
    B = {0: ('b', D, E, False), 1: ('b', X, Y, False), 'terminal':False}
    A = {0: ('a', B, C, False), 'terminal':False}

    t = Tree(A)

if __name__ == '__main__':
    main()

Answer 1

要生成所有树组合，您可以遍历每个节点的可能子节点(存储在每个节点字典的整数键下)，递归调用每个子节点的树构建方法，yield返回结果:
首先，树设置:

def get_tree():
    X = {0: ('x', None, None), 'terminal':True}
    Y = {0: ('y', None, None), 'terminal':True}
    G = {0: ('g', None, None), 'terminal':True}
    F = {0: ('f', None, None), 'terminal':True}
    D = {0: ('d', None, None), 'terminal':True}
    C = {0: ('c', None, None), 'terminal':True}
    E = {0: ('e', F, G, False), 'terminal':False}
    B = {0: ('b', D, E, False), 1: ('b', X, Y, False), 'terminal':False}
    A = {0: ('a', B, C, False), 'terminal':False}
    return A

然后，生成所有树组合的函数:

from itertools import product
def get_trees(t):
   for a, b in t.items():
      if isinstance(a, int):
         v = [[b[0]], *[[i] if i is None else list(get_trees(i)) for i in b[1:3]]]
         yield from product(*v)

trees = list(get_trees(get_tree()))
for tree in trees:
   print(tree)

输出:

('a', ('b', ('d', None, None), ('e', ('f', None, None), ('g', None, None))), ('c', None, None))
('a', ('b', ('x', None, None), ('y', None, None)), ('c', None, None))