Бинарное дерево выражений — это особый вид бинарного дерева, используемого для представления выражений . Два распространенных типа выражений, которые может представлять бинарное дерево выражений, — это алгебраические [1] и булевы . Эти деревья могут представлять выражения, содержащие как унарные , так и бинарные операторы. [1]
Как и любое бинарное дерево, каждый узел бинарного дерева выражений имеет ноль, одного или двух потомков. Эта ограниченная структура упрощает обработку деревьев выражений.
Входные данные в постфиксной нотации: ab + cde + * * Поскольку первые два символа являются операндами, создаются одноузловые деревья, а указатели на них помещаются в стек. Для удобства стек будет расти слева направо.
Следующий символ — «+». Он выталкивает два указателя на деревья, формируется новое дерево, а указатель на него помещается в стек.
Далее считываются c, d и e. Для каждого создается дерево из одного узла, и указатель на соответствующее дерево помещается в стек.
Продолжая, считывается «+», и он объединяет два последних дерева.
Теперь считывается '*'. Последние два указателя дерева удаляются, и формируется новое дерево с '*' в качестве корня.
Наконец, считывается последний символ. Два дерева объединяются, и указатель на последнее дерево остается в стеке. [2]
Деревья алгебраических выражений представляют выражения, содержащие числа , переменные , а также унарные и бинарные операторы. Некоторые из общих операторов: × ( умножение ), ÷ ( деление ), + ( сложение ), − ( вычитание ), ^ ( возведение в степень ) и - ( отрицание ). Операторы содержатся во внутренних узлах дерева, числа и переменные — в листовых узлах . [1] Узлы бинарных операторов имеют два дочерних узла , а унарные операторы имеют один дочерний узел.
Булевы выражения представляются очень похоже на алгебраические выражения, единственное отличие заключается в конкретных значениях и используемых операторах. Булевы выражения используют true и false как постоянные значения, а операторы включают ( AND ), ( OR ), ( NOT ).
