Определить структурную эквивалентность БСТ со стандартным обходом

Можно ли решить структурную эквивалентность двух бинарных деревьев поиска только с результатами обходов, до порядка, в порядке и после порядка. Предположим, что у меня есть только результирующие массивы всех обходов. Я знаю, что в порядке обхода один, не могу помочь. Но, я не мог визуализировать для других результатов обхода. Я понимаю, что BFS помогает. Я хочу знать, для предварительного и последующего прохождения заказа. И если возможно, пожалуйста, разместите любые ссылки на это.

2 3
algorithm data-structures search catalan

2 ответа:

Ответ таков: Вы можете восстановить бинарное дерево поиска из его предварительного обхода порядка .

Я не уверен, что у вас есть математическое образование, поэтому, пожалуйста, спросите, нужно ли вам больше объяснений. Для простоты я предполагаю, что узел помечен целым числом 1,2... n, где n-номер узла. Тогда предварительный обход дерева t дает вам перестановку [n] = {1,2,...,n}, которая имеет определенное свойство: каждый раз, когда у вас есть буква b в вашей перестановке, вы не могу найти две последовательные буквы ca после b в перестановке, такой что a<b<c. Такая перестановка, как говорят, избегает шаблона b-ac (подставка для произвольного числа букв).

Например, 4 2 1 3 избегает b-ac, тогда как 3 1 4 2 этого не делает, потому что 3 - 4 2.

Это фактически эквивалентность: перестановка - это предварительное чтение дерева, если оно избегает b-ac.

Известно, что существует столько же деревьев размера n, сколько перестановок, избегающих b-ac так что это биекция. Их число известно как каталонское число. Вы, вероятно, можете найти это упражнение в книге Стэнли "перечислительная комбинаторика".

Вот более алгоритмическое объяснение : 

RecTree: Recovering a tree from is Pre-order traversal:

input: list l
output: tree t

b <- l[0]
find an index i such that 
   - for 1<=j<=i then l[j] < b and
   - for i<j<=n  then l[j] > b
if there isn't exists such an index return Failure
else return Node(key=b, RecTree(l[1..i]), RecTree(l[i+1..n]))

Как следствие

Два бинарных дерева поиска равны тогда и только тогда, когда они имеют одинаковый предварительный порядок обхода

Есть ли в этом смысл для вас ?

Еще несколько ссылок

3

В BST вы можете пойти левым ребенком (L), правым ребенком (R) или вверх (U). Затем обход может быть описан строкой над {L, R, U}, например. "ЛЛУРУУРЛУРУУ". Для BST с эквивалентными структурами эти строки будут идентичны.

0