Во-первых, я предполагаю, что все элементы различны. Никакая последовательность не скажет вам форму дерева с элементами [3,3,3,3,3]
. Конечно, можно реконструировать некоторые деревья с дублирующимися элементами; Я не знаю, какие хорошие достаточные условия существуют.
Продолжая получать отрицательные результаты, вы не можете полностью перестроить двоичное дерево только из его последовательностей до и после упорядочивания. [1,2]
Предзаказ, [2,1]
пост-заказ должен иметь 1
в корне, но 2
может быть либо левый, либо правый. Если вас не волнует эта неоднозначность, вы можете восстановить дерево по следующему алгоритму:
- Пусть будет предварительного заказа, а будет предварительного заказа. Мы должны иметь , и это корень дерева.[ y n , … , y 1 ] x 1 = y 1[ х1, … , ХN][ уN, ... , у1]Икс1= у1
- y 2 x 2 = y 2 [ x 2 , … , x n ] [ y n , … , y 2 ]Икс2 - самый левый потомок корня, а - самый правый потомок. Если , корневой узел унарный; по и чтобы создать единственное поддерево.Y2Икс2= у2[ х2, … , ХN][ уN, ... , у2]
- В противном случае, пусть и будут такими индексами, что и . - это обход по предварительному заказу левого поддерева, - по правому поддереву, и аналогично для обходов после заказа. Левое поддерево имеет элементы , а правое поддерево содержит элементы . Рекурсировать один раз для каждого поддерева.
Кстати, этот метод обобщает на деревья с произвольным ветвлением. При произвольном ветвлении выясните размер левого поддерева и обрежьте его элементы из обоих списков, затем повторите, чтобы обрезать второе поддерево слева, и так далее.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= уяY2= хJ[ х2, … , ХJ - 1][ хJ,… , ХN]j - 2 = n - i + 1i - 2 = n - j + 1
J - 2
Как уже говорилось, время выполнения равно с наихудшим случаем (в случае с двумя дочерними элементами мы ищем каждый список линейно). Вы можете превратить это в если предварительно обработать списки для построения конечной структуры карты от значений элементов до позиций во входных списках , Также используйте массив или конечную карту для перехода от индексов к значениям; придерживайтесь глобальных индексов, так что рекурсивные вызовы получат целые карты и примут диапазон в качестве аргумента, чтобы знать, на что действовать.Θ ( n 2 ) O ( nO ( n2)Θ ( н2)O ( nl g ( n ) )NL g (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 ( nO ( n2)O ( nl g ( n ) )
Пост-заказ плюс заказ, конечно, симметричны.
2
является ли левый или правый дочерний элемент. Это соответствует случаю «одного поддерева» алгоритма восстановления.