Вам дан обход дерева по предварительному заказу, который строится следующим образом: output, traverse left, traverse right.
Поскольку прохождение после заказа происходит из BST, вы можете вывести прохождение в порядке (перемещение влево, выход, перемещение вправо) из прохождения после заказа, отсортировав числа. В вашем примере обход в порядке: 1, 2, 3, 4, 6, 7, 9, 10, 11.
Из двух обходов мы можем затем построить оригинальное дерево. Давайте для этого воспользуемся более простым примером:
- Предварительный заказ: 2, 1, 4, 3
- В заказе: 1, 2, 3, 4
Обход по предварительному заказу дает нам корень дерева как 2. Обход по порядку говорит нам, что 1 попадает в левое поддерево, а 3, 4 - в правое поддерево. Структура левого поддерева тривиальна, так как содержит один элемент. Обход предварительного порядка правого поддерева определяется путем извлечения порядка элементов в этом поддереве из исходного обхода предварительного порядка: 4, 3. Из этого мы знаем, что корень правого поддерева равен 4, и из упорядоченного обхода (3, 4) мы знаем, что 3 попадает в левое поддерево. Наше конечное дерево выглядит так:
2
/ \
1 4
/
3
Используя древовидную структуру, мы можем получить обход по порядку, пройдя по дереву: ход влево, ход вправо, вывод. Для этого примера обход после заказа составляет 1, 3, 4, 2.
Для обобщения алгоритма:
- Первым элементом в обходе предварительного заказа является корень дерева. Элементы меньше корня образуют левое поддерево. Элементы больше корня образуют правильное поддерево.
- Найдите структуру левого и правого поддеревьев, используя шаг 1 с обходом предварительного заказа, который состоит из элементов, которые мы разработали, чтобы поместить в это поддерево в том порядке, в котором они появляются в исходном предварительном порядке. ВТП.
- Пройдите по результирующему дереву в последующем порядке, чтобы получить обход по порядку, связанный с данным обходом по предварительному заказу.
Используя вышеприведенный алгоритм, прохождение после заказа, связанное с прохождением предварительного заказа в вопросе: 1, 3, 4, 2, 9, 11, 10, 7, 6. Как добраться, осталось в качестве упражнения .