Не преобразование выражений, а преобразование из предварительного заказа в заказ (не выражение)

Я не прошу преобразования выражений

преобразование из инфикса в префикс

Я просто спрашиваю, что для BST, если входные данные даны в виде префиксной нотации, то есть обхода предзаказа BST, то как мне преобразовать последовательность значений в инфиксную нотацию, то есть обход порядка следования BST.

                 8
/  \
1    12
\     /
5   9
/   \
4     7
/
6

например, обход предзаказа даст 8 1 5 4 7 6 12 9

Как я могу преобразовать эту последовательность значений (входы)
к выражению обхода по порядку 1 4 5 6 7 8 9 12.

AS в некоторых случаях проще обрабатывать выражения inorder …

0

Решение

С BST:
Префикс: Левое поддерево, узел, правое поддерево.
инфикс: Узел, левое поддерево, правое поддерево.
постфикс: правое поддерево, левое поддерево, узел.

Конверсия зависит от того, как вы пройдете дерево.

0

Другие решения

Позволять

V = вершина

L = левое поддерево

R = правое поддерево

Предзаказ = VLR

Inorder = LVR

Postorder = LRV

(Просто переключите порядок, чтобы исправить, и это то же самое)

Один из способов вернуть их для создания префиксных значений для инфиксных значений — это снова создать двоичное дерево поиска со значениями префиксов и выполнить обход Inorder.

ИЛИ ЖЕ!

Просто сортируй, чувак … (BST всегда сортируется, если ты их раздваиваешь (линия сверху вниз))

0

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector