Помеченные деревья или деревья выражений

Помеченное дерево – деревья узлы, которые хранят значения. В дереве выражений, каждый внутренний узел не лист хранит не арифметическую операцию (бинарную), а лист является переменной или константой, т.е. аргументом операции.

(а + в)*(а - с), чтобы вычислить это выражение а, в, +, а, с, -, * получим обратный обход или постфиксное (польскую) представление выражения, который используется при вычисление выражения в нем – P1 P2 Ө, где P1,P2 постфикс соответствующего выражения.

Здесь не требуется скобок для вычисления операций, потому что расставлена как к структуре дерева.

+ а в – а с, Ө P1 P2, префиксная форма запись подвыражения.

а + в * в – с, P1 Ө P2 симметричный (внутренний) инфикс, скобки в данном случае нужны.

Примеры решения задач:

Вычислить 5 9 10 * + Перевести из постфикса в префикс 2 4 3 * - 5 4 + +

Пусть E1 и E2 подвыражения арифметического вида E1 Ө E2, причем Е1 соответствие левого поддерева, а Е2 правое поддерево с корнем в узле Ө. Таки образом Ө соответствует арифметической операции бинарного вида, т.е. Е1 и Е2 построен в подобных структурах. Тогда обход этого дерева в прямом порядке, Ө Р1 Р2 соответствует префиксной форме записи арифметического выражения. Здесь Р1 и Р2 префиксные формы записи выражений Е1 и Е2. Скобки в префиксном выражение не требуются, так как всегда можно посмотреть Ө Р1 Р2 слева на право без возврата, чтобы определить самый короткий префикс Р1 как единственный возможный в выражение Р1 Р2 (Ө Р1 Р2 ≡ Р). Аналогично обратный обход записывается в виде Р1 Р2 Ө, где Р1 и Р2 постфиксная форма записи поддеревьев Е1 и Е2, скобки также не требуются, так как с одной стороны двигаясь слева на право в выражениях Р1 и Р2 всегда можно выделить Е1, как самый короткий постфикс. А с другой стороны само дерево выражений, так как сама структура дерева однозначно определяет приоритет операций, а разбирая префиксное или постфиксное выражение можно однозначно реконструировать самом дерево чего нельзя добиться в случае с инфиксной формой записи.