Нарисуйте бинарное дерево с данными "ATTA" в качестве обхода по порядку и порядку

Question

Меня попросили нарисовать бинарное дерево поиска, которое и в порядке, и в порядке прохождения заказа обрабатывают узлы в порядке "ATTA", Я пробовал много разных способов, но в итоге он работает только для одного из методов обхода.

Answer 1

Я верю, что вы просто говорите о обычном двоичном дереве, потому что создать такое двоичное дерево поиска невозможно.

Учитывая, что почтовый заказ заканчивается Aмы знаем, что корень должен быть A,

Учитывая, что у нас есть только 2 Aв порядке, а корень Aмы знаем, что левые или правые поддеревья корня пусты.

Учитывая, что второй последний узел в пост-заказе является Tмы знаем, что корень ребенка должен быть T,

Отсюда мы можем просто проверить оставшиеся 4 возможности:

               A        A    A        A
              /        /      \        \
             T        T        T        T
            / \      / \      / \      / \
           A   T    T   A    A   T    T   A

Inorder     ATTA     TTAA     ATAT     ATTA
Postorder   ATTA     TATA     ATTA     TATA

Так что единственная возможность:

    A
   /
  T
 / \
A   T

... и это не бинарное дерево поиска.