CODEWITHSUNDEEP
pythonbinary-treebreadth-first-search
TomMe
TomMe

Reputation: 65

BFS in python from a preorder and inorder

(Python 2.7)I need to print the bfs of a binary tree with a given preorder and inorder and a max lenght of the strings of preorder and inorder. I know how it works, for example: preorder:ABCDE inorder:CBDAE max length:5

                A
             /     \
           B        E
          / \         
         C   D

BFS:ABECD

So far I got this figured out

class BinaryTree:
    def __init__ (self, value, parent=None):
            self.parent = parent
            self.left_child = None
            self.right_child = None
            self.value=value

    def setLeftChild(self, child=None):
            self.left_child = child
            if child:
                child.parent = self

    def setRightChild(self, child=None):
            self.right_child = child
            if child:
                child.parent = self


preorder={}
inorder={}

print "max string length?"
i=int(raw_input())
count=0
while i>count:
    print"insert the preorder"
    preorder[raw_input()]=count
    count=count+1
print "preorder is",sorted(preorder, key=preorder.get)

count2=0
while i>count2:
    print"insert the inorder"
    inorder[raw_input()]=count2
    count2=count2+1
print "inorder is",sorted(inorder, key=inorder.get)
root=

I've figured out how to create a binary tree in python but the thing is I don't know how to add the values of the next childs. As you can see I already have the root and figured out how to insert the first childs (left and right) but I don't know how to add the next ones.

Upvotes: 3

Views: 1073

Answers (3)

Jon Clements
Jon Clements

Reputation: 142166

If you're using BFS - you ideally want to be using a graph - an excellent library is networkx

An example:

import networkx as nx

g = nx.DiGraph()
g.add_edge('A', 'B')
g.add_edge('A', 'E')
g.add_edge('B', 'C')
g.add_edge('B', 'D')

print 'A' + ''.join(node[1] for node in (nx.bfs_edges(g, 'A')))

# ABECD

Upvotes: 0

xvatar
xvatar

Reputation: 3259

I guess essentially the question is how to get all the parent-leftChild pairs and parent-rightChild pairs of the tree from given preorder and inorder

To get the parent-leftChild pairs, you need to check: 1) if node1 is right after node2 in preorder; 2) if node2 is in front of node1 in inorder

For your example preorder:ABCDE inorder:CBDAE

  • B is right after A in preorder and B is in front of A in inorder, thus B is the left child of A.

  • D is right after C in preorder, but D is also after C in inorder, thus D is not the left child of C

You can use the similar trick to get all parent-rightChild pairs

Upvotes: 2

Antimony
Antimony

Reputation: 39451

To add children to any node, just get the node that you want to add children to and call setLeftChild or setRightChild on it.

Upvotes: 1

Related Questions