Уровень 3 Уровень 2 Уровень 1 Уровень О

Рис. 15. Пример дерева.

Рис. 16. Еще один пример дерева.

способ размещения дерева на плоскости. Если не считать различными два дерева, которые Отличаются только относительным порядком поддеревьев узлов, то дерево называется ориентированным {oriented), поскольку при этом имеет значение только относительная ориентация узлов, а не их порядок. Сама природа представления данных в компьютере определяет неявный порядок любого дерева, поэтому в большинстве случаев упорядоченные деревья представляют наибольший интерес. Далее будем неявно предполагать, что все рассматриваемые деревья являются упорядоченными, еслп явно не указано обратное. Соответственно деревья на рис. 15 и 16 в общем случае рассматриваются как разные, хотя как ориентированные деревья они совершенно одинаковы.

Лес {forest) -это множество (обычно упорядоченное), не содержащее ни одного непересекающегося дерева или содержащее несколько непересекающихся деревьев. Тогда еще одна формулировка п. (Ь) в данном выше определении дерева могла бы выглядеть так: узлы дерева прн условии исключения корня образуют лес.

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

(Ь) ©

Рис. 17. Как следует рисовать деревья

Графически деревья можно представить по-разному. Например, для дерева на рис. 15 сухцествует еще три принципиально отличных альтернативных варианта, которые, как показано на рис. 17, отличаются расположением узлов относительно корня. Правила схематического изображения древовидных структур - это не чья-то прихоть, так как довольно часто при работе с ними приходится говорить о том, что один узел находится "над" другим, "выше" другого или является "крайним

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

Может показаться, что схема, представленная на рис. 15, выглядит предпочтительнее просто потому, что именно так растут деревья в природе. При отсутствии любых других существенных причин для более предпочтительного выбора следует использовать уже освященную веками традицию природы. Имея это в виду, автор при работе над данной серией книг следовал правилу изображения деревьев с корнем внизу, но после двух лет работы обнаружилась ошибочность такого выбора. Изучение литературы и многочисленные неформальные обсуждения широкого круга алгоритмов со специалистами в области информатики показали, что в более чем 80% рассмотренных случаев деревья изображаются с корнем вверху. Это не более чем непреодолимая тенденция рисовать от руки по направлению сверху вниз, а не снизу вверх (что вполне объяснимо, если вспомнить, как мы пишем). Даже термин "поддерево" в противоположность термину "наддерево" ассоциируется с нисходящим родством. Поэтому будем считать, что рис. 15 просто перевернут "вверх ногами". Впредь почти всегда схема дерева будет выглядеть так, как на рис. 17, (Ь), т. е. с корнем сверху и листьями внизу. В соответствии с такой ориентацией назовем корневой узел вершиной {apex) дерева и будем характеризовать уровни узлов как мелкие и глубокие.

Для рассмотрения деревьев необходимо создать хорошую описательную терминологию. Вместо двусмысленных формулировок наподобие "над" и "под" лучше использовать общепринятые термины, которые применяются при работе с генеалогическими деревьями. На рис. 18 показаны два наиболее распространенных типа генеалогических деревьев. Они отличаются тем, что в родословной показаны предки конкретного человека, а в родовой схеме - его наследники.

При наличии "скрещивания" родословная уже не является деревом, поскольку разные ветви дерева (как было отмечено выше) не могут соединяться. Для устранения этого несоответствия на рис. 18, (а) королева Виктория и принц Альберт дважды упоминаются в шестом поколении, а король Кристиан IX и королева Луиза - дважды в пятом и шестом поколениях. Родословную следует рассматривать как истинное дерево, если каждый его узел представляет не просто отдельного человека, а человека в качестве матери или отца какого-то другого человека.

Стандартная терминология древовидных структур происходит от генеалогических деревьев второго типа, а именно - от родовой схемы. Каждый узел называется родителем {parent) корней его поддеревьев, а сами корни называются братьями-сестрами {siblings), а также детьми {children) своего родителя. Корень всего дерева не имеет родителя. Например, на рис. 19 узел С имеет трех детей, D, Е и F, узел Е является родителем узла С, а узлы В и С являются братьями-сестрами. Эту терминологию, очевидно, можно расширить. Например, узел А является пра-прародителем (т. е. прадедушкой или прабабушкой) узла G, а узел В - двоюродным родителем (т. е. дядей или тетей) узла F, узлы Н и F являются двоюродными братьями-сестрами. Одни авторы вместо терминов "родители", "дети", "сестры-братья" предпочитают использовать "мужскую" терминологию: "отец" (father), "сын" (son), "брат" (brother), а другие - женскую: "мать" (mother) , "дочь" (daughter), "сестра" (sister). В любо.м случае узел имеет не более одного родителя или

Генриетта ,

Освальд----

Шарлотта -

Томас ------

Августа -

Адольф ----

Клод и н ~-

Александр---"

Луиза --- Кристиан IX -

Виктория -

Альберт-----

Виктория -

Альберт --- Елизавета --

Чарльз---"

Софи---

Морис --

Вильгельмина -Луис 11---~ Луиза ---

Йозеф---~

Шарлотта

Николай I ----

Шарлотта Вильям -- л уиза - Вильям -----

обилия -

Клод -

Мария -

Георг V -

; Виктория N

~ Луис

Ольг

Георг ]

Елизавета

Георг VI

, Алиса

Эидрю

Гомер; Магог Мадай /Иафет -Ивван ;

Фу в ал V Мешех Фирас

Аскеназ Рифат Фогарма Елиса Фарсис Киттим Доданим

Рис. 18. Генеалогические деревья (а) родословная, (Ь) родовая схема [Источники Burkes Peerag-e (1959), Aliminarh de Got/ia (1871), Genealogibches Яапс/бисй des Adels Furstliche HsLUser 1, Бытие 10 1-251

Сева

- Хавила

- Савта

- Равма Савтеха Нимрод / Лудим

Анамим Легавим Мицраим - Нафтухим Si Патрусим Y Каслухим * Кафторим Сидон Хет

Иевусей Аморрей Гергесей Евей АркеЙ Синей Арвадей Цемарей Химафей

Шева Дедан

Евер :