Какие комбинации до, после и по порядку секвенизации являются уникальными?

28

Мы знаем пост-заказ,

post L(x)     => [x]
post N(x,l,r) => (post l) ++ (post r) ++ [x]

и предварительный заказ

pre L(x)     => [x]
pre N(x,l,r) => [x] ++ (pre l) ++ (pre r)

и в порядке обхода соотв. sequentialisation.

in L(x)     => [x]
in N(x,l,r) => (in l) ++ [x] ++ (in r)

Легко видеть, что ни одно из них не описывает одно дерево однозначно, даже если мы предполагаем парные различные ключи / метки.

Какие комбинации трех могут быть использованы для этой цели, а какие нет?

Положительные ответы должны включать (эффективный) алгоритм для восстановления дерева и доказательство (идею), почему это правильно. Отрицательные ответы должны давать контрпримеры, т.е. разные деревья, которые имеют одинаковое представление.

Рафаэль
источник

Ответы:

16

Во-первых, я предполагаю, что все элементы различны. Никакая последовательность не скажет вам форму дерева с элементами [3,3,3,3,3]. Конечно, можно реконструировать некоторые деревья с дублирующимися элементами; Я не знаю, какие хорошие достаточные условия существуют.

Продолжая получать отрицательные результаты, вы не можете полностью перестроить двоичное дерево только из его последовательностей до и после упорядочивания. [1,2]Предзаказ, [2,1]пост-заказ должен иметь 1в корне, но 2может быть либо левый, либо правый. Если вас не волнует эта неоднозначность, вы можете восстановить дерево по следующему алгоритму:

  • Пусть будет предварительного заказа, а будет предварительного заказа. Мы должны иметь , и это корень дерева.[ y n , , y 1 ] x 1 = y 1[Икс1,...,ИксN][YN,...,Y1]Икс1знак равноY1
  • y 2 x 2 = y 2 [ x 2 , , x n ] [ y n , , y 2 ]Икс2 - самый левый потомок корня, а - самый правый потомок. Если , корневой узел унарный; по и чтобы создать единственное поддерево.Y2Икс2знак равноY2[Икс2,...,ИксN][YN,...,Y2]
  • В противном случае, пусть и будут такими индексами, что и . - это обход по предварительному заказу левого поддерева, - по правому поддереву, и аналогично для обходов после заказа. Левое поддерево имеет элементы , а правое поддерево содержит элементы . Рекурсировать один раз для каждого поддерева. Кстати, этот метод обобщает на деревья с произвольным ветвлением. При произвольном ветвлении выясните размер левого поддерева и обрежьте его элементы из обоих списков, затем повторите, чтобы обрезать второе поддерево слева, и так далее.j x 2 = y i y 2 = x j [ x 2 , , x j - 1 ] [ x j , , x n ] j - 2 = n - i + 1 i - 2 = n - j + 1 J - 2яJИкс2знак равноYяY2знак равноИксJ[Икс2,...,ИксJ-1][ИксJ,...,ИксN]J-2знак равноN-я+1я-2знак равноN-J+1
    J-2

Как уже говорилось, время выполнения равно с наихудшим случаем (в случае с двумя дочерними элементами мы ищем каждый список линейно). Вы можете превратить это в если предварительно обработать списки для построения конечной структуры карты от значений элементов до позиций во входных списках , Также используйте массив или конечную карту для перехода от индексов к значениям; придерживайтесь глобальных индексов, так что рекурсивные вызовы получат целые карты и примут диапазон в качестве аргумента, чтобы знать, на что действовать.Θ ( n 2 ) O ( nО(N2)Θ(N2)О(NLг(N))NLг(N)

С помощью обхода по предварительному заказу и обхода по порядку вы можете перестроить дерево следующим образом:[Икс1,...,ИксN][Z1,...,ZN]

  • Корень является главой обхода предварительного заказа .Икс1
  • Пусть будет индексом таким, что . Тогда является обходом левого потомка по порядку, а является обходом правого потомка. Исходя из количества элементов, является предварительного порядка левого потомка, а - правым потомком. Повторяйте, чтобы построить левое и правое поддеревья.z k = x 1 [ z 1 , , z k - 1 ] [ z k + 1 , , z n ] [ x 2 , , x k ] [ x k + 1 , , x n ]КZКзнак равноИкс1[Z1,...,ZК-1][ZК+1,...,ZN][Икс2,...,ИксК][ИксК+1,...,ИксN]

Опять же, этот алгоритм имеет как указано, и может быть выполнен в если список предварительно обработан в конечную карту от значений до позиций.O ( nО(N2)О(NLг(N))

Пост-заказ плюс заказ, конечно, симметричны.

Жиль "ТАК - перестань быть злым"
источник
Есть ли здесь опечатка: «[1,2] preorder, [1,2] post-order должен иметь 1 в корне, но 2 может быть либо левым, либо правым потомком.» Post-порядок такого Дерево будет [2,1], а не [1,2], независимо от того, является ли 2 левым или правым потомком. Кроме того, вы имеете в виду, что если даны как предварительный заказ, так и почтовый заказ, мы не можем реконструировать дерево, или вы имеете в виду, если нам дан только один из них, то мы не можем восстановить дерево?
CEGRD
@ CEGRD Действительно, заказ был опечаткой. Пример показывает, что вы не можете полностью восстановить дерево в этом случае: вы не можете знать, 2является ли левый или правый дочерний элемент. Это соответствует случаю «одного поддерева» алгоритма восстановления.
Жиль "ТАК - перестань быть злым"
как это изменится, если мы знаем, что это дерево двоичного поиска? для простого случая в вашем примере ([1,2] preorder, [2,1] post-order) мы могли бы определить, что корень равен 1 и что 2 является правильным потомком (потому что 2 больше 1) ... правильно?
fersarr