当前位置: 动力学知识库 > 问答 > 编程问答 >

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

问题描述:

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.

网友答案:
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?

分享给朋友:
您可能感兴趣的文章:
随机阅读: