Помеченные деревья и деревья выражений
Часто бывает полезным сопоставить каждому узлу дерева метку или значение. Дерево, у которого узлам сопоставлены метки, называется помеченным деревом. Метка узла – это значение, которое «хранится» в узле. Полезна следующая аналогия: дерево – список, узел – позиция, метка – элемент. Рассмотрим пример дерева с метками, представляющее арифметическое выражение (a + b)*(a + c), где n1, n2, …, n7 – имена узлов, а метки проставлены рядом с соответствующими узлами. Правила соответствия меток деревьев элементам выражений следующие: Метка каждого листа соответствует операнду и содержит его значение; Метка каждого внутреннего (родительского) узла соответствует оператору.
Часто при обходе деревьев составляется список не имен узлов, а их меток. В случае дерева выражений при прямом обходе получим известную префиксную форму записи выражения, где оператор предшествует обоим операндам. В нашем примере мы получим префиксное выражение вида: *+ ab + ac. Обратный обход меток дерева дает постфиксное представление выражения (польскую запись). Обратный обход нашего дерева даст нам следующую запись выражения: ab + ac +*. Следует учесть, что префиксная и постфиксная запись выражения не требует скобок. При симметричном обходе мы получим обычную инфиксную запись выражения: a + b * a + c. Правда для инфиксной записи выражений характерно заключение в скобки: (a + b)*(a + c).
|
