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

Глубина узла v в дереве - это длина пути из корня в V. Высота узла V в дереве - это длина самого длинного пути из и в какой-нибудь лист. Высотой дерева называется высота его корня. Уровень узла V в дереве равен разности высоты дерева и глубины узла v. Например, на рис. 2.7,а узел 3 имеет глубину 2, высоту О и уровень 1.

Упорядоченным деревом называется дерево, в котором множество сыновей каждого узла упорядочено. При изображении упорядоченного дерева мы будем считать, что множество сыновей каждого узла упорядочено слева направо. Двоичньш (бинарньш) деревом называется такое упорядоченное дерево, что

1) каждый сын произвольного узла идентифицируется либо как левый сын, либо как правый сын,

2) каждый узел имеет не более одного левого сына и не более одного правого сына.

Поддерево Г,, корнем которого является левый сын узла v (если такое существует), называется левьш поддеревом узла v. Аналогично поддерево Тг, корнем которого является правый сын узла v (если такое существует), называется правым поддеревом узла v. Все узлы в Ti расположены левее всех узлов в Т.

Двоичное дерево обычно представляют в виде двух массивов ЛЕВЫЙСЫН и ПРАВЫЙСЫН. Пусть узлы двоичного дерева занумерованы целыми числами от 1 до п. В этом случае ЛЕВЫЙ-СЫН!/] =/ тогда и только тогда, когда узел с номером / является левым сыном узла с номером i. Если у узла i нет левого сына, то ЛЕВЫЙСЫН[1]=0. ПРАВЫЙСЫН[Л определяется аналогично.

Пример 2.3. Двоичное дерево и его представление изображены на рис. 2.7. □

Определение. Двоичное дерево называется полным, если для некоторого целого числа k каждый узел глубины меньшей k имеет как левого, так и правого сына и каждый узел глубины k является листом. Полное двоичное дерево высоты k имеет ровно 2*+-1 узлов.

Полное двоичное дерево высоты k часто представляют одним массивом. В позиции 1 этого массива находится корень. Левый сын узла в позиции ( расположен в позиции 2i, а его правый сын - в позиции 21+1. Отец узла, находящегося в позиции t>l, расположен в позиции 1/2 J.

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




Рис. 2,8, Прохождение дерева: а - в прямом порядке; б - обратном; в - внутреннем.

Определение. Пусть Т - дерево о корнем г и сыновьями Vt,. . . ..., Uft, kO. При k=0 это дерево состоит из единственного узла г.

Прохождение дерева Т в прямом порядке определяется следующей рекурсией:

1) посетить корень г,

2) посетить в прямом порядке поддеревья с корнями Uf, . . . , Уь в указанной последовательности.

Прохождение дерева Т в обратном порядке определяется следующей рекурсией:

1) посетить в обратном порядке поддеревья с корнями Vi, ... . . . , Vh в указанной последовательности,

2) посетить корень г.

Прохождение двоичного дерева во внутреннем порядке определяется следующей рекурсией:

1) посетить во внутреннем порядке левое поддерево корня (если оно существует),

2) посетить корень,

3) посетить во внутреннем порядке правое поддерево корня (если оно существует).

Пример 2.4. На рис. 2.8 изображено двоичное дерево, узлы которого пронумерованы в соответствии с прохождением его в прямом порядке (риб. 2,8,а), обратном (рив. 2.8,6) и внутреннем (рис. 2,8,в). □

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



Если все узлы занумерованы в порядке посещения, то рассмотренные нумерации обладают рядом интересных свойств.

При нумерации в прямом порядке все узлы поддерева с корнем г имеют номера, не меньшие г. Точнее, если - множество потомков узла г, то V будет номером некоторого узла из тогда и только тогда, когда r<u<r-f HDII. Поставив в соответствие каждому узлу V его номер в прямом порядке и количество его потомков, легко определить, является ли некоторый узел w потомком для v. После того как номера присвоены (в соответствии с прямым порядком) и вычислено количество потомков каждого узла, на вопрос, является ли w потомком для V, можно ответить за фиксированное время, не зависящее от размера дерева. Номера, соответствующие обратному порядку, обладают аналогичным свойством.

Номера узлов двоичного дерева, соответствующие внутреннему порядку, обладают тем свойством, что номера узлов в левом поддереве для V меньше v, а в правом поддереве больше v. Таким образом, чтобы найти узел с номером w, надо сравнить w с корнем г. Если ш=г, то искомый узел найден. Если ш<г, то надо повторить этот процесс для левого поддерева; если tiy>»r, то повторить процесс для правого поддерева. В конце концов узел с номером w будет найден. Такие свойства прохождений нам понадобятся в следующих главах.

Дадим теперь еще одно, последнее определение, касающееся деревьев.

Определение. Неориентированньш деревом называется неориентированный ациклический связный (любые два узла соединены путем) граф. Корневое неориентированное дерево - это неориентированное дерево, в котором один узел выделен в качестве корня.

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

2.5. РЕКУРСИЯ

Процедуру, которая прямо или косвенно обращается к себе, называют рекурсивной. Применение рекурсии часто позволяет давать более прозрачные и сжатые описания алгоритмов, чем это было бы возможно без рекурсии. В настоящем разделе мы приведем пример рекурсивного алгоритма и кратко опишем, как можно реализовать рекурсию на РАМ.





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 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0021