Построение дерева с обходом в порядке и перед порядком в Python3.x

Я пытаюсь построить дерево, используя обходы предварительного и неупорядоченного (список целых чисел). Вот что у меня есть на данный момент:

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)]

Я считаю этот алгоритм правильным, хотя могу ошибаться.

У меня такой вопрос - в какой момент я вставляю элементы в дерево? У меня есть класс, который справляется с этим, я просто не уверен, куда вставить этот вызов, так как функция будет работать рекурсивно. Приветствуются любые предложения о том, как мне вставлять узлы в дерево.


python algorithm tree tree-traversal
person somebody    schedule 23.04.2014    source источник
comment
какие? Я понимаю отдельные слова, которые вы говорите, но я не понимаю, что вы пытаетесь сделать ... и ваш код не так уж и полезен   -  person Joran Beasley    schedule 24.04.2014
comment
root = preorder[0] это место. Остальное не выглядит правильным.   -  person user58697    schedule 24.04.2014
comment
Я не уверен, куда на самом деле вставить вызов моего класса, который превратит элемент списка в узел.   -  person somebody    schedule 24.04.2014

Ответы (1)


arrow_upward
1
arrow_downward 

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)

что-то такое?

person Joran Beasley    schedule 23.04.2014