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:
root = preorder # 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.
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?