в основном дерево, которое не является бинарным деревом, может быть пройдено в двух порядках: предзаказ (перечисление внутренних узлов перед висящими на нем поддеревьями) и поступорядочение (перечисление внутренних узлов после висящих на нем поддеревьев). Я полагаю, что в вашей задаче «снизу вверх» - это порядок, а «сверху вниз» - порядок.
Предположим далее, что все объекты могут быть отделены друг от друга, т.е. они имеют разные значения или указатели. Если все объекты идентичны, т. Е. Все являются идентичными состояниями, вы не можете определить форму дерева только из списков обхода, потому что они будут выглядеть одинаково.
Теперь дело в том, что если у него есть дерево T и списки узлов, сгенерированные для него по предварительному заказу и после заказа, то ROOT этого дерева является ПЕРВЫМ узлом в списке предварительного заказа и ЛАСТНЫМ узлом в списке почтового заказа. Это дает вам следующий метод реконструкции:
У вас есть два списка: списки пройденных узлов по предварительному и после заказа. Назовите эти R (pRe) и O (pOst).
- Первым элементом R является корневой узел. Удалить его из R
- Удалить последний элемент из O и проверить, что это тот же корневой узел (должен быть)
- Теперь проверьте первый элемент R, это корень самого левого поддерева
- Найти тот же узел из O; скажем, это k -й узел на O
- Теперь самое левое поддерево имеет k узлов; возьмите первые k узлов из обоих списков R и O и рекурсивно выполните этот алгоритм , чтобы восстановить самое левое поддерево
- Продолжите с оставшейся частью R и O, повторяя это, чтобы восстановить оставшиеся поддеревья корневого узла
Псевдокод - рекурсивная процедура, которая возвращает дерево. Входные данные: два списка обхода r = предварительный заказ, o = почтовый заказ
def mktree(r, o):
l = len(r)
assert l == len(o)
root = r[0]
assert root == o[l - 1]
if l == 1:
return mknode(root)
else:
myroot = mknode(root)
r = r[1:l] # sublist that excludes first element
o = o[0:l-1] # sublist that excludes last element
while len(r) > 0: # iterate and construct subtrees
first = r[0]
lim = -1
for i in 0..l - 1:
if o[i] == first:
lim = i + 1
break
assert lim != -1
myroot.add_rightmost_child(mktree(r[0:lim], o[0:lim])
r = r[lim:len(r)] # sublist from lim until end of list
o = o[lim:len(o)] # sublist from lim until end of list
return myroot
Вот пример того, как это работает:
Оригинальное дерево:
1
/ | \
2 3 4
/ / \
5 6 7
Обход по предварительному заказу («сначала сверху вниз»): 1 2 5 3 4 6 7
Обращение по почтовому заказу («снизу вверх»): 5 2 3 6 7 4 1
Алгоритм выполнения:
mktree(1253467, 5236741)
myroot = 1
r = 253467, o = 523674
loc = 1 (location of '2' in o)
mktree(25, 52)
myroot = 2
mktree(5, 5) -> returns singleton tree 5
list exhausted -> returns tree 2[5] (5 only child of 2)
add 2[5] to myroot as right child, tree at myroot 1[2[5]]
r = 3467, o = 3674 (stripped away "25" that was processed)
loc = 0 (location of '3' in o)
mktree(3, 3) returns singleton tree 3
add 3 to myroot as right child, tree at myroot 1[2[5], 3]
r = 467, o = 674 (stripped away "3" that was processed)
loc = 2 (location of '4' in o)
mktree(467, 674)
myroot = 4
r = 67, o = 67
(recursive calls return first singleton 6, then 7)
returns tree 4[6,7]
add 4[6,7] to myroot as right child, tree at myroot 1[2[5],3,4[6,7]]
list exhausted, return tree
В результате оригинальное дерево было реконструировано.
Для справки, здесь определение предзаказа и прохождения порядка в псевдокоде:
def preorder(t):
l = [root_node(t)] # BEFORE recursion = PREorder
for c in t.children(): # in left to right order
l.append(preorder(c))
return l
def postorder(t):
l = []
for c in t.children(): # in left to right order
l.append(postorder(c))
l.append(root_node(t)) # AFTER recursion = POSTorder
return l