Я не прошу преобразования выражений
преобразование из инфикса в префикс
Я просто спрашиваю, что для 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 …
С BST:
Префикс: Левое поддерево, узел, правое поддерево.
инфикс: Узел, левое поддерево, правое поддерево.
постфикс: правое поддерево, левое поддерево, узел.
Конверсия зависит от того, как вы пройдете дерево.
Позволять
V = вершина
L = левое поддерево
R = правое поддерево
Предзаказ = VLR
Inorder = LVR
Postorder = LRV
(Просто переключите порядок, чтобы исправить, и это то же самое)
Один из способов вернуть их для создания префиксных значений для инфиксных значений — это снова создать двоичное дерево поиска со значениями префиксов и выполнить обход Inorder.
ИЛИ ЖЕ!
Просто сортируй, чувак … (BST всегда сортируется, если ты их раздваиваешь (линия сверху вниз))