Структуры данных и алгоритмы (1021739), страница 21
Текст из файла (страница 21)
Отметим, что в префиксныхформах нет необходимости отделять или выделять отдельные префиксные выражения скобками, так как всегда можно просмотреть префиксное выражение 0PiP2 иопределить единственным образом PI как самый короткий префикс выражения PiP2.Например, при прямом упорядочивании узлов (точнее, меток) дерева, показанногона рис. 3.6, получаем префиксное выражение *+ab+ac. Самым коротким корректнымпрефиксом для выражения +ab+ac будет префиксное выражение узла п2: +ab.Обратное упорядочивание меток дерева выражений дает так называемое постфиксное (или польское) представление выражений.
Выражение 0PjP2 в постфикснойформе имеет вид PiP20, где Рх и Р2 — постфиксные формы для выражений EI и Е2соответственно. При использовании постфиксной формы также нет необходимости вприменении скобок, поскольку для любого постфиксного выражения PtP2 легко проследить самый короткий суффикс Р2, что и будет корректным составляющим постфиксным выражением. Например, постфиксная форма выражения для дерева нарис. 3.5 имеет вид ab+ac+*. Если записать это выражение как PiP2*, то Р2 (т.е. выражение ас+) будет самым коротким суффиксом для ab+ac+ и, следовательно, корректным составляющим постфиксным выражением.При симметричном обходе дерева выражений получим так называемую инфиксную форму выражения, которая совпадает с привычной "стандартной" формой записи выражений, но также не использует скобок. Для дерева на рис.
3.6 инфиксноевыражение запишется как а + Ь * а + с. Читателю предлагается разработать алгоритм обхода дерева выражений, который бы выдавал инфиксную форму выражениясо всеми необходимыми парами скобок.Вычисление „наследственных" данныхОбход дерева в прямом или обратном порядке позволяет получить данные об отношениях предок-потомок узлов дерева. Пусть функция postorder(n) вычисляет позицию узла п в списке узлов, упорядоченных в обратном порядке. Например, для уз82ГЛАВА 3. ДЕРЕВЬЯлов п2, п± и га5 дерева, представленного на рис. 3.6, значения этой функции будут 3,1 и 2 соответственно.
Определим также функцию desc(n), значение которой равночислу истинных потомков узла п.Эти функции позволяют выполнить ряд полезных вычислений. Например, все узлыподдерева с корнем га будут последовательно занимать позиции от postorder(ri) - desc(n)до postorder(n) в списке узлов, упорядоченных в обратном порядке. Для того чтобыузел х был потомком узла у, надо, чтобы выполнялись следующие неравенства:postorderiy) - desc(y) < postorder(x) <, postorderiy).Подобные функции можно определить и для списков узлов, упорядоченных впрямом порядке.3.2. Абстрактный тип данных TREEВ главе 2 списки, стеки, очереди и отображения получили трактовку как абстрактные типы данных (АТД).
В этой главе рассмотрим деревья как АТД и какструктуры данных. Одно из наиболее важных применений деревьев — это использование их при разработке реализаций различных АТД. Например, в главе 5 мы покажем, как можно использовать "дерево двоичного поиска" при реализации АТД, основанных на математической модели множеств.
В следующих двух главах будут представлены многочисленные примеры применения деревьев при реализации различныхабстрактных типов данных.В этом разделе мы представим несколько полезных операторов, выполняемых наддеревьями, и покажем, как использовать эти операторы в различных алгоритмах.Так же, как и в случае списков, можно предложить большой набор операторов, выполняемых над деревьями. Здесь мы рассмотрим следующие операторы.1.PARENT(ra, Т). Эта функция возвращает родителя (parent) узла п в дереве Т.
Если п является корнем, который не имеет родителя, то в этом случае возвращается Л. Здесь Л обозначает "нулевой узел" и указывает на то, что мы выходим запределы дерева.2. LEFTMOST_CHILD(n, Т). Данная функция возвращает самого левого сына узла п вдереве Т. Если п является листом (и поэтому не имеет сына), то возвращается Л.3. RIGHT_SIBLING(ra, Т). Эта функция возвращает правого брата узла га в дереве Ти значение Л, если такового не существует.
Для этого находится родитель р узлага и все сыновья узла р, затем среди этих сыновей находится узел, расположенный непосредственно справа от узла п. Например, для дерева на рис. 3.6LEFTMOST_CHILD(ra2) = п4, RIGHT_SIBLING(ra4) = п5 и RIGHT_SIBLING(n5) = Л.4. LABEL(w, Т). Возвращает метку узла га дерева Т. Для выполнения этой функциитребуется, чтобы на узлах дерева были определены метки.5. CREATED, TI, T2, ..., Tt) — это обширное семейство "созидающих" функций, которые для каждого i = О, 1, 2, ... создают новый корень г с меткой и и далее для этогокорня создает i сыновей, которые становятся корнями поддеревьев Т1? Т2, ....
Tt. Этифункции возвращают дерево с корнем г. Отметим, что если i = О, то возвращаетсяодин узел г, который одновременно является и корнем, и листом.6. ROOT(T) возвращает узел, являющимся корнем дерева Т. Если Т — пустое дерево, то возвращается Л.7. MAKENULL(r). Этот оператор делает дерево Т пустым деревом.Пример 3.5. Напишем рекурсивную PREORDER и нерекурсивную NPREORDERпроцедуры обхода дерева в прямом порядке и составления соответствующего спискаего меток. Предположим, что для узлов определен тип данных node (узел), так же,как и для типа данных TREE (Дерево), причем АТД TREE определен для деревьев с3.2. АБСТРАКТНЫЙ ТИП ДАННЫХ TREE83метками, которые имеют тип данных labeltype (тип метки).
В листинге 3.2 приведенарекурсивная процедура, которая по заданному узлу п создает список в прямом порядке меток поддерева, корнем которого является узел п. Для составления спискавсех узлов дерева Т надо выполнить вызов PREORDER(ROOT(!T)).:.-— :;. .
. -..•"':••".•.. :•:•-"•"./'•'.'•'•••''•''.'•.".•' ••':• '. •'.'•Листинг 3.2. Рекурсивная процедура обхода дерева в прямом порядкеprocedure PREORDER ( n: node );varс: node;beginprint(LABEL(n, T)) ;С: = LEFTMOST_CHILD(n, T) ;while с о Л do beginPREORDER(c) ;C:= RIGHT_SIBLING(c, T)endend; { PREORDER }Теперь напишем нерекурсивную процедуру для печати узлов дерева в прямом порядке. Чтобы совершить обход дерева, используем стек S, чей тип данных STACKуже объявлен как "стек для узлов". Основная идея разрабатываемого алгоритма заключается в том, что, когда мы дошли до узла и, стек хранит путь от корня до этогоузла, причем корень находится на "дне" стека, а узел п — в вершине стека.1Один из подходов к реализации обхода дерева в прямом порядке показан на примере программы NPREORDER в листинге 3.3.
Эта программа выполняет два видаопераций, т.е. может находиться как бы в одном из двух режимов. Операции первоговида (первый режим) осуществляют обход по направлению к потомкам самого левогоеще не проверенного пути дерева до тех пор, пока не встретится лист, при этом выполняется печать узлов этого пути и занесение их в стек.Во втором режиме выполнения программы осуществляется возврат по пройденному пути с поочередным извлечением узлов из стека до тех пор, пока не встретитсяузел, имеющий еще "не описанного" правого брата. Тогда программа опять переходит в первый режим и исследует новый путь, начиная с этого правого брата.Программа начинается в первом режиме с нахождения корня дерева и определения,является ли стек пустым.
В листинге 3.3 показан полный код этой программы. ПЛистинг 3.3. Нерекурсивная процедура обхода дерева в прямом порядкеprocedure NPREORDER ( Т: TREE );varm: node; { переменная для временного хранения узлов }5: STACK; { стек узлов, хранящий путь от корня дородителя TOP(S) текущего узла т }begin { инициализация }MAKENULL(S);т:= ROOT (Г) ;while true doif m <> Л then beginprint(LABEL(т, Т));PUSH(m, S) ;1Можно вернуться к разделу 2.6, где обсуждалась реализация рекурсивных процедур с помощью стека активационных записей.
При рассмотрении листинга 3.2 нетрудно заметить, чтоактивационную запись можно заносить в стек при каждом вызове процедуры PREORDER(n) и,это главное, стек будет содержать актнвационные записи для всех предков узла п.84ГЛАВА 3. ДЕРЕВЬЯ{ исследование самого левого сына узла т }т:= LEFTMOST_CHILD(ra, Т)endelse begin{. завершена проверка пути, содержащегося в стеке }if EMPTY(S) thenreturn;{ исследование правого брата узла,находящегося в вершине стека }л:= RIGHT_SIBLING(TOP(S) , Т);POP(S)endend; { NPREORDER }3.3. Реализация деревьевВ этом разделе мы представим несколько основных реализаций деревьев и обсудим их возможности для поддержки операторов, введенных в разделе 3.2.Представление деревьев с помощью массивовПусть Т — дерево с узлами 1, 2, ..., п.
Возможно, самым простым представлениемдерева Т, поддерживающим оператор PARENT (Родитель), будет линейный массив А,где каждый элемент A[i] является указателем или курсором на родителя узла I. Кореньдерева Т отличается от других узлов тем, что имеет нулевой указатель или указательна самого себя как на родителя. В языке Pascal указатели на элементы массива недопустимы, поэтому мы будем использовать схему с курсорами, тогда A[i] = /, если узел jявляется родителем узла i, и A[i] = О, если узел i является корнем.а.
ДеревоАО83 4 5 61] 1 ] 2 | 2 | 5] 5| 5910б. Курсоры на родителейРис. 3.7. Дерево и курсоры на родителей3.3. РЕАЛИЗАЦИЯ ДЕРЕВЬЕВ85Данное представление использует то свойство деревьев, что каждый узел, отличныйот корня, имеет только одного родителя. Используя это представление, родителя любого узла можно найти за фиксированное время.
Прохождение по любому пути, т.е. переход по узлам от родителя к родителю, можно выполнить за время, пропорциональноеколичеству узлов пути. Для реализации оператора LABEL можно использовать другоймассив L, в котором элемент L\i\ будет хранить метку узла i, либо объявить элементымассива А записями, состоящими из целых чисел (курсоров) и меток.Пример 3.6. На рис. 3.7 показаны дерево и массив А курсоров на родителей этого дерева.
DИспользование указателей или курсоров на родителей не помогает в реализации операторов, требующих информацию о сыновьях. Используя описанное представление, крайне тяжело для данного узла п найти его сыновей или определитьего высоту. Кроме того, в этом случае невозможно определить порядок сыновейузла (т.е. какой сын находится правее или левее другого сына). Поэтому нельзяреализовать операторы, подобные LEFTMOST_CHILD и RIGHTJ3IBLING. Можноввести искусственный порядок нумерации узлов, например нумерацию сыновей ввозрастающем порядке слева направо.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
