Building a Tree with inorder and preorder traversal in Python3.x

Question

I am trying to build a tree using the preorder and inorder traversals (list of ints). Here is what I have so far:

def build(preorder, inorder, heap): # Builds tree with the inorder and preorder traversal if len(preorder) == 0: return None root = preorder[0] # Root is first item in preorder k = root left_count = inorder[(k-1)] # Number of items in left sub-tree left_inorder = inorder[0:left_count] left_preorder = preorder[1:1+left_count] right_inorder = inorder[1+left_count:] right_preorder = preorder[1+left_count:] return [root, build(left_preorder, left_inorder), build(right_preorder, right_inorder)]

I believe this algorithm is correct, although I could be wrong.

My question is this - at what point do I insert the items into the tree? I have a class written to handle this, I'm just not sure where to insert this call, as the function will operate recursively. Any suggestions for how I should insert the nodes into the tree would be appreciated.

what? I understand the individual words you are saying but I dont understand what you are trying to do ... and your code is not all that enlightening — Joran Beasley
– Joran Beasley, Commented Apr 23, 2014 at 23:02
root = preorder[0] is the place. The rest doesn't look right. — user58697
– user58697, Commented Apr 23, 2014 at 23:07
I'm not sure where to actually insert the call to my class which will make the list item into a node. — somebody
– somebody, Commented Apr 23, 2014 at 23:10

Joran Beasley · Accepted Answer · 2014-04-23 23:11:10Z

class heap: def __init__(self,the_heap): self.heap = the_heap def getChildren(self,value): n = self.heap.index(value) return self.heap[2*n+1],self.heap[2*n+2] # i think ... def getParent(self,value): n = self.heap.index(value) if n == 0: return None return self.heap[math.floor(n-1/2.0) ] # i think ... def traverse(self): #do your traversal here just visit each node in the order you want pass the_heap = heap(range(100)) print the_heap.getChildren(2) print the_heap.getParent(6)

something like that?

Collectives™ on Stack Overflow

Building a Tree with inorder and preorder traversal in Python3.x

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related