Структуры данных и алгоритмы (1021739), страница 20
Текст из файла (страница 20)
Вэтом дереве п будет корнем, a Tlt T2, ..., Tk — поддеревьями этого корня. Узлы/»!,' /12. • ••>пи называются сыновьями узла га.Часто в это определение включают понятие нулевого дерева, т.е. "дерева" без узлов, такое дерево мы будем обозначать символом Л.Пример 3.1. Рассмотрим оглавление книги, схематически представленное нарис.
3.1, а. Это оглавление является деревом, которое в другой форме показано нарис. 3.1, б. Отношение родитель-сын отображается в виде линии. Деревья обычно рисуются сверху вниз, как на рис. 3.1, б, так, что родители располагаются выше "детей".КнигаГл.1Р.1.1Р. 1.2Гл.2Р.2.1Р.2.1.1Р.2.1.2Р.2.2Р2 3Гл.ЗКнига_Гл.1Гл.2Р.2.1.1Р.2.1.2Рис.
3.1. Оглавление книги и его представление в виде дерева•:"'-:•'.;••••'••;:- . • . ,Гл.ЗКорнем этого дерева является узел Книга, который имеет три поддерева соответственно с корнями Гл.1, Гл.2 и Гл.З. Эти отношения показаны линиями, идущими изкорня Книга к узлам Гл.1, Гл.2 и Гл.З. Узел Книга является родителем узлов Гл../,Гл.2 и Гл.З, а эти три узла — сыновьями узла Книга.Третье поддерево, с корнем Гл.З, состоит из одного узла, остальные два поддереваимеют нетривиальную структуру. Например, поддерево с корнем Гл.2 в свою очередьимеет три поддерева, которые соответствуют разделам книги Р.2.1, Р.2.2 и Р.2.3; последние два поддерева имеют по одному узлу, в то время как первое имеет два поддерева, соответствующие подразделам книги Р.2.1.1 и Р.2.1.2. ППример 3.1 показывает типичные данные, для которых наилучшим представлением будут деревья.
В этом примере родительские отношения устанавливают подчиненность глав и разделов: родительский узел связан с узлами сыновей (и указываетна них), как узел Книга подчиняет себе узлы Гл.1, Гл.2 и Гл.З. В этой книге вывстретите много различных отношений, которые можно представить с помощью родительских отношений и подчиненности в виде деревьев.Путем из узла »i в узел п/, называется последовательность узлов n l t n2, ..., nt,где для всех i, I < i < k, узел л( является родителем узла TI,-+I. Длиной пути называется число, на единицу меньшее числа узлов, составляющих этот путь.
Таким образом, путем нулевой длины будет путь из любого узла к самому себе. На рис. 3.1 путем длины 2 будет, например, путь от узла Гл.2 к узлу Р.2.1.2.Если существует путь из узла о в ft, то в этом случае узел а называется предкомузла Ь, а узел Ь — потомком узла а. Например, на рис. 3.1 предками узла Р.2.1 будут следующие узлы: сам узел Р.2.1 и узлы Гл.2 и Книга, тогда как потомками этогоузла являются опять сам узел Р.2.1 и узлы Р.2.1.1 и Р.2.1.2. Отметим, что любой узелодновременно является и предком, и потомком самого себя.Предок или потомок узла, не являющийся таковым самого себя, называется истинным предком или истинным потомком соответственно.
В дереве только кореньне имеет истинного предка. Узел, не имеющий истинных потомков, называется листом. Теперь поддерево какого-либо дерева можно определить как узел (корень поддерева) вместе со всеми его потомками.Высотой узла дерева называется длина самого длинного пути из этого узла докакого-либо листа. На рис.3.1 высота узла Гл.1 равна 1, узла Гл.2 — 2, а узла Гл.З —0. Высота дерева совпадает с высотой корня. Глубина узла определяется как длинапути (он единственный) от корня до этого узла.Порядок узловСыновья узла обычно упорядочиваются слева направо.
Поэтому два дерева на рис.3.2 различны, так как порядок сыновей узла а различен. Если порядок сыновей игнорируется, то такое дерево называется неупорядоченным, в противном случае деревоназывается упорядоченным.Рис. 3.2. Два различных упорядоченныхдереваУпорядочивание слева направо сыновей ("родных детей" одного узла) можно использовать для сопоставления узлов, которые не связаны отношениями предкипотомки. Соответствующее правило звучит следующим образом: если узлы а и Ь яв78ГЛАВА 3. ДЕРЕВЬЯляются сыновьями одного родителя и узел а лежит слева от узла Ь, то все потомкиузла а будут находиться слева от любых потомков узла Ъ.Пример 3.2.
Рассмотрим дерево на рис. 3.3. Узел 8 расположен справа от узла 2,слева от узлов 9, 6, 10, 4 и 7, и не имеет отношений справа-слева относительно предков 1, 3 и 5.Рис. 3.3. ДеревоСуществует простое правило, позволяющее определить, какие узлы расположеныслева от данного узла га, а какие — справа. Для этого надо прочертить путь от корнядерева до узла га. Тогда все узлы и их потомки, расположенные слева от этого пути,будут находиться слева от узла п, и, аналогично, все узлы и их потомки, расположенные справа от этого пути, будут находиться справа от узла п. DПрямой, обратный и симметричный обходы дереваСуществует несколько способов обхода (прохождения) всех узлов дерева1.
Тринаиболее часто используемых способа обхода дерева называются обход в прямом порядке, обход в обратном порядке и обход во внутреннем порядке (последний вид обхода также часто называют симметричным обходом, мы будем использовать оба этихназвания как синонимы). Все три способа обхода рекурсивно можно определить следующим образом.• Если дерево Т является нулевым деревом, то в список обхода заносится пустаязапись.• Если дерево Т состоит из одного узла, то в список обхода записывается этот узел.• Далее, пусть Т — дерево с корнем п и поддеревьями Т\, Т2, ..-, Tt, как показанона рис. 3.4. Тогда для различных способов обхода имеем следующее.Рис. 3.4.
Дерево Т1Обход узлов дерева равнозначен упорядочиванию по какому-либо правилу этих узлов. Поэтому в данном разделе мы будем использовать слова "обход узлов" и "упорядочивание узлов"как синонимы. — Прим. ред.3.1. ОСНОВНАЯ ТЕРМИНОЛОГИЯ1.При прохождении в прямом порядке (т.е. при прямом упорядочивании) узлов дерева Т сначала посещается корень п, затем узлы поддерева Т\, далее все узлыподдерева Т2, и т.д. Последними посещаются узлы поддерева Tk.2. При симметричном обходе узлов дерева Т сначала посещаются в симметричномпорядке все узлы поддерева Т\, далее корень п, затем последовательно в симметричном порядке все узлы поддеревьев Т2, ••., Т/,.3., Во время обхода в обратном порядке сначала посещаются в обратном порядкевсе узлы поддерева Tlt затем последовательно посещаются все узлы поддеревьевТ2, ..., Tk, также в обратном порядке, последним посещается корень п.В листинге 3.1,а показан набросок процедуры PREORDER (Прямое упорядочивание), составляющей список узлов дерева при обходе его в прямом порядке.
Чтобы изэтой процедуры сделать процедуру, выполняющую обход дерева в обратном порядке,надо просто поменять местами строки (1) и (2). В листинге 3.1,6 представлен набросок процедуры INORDER (Внутреннее упорядочивание). В этих процедурах производится соответствующее упорядочивание деревьев путем вызова соответствующихпроцедур к корню дерева.Листинг 3.1. Рекурсивные процедуры обхода деревьева. Процедура PREORDERprocedure PREORDER ( л: узел ) ;begin(1)занести в список обхода узел л;(2)for для каждого сына с узла л в порядке слева направо doend;{PREORDER(с)PREORDER }б. Процедура INORDERprocedure INORDER ( л: узел ) ;beginif л — лист thenзанести в список обхода узел л;else beginINORDER(самый левый сын узла л ) ;занести в список обхода узел л;for для каждого сына с узла п, исключая самый левый,в порядке слева направо doINORDER(с)endend; { INORDER }Пример 3.3.
Сделаем обход дерева, показанного на рис. 3.3, в прямом порядке.Сначала запишем (посетим) узел 1, затем вызовем процедуру PREORDER для обхода первого поддерева с корнем 2. Это поддерево состоит из одного узла, котороемы и записываем. Далее обходим второе поддерево, выходящее из корня 1, этоподдерево имеет корень 3. Записываем узел 3 и вызываем процедуру PREORDERдля обхода первого поддерева, выходящего из узла 3.
В результате получим списокузлов 5, 8 и 9 (именно в таком порядке). Продолжая этот процесс, в конце мы получим полный список узлов, посещаемых при прохождении в прямом порядке исходного дерева: 1, 2, 3, 5, 8, 9, 6, 10, 4 и 7.Подобным образом, предварительно преобразовав процедуру PREORDER в процедуру, выполняющую обход в обратном порядке (как указано выше), можно получитьобратное упорядочивание узлов дерева из рис. 3.3 в следующем виде: 2, 8, 9, 5, 10,80ГЛАВА 3. ДЕРЕВЬЯ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 показано дерево с метками, представляющее арифметическое выражение (а + Ь) * (а + с), где п\, ..., Пу — имена узлов (метки на рисунке проставлены рядом с соответствующими узлами).
Правила соответствия меток деревьевэлементам выражений следующие.1.2.Метка каждого листа соответствует операнду и содержит его значение, напримерузел л4 представляет операнд а.Метка каждого внутреннего (родительского) узла соответствует оператору. Предположим, что узел п помечен бинарным оператором в (например, + или *) и левый сын этого узла соответствует выражению Ег, а правый — выражению Е2.Тогда узел п и его сыновья представляют выражение (Ег) 9 (Е2). Можно удалятьродителей, если это необходимо.3.1. ОСНОВНАЯ ТЕРМИНОЛОГИЯ81Рис. 3.6. Дерево выражения с меткамиНапример, узел п2 имеет оператор +, а левый и правый сыновья представляютвыражения (операнды) а и Ъ соответственно. Поэтому узел пг представляет (а) + (6),т.е. а + Ь.
Узел n t представляет выражение (а + Ь) * (а + с), поскольку оператор *является меткой узла n l t выражения а + Ь и а + с представляются узлами п2 и п3 соответственно. ПЧасто при обходе деревьев составляется список не имен узлов, а их меток. В случае дерева выражений при прямом упорядочивании получаем известную префикснуюформу выражений, где оператор предшествует и левому, и правому операндам. Дляточного описания префиксной формы выражений сначала положим, что префикснымвыражением одиночного операнда а является сам этот операнд. Далее, префикснаяформа для выражения (Et) 9 (Е2), где 9 — бинарный оператор, имеет вид QPiP2, здесьР! и Pz — префиксные формы для выражений Е\ и Е2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
