yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->Помеченные деревья и деревья выражений

Алгоритмы структуры данных

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

Часто бывает полезным сопоставить каждому узлу дерева метку (label) или значение, точно так же, как мы в предыдущей главе сопоставляли элементам списков определенные значения. Дерево, у которого узлам сопоставлены метки, называется помеченным деревом. Метка узла — это не имя узла, а значение, которое "хранится" в узле. В некоторых приложениях мы даже будем изменять значение метки, поскольку имя узла сохраняется постоянным. Полезна следующая аналогия: дерево-список, узел-позиция, метка-элемент.

Пример 3.4. На рис. 3.6 показано дерево с метками, представляющее арифметическое выражение (а + b) * (а + с), где n1, ..., n7 — имена узлов (метки на рисунке проставлены рядом с соответствующими узлами). Правила соответствия меток деревьев элементам выражений следующие.

1.    Метка каждого листа соответствует операнду и содержит его значение, например узел n4 представляет операнд а.

2.    Метка каждого внутреннего (родительского) узла соответствует оператору. Предположим, что узел n помечен бинарным оператором θ (например, + или *) и левый сын этого узла соответствует выражению e1, а правый — выражению Е2. Тогда узел п и его сыновья представляют выражение (E1) θ (E2). Можно удалять родителей, если это необходимо.

Например, узел п2 имеет оператор +, а левый и правый сыновья представляют выражения (операнды) а и Ъ соответственно. Поэтому узел п2 представляет (а) + (b), т.е. а + b. Узел /ІІ представляет выражение (а + b) * (а + с), поскольку оператор * является меткой узла n1 выражения а + b и а + с представляются узлами п2 и п3 соответственно.

Часто при обходе деревьев составляется список не имен узлов, а их меток. В случае дерева выражений при прямом упорядочивании получаем известную префиксную форму выражений, где оператор предшествует и левому, и правому операндам. Для точного описания префиксной формы выражений сначала положим, что префиксным выражением одиночного операнда а является сам этот операнд. Далее, префиксная форма для выражения 1) θ 2), где θ — бинарный оператор, имеет вид θР1Р2, здесь pi и Р2префиксные формы для выражений Е1 и Е2. Отметим, что в префиксных формах нет необходимости отделять или выделять отдельные префиксные выражения скобками, так как всегда можно просмотреть префиксное выражение θP1P2 и определить единственным образом p1 как самый короткий префикс выражения Р1Р2.

Например, при прямом упорядочивании узлов (точнее, меток) дерева, показанного на рис. 3.6, получаем префиксное выражение *+ab+ac. Самым коротким корректным префиксом для выражения b+ас будет префиксное выражение узла п2: +ab.

Обратное упорядочивание меток дерева выражений дает так называемое постфиксное (или польское) представление выражений. Выражение θР1Р2 в постфиксной форме имеет вид P1P2θ, где Р1 и Р2 — постфиксные формы для выражений Е1 и Е2 соответственно. При использовании постфиксной формы также нет необходимости в применении скобок, поскольку для любого постфиксного выражения Р1Р2 легко проследить самый короткий суффикс Р2, что и будет корректным составляющим постфиксным выражением. Например, постфиксная форма выражения для дерева на рис. 3.5 имеет вид ab+ac+*. Если записать это выражение как Р1Р2*, то Р2 (т.е. выражение ас+) будет самым коротким суффиксом для ab+ac+ и, следовательно, корректным составляющим постфиксным выражением.

При симметричном обходе дерева выражений получим так называемую инфиксную форму выражения, которая совпадает с привычной "стандартной" формой записи выражений, но также не использует скобок. Для дерева на рис. 3.6 инфиксное выражение запишется как а + b * а + с. Читателю предлагается разработать алгоритм обхода дерева выражений, который бы выдавал инфиксную форму выражения со всеми необходимыми парами скобок.

Вычисление „наследственных" данных

Обход дерева в прямом или обратном порядке позволяет получить данные об отношениях предок-потомок узлов дерева. Пусть функция postorder(n) вычисляет позицию узла п в списке узлов, упорядоченных в обратном порядке. Например, для узлов n2, n4 и n5 дерева, представленного на рис. 3.6, значения этой функции будут 3, 1 и 2 соответственно. Определим также функцию desc(n), значение которой равно числу истинных потомков узла n.

Эти функции позволяют выполнить ряд полезных вычислений. Например, все узлы поддерева с корнем п будут последовательно занимать позиции от postorder(n) - desc(n) до postorder{n) в списке узлов, упорядоченных в обратном порядке. Для того чтобы узел х был потомком узла у, надо, чтобы выполнялись следующие неравенства:

postorder(y) - desc(y) < postorder(x) < postorder(y).

Подобные функции можно определить и для списков узлов, упорядоченных в прямом порядке.

 

34