Представление алгебраических выражений бинарными деревьями

Любое алгебраическое выражение, которое содержит переменные, константы, знаки операций и скобки можно представить в виде бинарного дерева, в котором знак операции помещается в корне, первый операнд — в левом поддереве, а второй операнд — в правом. Скобки при этом опускаются. В результате все константы и переменные окажутся в листьях, а знаки операций — во внутренних вершинах. БД алгебраического выражения a + 5 * b * (3 + c * d) представлено на рис.28.

 

       
 
   
 

 


Рис.28. БД алгебраического выражения a+5*b*(3+c*d)

 

Если выполнить обход БД (рис.28) в прямом порядке, то получим прямую польскую запись (ППЗ) алгебраического выражения:

+ a * * 5 b + 3 * c d

Используя ППЗ можно сформировать БД алгебраического выражения.