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

Корнем этого дерева является узел Книга, который имеет три поддерева соответственно с корнями ГлЛ, Гл.2 и Гл.З. Эти отношения показаны линиями, идушими из корня Книга к узлам Гл.1, Гл.2 и Гл.З. Узел Книга является родителем узлов Гл.1, Гл.2 и Гл.З, а эти три узла - сыновьями узла Книга.

Третье поддерево, с корнем Гл.З, состоит из одного узла, остальные два поддерева имеют нетривиальную структуру. Например, поддерево с корнем Гл.2 в свою очередь имеет три поддерева, которые соответствуют разделам книги Р.2.1, Р.2.2 и Р.2.3; последние два поддерева имеют по одному узлу, в то время как первое имеет два поддерева, соответствуюшие подразделам книги Р.2.1.1 и Р.2.1.2. □

Пример 3.1 показывает типичные данные, для которых наилучшим представлением будут деревья. В этом примере родительские отношения устанавливают подчиненность глав и разделов: родительский узел связан с узлами сыновей (и указывает на них), как узел Книга подчиняет себе узлы Гл.1, Гл.2 и Гл.З. В этой книге вы встретите много различных отношений, которые можно представить с помошью родительских отношений и подчиненности в виде деревьев.

Путем из узла п\ в узел п/, называется последовательность узлов Пг, Лд, щ, где для всех /, 1 < i < к, узел щ является родителем узла n,+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. Два различных упорядоченных дерева

Упорядочивание слева направо сыновей ("родных детей" одного узла) можно использовать для сопоставления узлов, которые не связаны отношениями предки-потомки. Соответствующее правило звучит следующим образом: если узлы а и b яв-



ляются сыновьями одного родителя и узел а лежит слева от узла Ь, то все потомки узла а будут находиться слева от любых потомков узла Ъ.

Пример 3.2. Рассмотрим дерево на рис. 3.3. Узел 8 расположен справа от узла 2, слева от узлов 9, 6, 10, 4 и 7, и не имеет отношений справа-слева относительно предков 1, 3 и 5.


Рис. 3.3. Дерево

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

Прямой, обратный и симметричный обходы дерева

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

• Если дерево Т является нулевым деревом, то в список обхода заносится пустая запись.

• Если дерево Г состоит из одного узла, то в список обхода записывается этот узел.

• Далее, пусть Т - дерево с корнем п и поддеревьями Ti, ..... Г, как показано

на рис. 3.4. Тогда для различных способов обхода имеем следующее.


Рис. 3.4. Дерево Т

Обход узлов дерева равнозначен упорядочиванию по какому-либо правилу этих узлов. Поэтому в данном разделе мы будем использовать слова "обход узлов" и "упорядочивание узлов" как синонимы. - Прим. ред.



1. При прохождении в прямом порядке (т.е. при прямом упорядочивании) узлов дерева Т сначала посещается корень «, затем узлы поддерева Т, далее все узлы поддерева Та, и т.д. Последними посещаются узлы поддерева 1".

2. При симметричном обходе узлов дерева Т сначала посещаются в симметричном порядке все узлы поддерева Tj, далее корень «, затем последовательно в симметричном порядке все узлы поддеревьев Tj, • •., Г.

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

В листинге 3.1,а показан набросок процедуры PREORDER (Прямое упорядочивание), составляющей список узлов дерева при обходе его в прямом порядке. Чтобы из этой процедуры сделать процедуру, выполняющую обход дерева в обратном порядке, надо просто поменять местами строки (1) и (2). В листинге 3.1,6 представлен набросок процедуры INORDER (Внутреннее упорядочивание). В этих процедурах производится соответствующее упорядочивание деревьев путем вызова соответствующих процедур к корню дерева.

Листинг 3.1. Рекурсивные процедуры обхода деревьев

а. PpoiieAypaPREORDER

procedure PREORDER ( п: узел ); begin

(1) занести в список обхода узел л;

(2> for для каждого сына с узла л в порядке слева направо do

PREORDER (с) end; { PREORDER )

б. Процедура INORDER

procedure INORDER ( n: узел ) ; begin

if л - лист then

занести в список обхода узел л; else begin

INORDER(самый левый сын узла п) ; занести в список обхода узел л;

for для каждого сына с узла п, исключая самый левый, в порядке слева направо do INORDER ( с)

end; { 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,





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.0016