class Node:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
def construct(start, end, preorder, pIndex, dict):
# base case
if start > end:
return None, pIndex
root = Node(preorder[pIndex])
pIndex = pIndex + 1
index = dict[root.data]
root.left, pIndex = construct(start, index - 1, preorder, pIndex, dict)
root.right, pIndex = construct(index + 1, end, preorder, pIndex, dict)
return root, pIndex
def constructTree(inorder, preorder):
dict = {}
for i, e in enumerate(inorder):
dict[e] = i
pIndex = 0
return construct(0, len(inorder) - 1, preorder, pIndex, dict)[0]
if __name__ == '__main__':
inorder = [4, 2, 1, 7, 5, 8, 3, 6]
preorder = [1, 2, 4, 3, 5, 7, 8, 6]
root = constructTree(inorder, preorder)
print("The inorder traversal is ", end='')
inorderTraversal(root)
preorderTraversal(root)
Этот код строит дерево с обходом в прямом и обратном порядке. Как я могу изменить этот код, чтобы он работал для предварительного заказа и предварительного заказа? Думаю, мне просто нужно изменить construct()
и создать constructPreOrderInOrderTree()
и constructPreOrderPostOrderTree()
аналогичным образом.
ИЗМЕНИТЬ
Предположим, у меня есть inorder=[3, 7, 1, 10, 9, 5, 8, 6, 4, 2]
и postorder = [3, 7, 10, 9, 1, 8, 4, 6, 2, 5]
. construct()
сделал бы это для предварительного заказа, но он не адаптирован для этого примера. Поэтому мне нужна версия этой функции, которая работала бы как с порядком-после заказа, так и с порядком-предзаказом.
inorder-preorder
иpreorder-postorder
иinorder-postorder
? Я могу понять, что означают просто inorder или preorder или postorder, но не вместе. - person Arty   schedule 12.04.2021inorder=[3, 7, 1, 10, 9, 5, 8, 6, 4, 2]
, вы не сможете полностью перестроить бинарное дерево. Вам понадобится что-то еще, чтобы полностью построить двоичное дерево.inorder = [4, 2, 1, 7, 5, 8, 3, 6]
иpreorder = [1, 2, 4, 3, 5, 7, 8, 6]
будут генерировать двоичное дерево из этого вопроса: stackoverflow.com/questions/67059333/ - person Robert   schedule 12.04.2021preorder-postorder
вариант задачи разрешим? Вы сами придумали эту задачу или она является частью набора данных о практических задачах geeksforgeeks? Можете указать ссылку наpreorder-postorder
описание проблемы на сайте GeeksForGeeks? - person Arty   schedule 12.04.2021