Двоичные деревья выражений

Структуры типа двоичных деревьев часто применяются для представления математических выражений.

Например, выражение 2+3 можно описать следующим образом:

Выражение 7+(6*4) представляется следующим образом:

Этот тип деревьев называется деревьями выражений, потому что каждое такое дерево описывает некоторое выражение.

Двоичные деревья, описывающие выражения только с двоичными операциями (двоичные операции – это операции, имеющие два операнда), называются двоичными деревьями выражений.

Двоичные деревья выражений имеют следующие свойства:

1. Каждая листьевая вершина содержит простой операнд, а каждая нелистьевая вершина содержит операцию.

2. Каждое поддерево представляет собой некоторое подвыражение.

3. Левое (или правое) подвыражение должно быть вычислено перед выполнением операции, соответствующей корню поддерева.

Деревья выражений часто используются в компиляторах и интерпретаторах для анализа семантики выражений. Обобщенное его понятие применяется в компиляторах для анализа синтаксиса программ.