Пусть у меня есть какое-нибудь выражение как 2*3/(2-1) +5*(4-1). Это инфиксная запись. Конечно, я могу построить для этого выражения дерево, которое вы видите на картинке. введите здесь описание изображения
Затем запишем это выражение в постфиксной и префиксной формах. Постфикс: 2 3 * 2 1 - / 5 4 1 - * + Префикс: + / * 2 3 - 2 1 * 5 - 4 1
И вопрос: дерево для вышеперечисленных выражений будет таким же? Если нет, то как его построить?
И вопрос: дерево для вышеперечисленных выражений будет таким же?
Да, это одно и то же дерево - разные обозначения представляют один и тот же расчет.
Различные способы записи выражения соответствуют разным обходам одного и того же дерева:
(предварительный заказ: F, B, A, D, C, E, G, I, H)
(по порядку: A, B, C, D, E, F, G, H, I)
(после заказа: A, C, E, D, B, H, I, G, F)
Вот примерный набросок построения дерева из префиксного представления (представьте префиксную нотацию как поток чисел и операторов):
preocedure buildTree(prefix):
c := first item of prefix
if c is a number then
return a tree node containing the number
else
create a tree node t with c (an operator in this case)
t.left := buildTree(rest of prefix)
t.right := buildTree(rest of prefix)
return t
Вы должны вызвать этот метод с префиксным представлением дерева. Метод рекурсивно построит из него поддеревья.
Вы также можете написать аналогичный метод для построения дерева из постфиксного представления. Вам нужно будет настроить этот алгоритм, чтобы начать с правого конца и сначала построить правильное поддерево.
Существует множество ресурсов о том, как построить дерево выражений. Здесь wiki есть очень хорошая ссылка.
Идея состоит в том, что при повторении каждого символа, например, постфиксного выражения.
Если символ является операндом, вы помещаете его в стек
Если символ является оператором, то вы извлекаете два элемента из стека и делаете их потомками текущего оператора, затем вы помещаете оператор в стек.
После завершения цикла вы получите единственный элемент в стеке в качестве корня дерева.
