Главная Промышленная автоматика.

6, 3, 7, 4 и 1. Применяя процедуру INORDER, получим список симметрично упорядоченных узлов этого же дерева: 2, 1, 8, 5, 9, 3, 10, 6, 7 и 4.

При обходе деревьев можно применить следующий полезный прием. Надо нарисовать непрерывный контур вокруг дерева, начиная от корня дерева, рисуя контур против часовой стрелки и поочередно обходя все наружные части дерева. Такой контур вокруг дерева из рис. 3.3 показан на рис. 3.5.


Рис. 3.5. Контур дерева

При прямом упорядочивании узлов надо просто записать их в соответствии с нарисованным контуром. При обратном упорядочивании после записи всех сыновей переходим к их родителю. При симметричном (внутреннем) упорядочивании после записи самого правого листа мы переходим не по ветви в направлении к корню дерева, а к следующему "внутреннему" узлу, который еще не записан. Например, если на рис. 3.5 узлы 2 и 1 уже записаны, то мы как бы перескакиваем "залив" между узлами 2 и 3 и переходим к узлу 8. Отметим, что при любом упорядочивании листья всегда записываются в порядке слева направо, при этом в случае симметричного упорядочивания между сыновьями может быть записан родитель. □

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

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

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

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

Метка каясдого внутреннего (родительского) узла соответствует оператору. Предположим, что узел и помечен бинарным оператором в (например, -i- или *) и левый сын этого узла соответствует выражению Е, а правый - выражению Е. Тогда узел и и его сыновья представляют выражение (Е) 0 (Eg). Можно удалять родителей, если это необходимо.




Рис. 3.6. Дерево выражения с метками

Например, узел щ имеет оператор +, а левый и правый сыновья представляют выражения (операнды) а п Ъ соответственно. Поэтому узел лз представляет (а) + (6), т.е. а + Ь. Узел представляет выражение (а + Ь) * (а + с), поскольку оператор * является меткой узла п-г выражения а + Ь н а + с представляются узлами пз и щ соответственно. □

Часто при обходе деревьев составляется список не имен узлов, а их меток. В случае дерева выражений при прямом упорядочивании получаем известную префиксную форму выражений, где оператор предшествует и левому, и правому операндам. Для точного описания префиксной формы выражений сначала положим, что префиксным выражением одиночного операнда а является сам этот операнд. Далее, префиксная форма для выражения (£i)0 (£2)»где О - бинарный оператор, имеет вид 0PiP2> здесь Pi н Pi - префиксные формы для выражений £i и £2- Отметим, что в префиксных формах нет необходимости отделять или выделять отдельные префиксные выражения скобками, так как всегда можно просмотреть префиксное выражение QP1P2 и определить единственным образом Р как самый короткий префикс выражения Р1Р2.

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

Обратное упорядочивание меток дерева выражений дает так называемое постфиксное (или польское) представление выражений. Выражение QP1P2 в постфиксной форме имеет вид Р\Рф, где Pi vl Р2 - постфиксные формы для выражений Еу и £2 соответственно. При использовании постфиксной формы также нет необходимости в применении скобок, поскольку для любого постфиксного выражения Р1Р2 легко проследить самый короткий суффикс Р2, что и будет корректным составляюшим постфиксным выражением. Например, постфиксная форма выражения для дерева на рис. 3.5 имеет вид айч-асч-*. Если записать это выражение как Р1Р2*, то Р2 (т.е. выражение ас+) будет самым коротким суффиксом для аЬ+ас+ и, следовательно, корректным составляюшим постфиксным выражением.

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

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

Обход дерева в прямом или обратном порядке позволяет получить данные об отношениях предок-потомок узлов дерева. Пусть функция postorderin) вычисляет позицию узла п в списке узлов, упорядоченных в обратном порядке. Например, для уз-



лов Пг, и4 и FEj дерева, представленного на рис. 3.6, значения этой функции будут 3, 1 и 2 соответственно. Определим таюке функцию desc(n), значение которой равно числу истинных потомков узла и.

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

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

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

3.2. Абстрактный тип данных TREE

в главе 2 списки, стеки, очереди и отображения получили трактовку как абстрактные типы данных (АТД). В этой главе рассмотрим деревья как АТД и как структуры данных. Одно из наиболее важных применений деревьев - это использование их при разработке реализаций различных АТД. Например, в главе 5 мы покажем, как можно использовать "дерево двоичного поиска" при реализации АТД, основанных на математической модели множеств. В следующих двух главах будут представлены многочисленные примеры применения деревьев при реализации различных абстрактных типов данных.

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

1. PARENT(n, Т). Эта функция возвращает родителя (parent) узла п в дереве Т. Если и является корнем, который не имеет родителя, то в этом случае возвращается Л. Здесь Л обозначает "нулевой узел" и указывает на то, что мы выходим за пределы дерева.

2. LEFTMOST CHILD(ra, Т). Данная функция возвращает самого левого сына узла и в дереве Т. Если и является листом (и поэтому не имеет сына), то возвращается Л.

3. RIGHT SIBLING(ra, Т). Эта функция возвращает правого брата узла га в дереве Т и значение Л, если такового не существует. Для этого находится родитель р узла га и все сыновья узла р, затем среди этих сыновей находится узел, расположенный непосредственно справа от узла и. Например, для дерева на рис. 3.6 LEFTMOST CHILD(ra2) = "4, RIGHT SIBLING(ra4) = RIGHT SIBLING(ra5) = Л.

4. LABEL(ra, Т). Возвращает метку узла га дерева Т. Для выполнения этой функции требуется, чтобы на узлах дерева были определены метки.

5. CREATEj(t;, Ti, Т2, Ti) - это обпшрное семейство "созидающих" фугжций, которые для кавдого i = О, 1,2, ... создают новый корень г с меткой v и далее для этого корня создает i сыновей, которые становятся корнями поддеревьев Т, Т, Tj. Эти функции возвращают дерево с корнем г. Отметим, что если i = О, то возвращается один узел г, который одновременно является и корнем, и листом.

6. ROOT(r) возвращает узел, являющимся корнем дерева Т. Если Т - пустое дерево, то возвращается Л.

7. MAKENULL(7). Этот оператор делает дерево Т пустым деревом.

Пример 3.5. Напищем рекурсивную PREORDER и нерекурсивную NPREORDER процедуры обхода дерева в прямом порядке и составления соответствующего списка его меток. Предположим, что для узлов определен тип данных node (узел), так же, как и для типа данных TREE (Дерево), причем АТД TREE определен для деревьев с

3.2. АБСТРАКТНЫЙ ТИП ДАННЫХ TREE 83





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 [23] 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0017