Создание двоичного дерева из двух выходных данных

Question

Это домашняя работа, но по какой-то причине она не позволяет мне добавлять тег домашней работы.

Нам была назначена лаборатория для структур данных, в которой последний вопрос попросил нас найти двоичное дерево, которое получило бы следующие выходные данные из данных методов обхода:

LRN: 12, 9, 4, 7, 1, 14, 8, 13, 10, 15, 11, 2, 5, 16, 6, 3

а также

LNR: 12, 3, 4, 9, 8, 1, 7, 14, 6, 13, 10, 16, 5, 15, 2, 11

Я определил следующее о дереве:

Корневой узел - 3. Корневой узел - левый дочерний элемент, и только левый дочерний элемент дерева - 12. Корневой узел - правый дочерний элемент - 6. Самый дальний правый узел - 5.

К сожалению, я застрял в том, как поступить. Любые советы будут с благодарностью.

Answer 1

Из пост-заказа (LRN) мы знаем, что последний элемент является корнем. Мы можем найти корень по порядку (LNR). Затем мы можем идентифицировать левое и правое поддеревья корня по порядку.

Используя длину левого поддерева, мы можем определить левое и правое поддеревья в массиве после заказа. Рекурсивно, мы можем построить дерево.

Проверьте эту ссылку.