how to print all the possible trees python

user_6802442 0
Viewed 383

I have a tree where one node may be branching in two or more ways:

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


    A
   / \
  B   C
 / \
X   Y

Here the node B can either have the branches D and E, or the branches X and Y. Each node is represented as a dictionary in python. E.g. node B = {0: node with D and E as branches, 1: node with X and Y as branches}.

My question is: how do I print the two trees?

So far my program first prints A and B, and then it prints D, E, F, G, then X, Y, and finally C.

I want it to print the first tree completely, as in: A B D E F G C, and then start from the beginning the print the other tree A B X Y C. Can anyone help me with this? I've been playing with it for a whole day without any progress. Any help is greatly appreciated.

Here are my test code:

'''
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()
traversal tree python
1 Answers

To produce all the tree combinations, you can iterate over the possible children for each node (stored under the integer keys of each node dictionary), recursively call the tree building method on each of these children, yielding back the results:

First, the tree setup:

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

Then, the function to produce all the tree combinations:

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)

Output:

('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))
user_73267380
Related