AOP_Tom1 (1021736), страница 88
Текст из файла (страница 88)
Между абстрактными понятиями леса и деревьев существует не очень заметная разница. При удалении корня дерева получим лес, и наоборот: при добавлении одного узла в лес, все деревья которого рассматриваются как поддеренья нового узла, получим дерево.
Поэтому понятия "лес" и "дерево" часто используются как равнозначные при работе со структурами данных. Рис. 17. Как следует рисовать деревьях Графически деревья можно представить по-разному. Например, для дерева на рис. 15 существует еще три принципиально отличных альтернативных варианта, которые, .как показано на рис. 17, отличаются расположением узлов относительно корня. Правила схематического изображения древовидных структур — это не чьято прихоть, так как довольно часто при работе с ними приходится говорить о том, что одиь узел ваходится "иад' другим, "выше" другого или является "крайним справа н т. д. Одни алгоритмы обработки древовидных структур называются нисходящими, а другие — восходящими.
Без строгого соглашения о правилах схематического изображения деревьев такая терминология может привести к путанице. Может показаться, что схема, представленная ва рис. 15, выглядит предпочтительнее просто потому, что именно так растут деревья в природе. При отсутствии любых других существенных причин для более предпочтительного выбора следует использовать уже освященную веками традицию природы. Имея это в виду, автор при работе над данной серией книг следовал правилу изображения деревьев с корнем внизу, но после двух лет работы обнаружилась ошибочность такого выбора.
Изучение литературы и многочисленные неформальные обсуждения широкого круга алгоритмов со специалистами в области информатики показали, что в более чем 80% рассмотренных случаев деревья изображаются с корнем вверху. Это не более чем непреодолимая тенденция рисовать от руки по направлению сверху вниз, а не снизу вверх (что вполне объяснимо, если вспомнить, как мы пишем). Даже термин "поддерево" в противоположность термину "нгддерево" ассоциируется с нисходящим родством.
Поэтому будем считать, что рнс. 15 просто перевернут "вверх ногамп". Впредь почти всегда схема дерева будет выглядеть так, как на рис. 17, (Ь), т. е. с корнем сверху и листьями внизу. В соответствии с такой ориентацией назовем корневой узел вершиной (арех) дерева и будем характеризовать уровни узлов как мелкие и глубокие. Для рассмотрения деревьев необходимо создать хорошую описательную терминологию.
Вместо двусмысленных формулировок наподобие "над" и "под" лучше использовать общепринятые термины, которые применяются при работе с генеалогическими деревьями. На рис. 18 показаны два наиболее распространенных типа генеалогических деревьев. Они отличаются тем, что в родословной показаны предки конкретного человека, а в родовой схеме — его наследники. При наличии "скрещивания" родословная уже не нвляетгя деревом, поскольку разные ветви дерева (как было отмечено выше) не могут соединяться. Для устранения этого несоответствия на рис. 18, (а) королева Виктория и принц Альберт дважды упоминаются в шестом поколении, а король Кристиан 1Х н королева Луиза— дважды в пятом и шестом поколениях.
Родословную следует рассматривать как истинное дерево, если каждый его узел представляет не просто отдельного человека, а человека в качестве матери илн отца какого-то другого человека. Стандартная терминология древовидных структур происходит от генеалогических деревьев второго типа, а именно — от родовой схемы. Каждый узел называется родителем (рагепг) корней его поддеревьев, а сами корни называются братьями- сестрами (ггбйпаг), а также детьми (сЫдгеп) своего родителя. Корень всего дерева не имеет родителя. Например, на рис.
19 узел С имеет трех детей, В, Е и Е, узел Е является родителем узла С. а узлы В и С являются братьями-сестрами. Эту терминологию, очевидно, можно расширить. Например, узел А является прапрародителем (т. е. прадедушкой нли прабабушкой) узла С, а узел  — двоюродным родителем (т. е, дядей или тетей) узла Г, узлы Н н Е являются двоюродными братьями-сестрами.
Одни авторы вместо терминов "родители', "дети", "сестры- братья" предпочитают использовать "мужскую" терминологию: "отец" (1асЬег), "сын" (гоп), "брат" (Ьгосйег), а другие — женскую: "мать" (шосЬег), "дочь' (дап8Ь1ег), 'сестра" (г1гсег). В любом случае узел имеет не более одного родителя или А а Эдвмн Амне В Г рне та О» д Шр то а Авгус в Адол ф К одни Ал с др Лу за Кри г* н 1Х В торна А берт В ор А бер Елмзвеета Чзр Соф Мор с В ае»г в Луис Н Лу зе йозеф Шарло тв Н Я1- Шаро а в Лт за В л Лтнса В нор Лун«Н А е««в лр в к и Алемсанлр» В Олма Ко с Э Дг Лу за Г ор'1 Крс 1Х 1а) Нам Карол на Чарлзе Фрасг К ад Марна Фр с Але ганлрв Эд,ард УН Сяснли Мар м г'3 Георг У1 Ге ор У Ас енвз Г, — Рифа Мвг г Ивфе — Иа а К Фуаал д двн Менгса Ф р Се «» а Св ху Ше в ~~~Рва в Са те р д Луд Аан Л г М цра — Н Фтг Ха Нвтрус К у Кафтор Рис.
18. Генеалогические деревья 1а) родословная, 1Ь) родовая схема )Источники Виг)се'й Реегаяе (1959), А!гоаоаеЛ с)е йогЛВ (1871), степей)о81ъсйеб Налс1ЬисЛ с)ее Ас)е1б ГигкСЛГЛе Наибег 1, Бытие 10 1- 25) С до Фгт Х И ву ей А орр й Хан а — Евей ~«лр ей С й Лр дей Ц арей Хн вфей Ела уг Ассур Арф» с д— Фа е Сага — Е р Ио тан Уц ху Гефер Мв сЬ) предка. Далее для обозначения родства, которое может простираться на несколько у ровней дерева, будут ис- А пользоваться термины "предок" (апсеэФог) н "потомок" в с (г1евсепйапт).
Например, йотомками узла С на рис. 19 в з в в являются узлы П, Е, Е н С, а предками узла С вЂ” узлы Е, С и А. С Родословная, показанная на рис. 18, (а), является примером бинарного дерева (бищгу ггее) — одного из наиРнс. 19. Обычная схема дерева более важных типов деревьев. Читатель наверняка не раз встречался с бинарными деревьями в соревнованиях по теннису нли других турнирах, которые проводятся по олимпийской системе с выбыванием проигравшего. Каждый узел бинарного дерева имеет не более двух поддеревьев, причем в случае только одного поддерева следует различать левое н правое. Строго говоря, бинарное дерево — это конечное множество узлов, которое является пустым плп состоит цз корня н двух непересекающихся бпнарных деревьев, которые называются левым и правым подлеревьями данного корня.
Тщательно изучим это рекурсивное определение бинарного дерева. Обратите внимание на то, что бинарное дерево не является особым типом ранее определенного обычного дерева. На самом деле это совершенно другое понятие (хотя впоследствии мы увидим, что у них есть много общего). Например, бинарные деревья являются различными, так как в первом случае корень имеет пустое правое поддерево, а в другом — пустое левое поддерево. Однако как деревья онн совершенно идентичны.
Бинарное дерево может быть пустым, а обычное дерево- — нет. Следовательно, при работе с бинарными деревьями нужно не забывать об обязательном эпитете "бинарный", чтобы не путать их с обычными деревьями. Некоторые авторы предлагают несколько иное определение бинарного дерева (см. упр. 20). Древовидную структуру можно представить графически несколькими способамн, которые могут выглядеть совершенно не так, как настоящие деревья в природе. На рис. 20 показаны три способа представления структуры с рнс. 19: по сухи, на рис.
20,(а) дерево с рис. 19 представлено в виде ориентированного дерева (огшп$ей 1гее). Эта схема является частным случаем вложенных мнолсесте(пез1ел зе1э), а именно — набором множеств. в котором либо каждая пара множеств не перегекается, либо одно множество содержит другое (см. упр. 10). Если на рис. 20, (а) вложенные множества расположены в одной плоскости, то на рис, 20.
(Ь) они находятся на одной линии, причем таким образом указывается н упорядочение данного дерева. Схема на рнс. 20, (Ь) может рассматриваться как некая алгебраическая формула с вложенными скобками. Наконец, на рис. 20, (с) показан еьце один общий способ представления древовидных структур с использованием отсшула (щдепгаНоп), Само по себе количество разных методов представления является прекрасным доказательством важности древовидных структур как в повседневной жизни, так и в программировании.
В итоге любая классификация с иерархической структурой имеет древовидную структуру. (А(В(Н)(.У))(С(ВНЕ(С)ИР))) (с) (Ь) (а) Рис. 20. Способы изображения древовидных структур: (а) вложенные множества; (Ь) вложенные скобки; (с) список с отступами. Алгебраическая формула неявным образом определяет древовидную структуру, которая часто обозначается другими средствами, причем либо вместе со скобками, либо совсем без них. Например, на рнс. 21 показано дерево, соответствующее арифметическому выражению (2) а — о(с/и+ е//). Согласно стандартным математическим соглашениям операции умножения и деленна обладают приоритетом по сравнению с операциями сложения и вычитания.
Благодаря этому приведенное выше выражение можно представить в упрощенном виде (2), а не в виде а — (Ь х ((с/с() + (е//))), в котором все части выражения заключены в скобки. Эта связь между формулами и деревьями особенно важна при создании приложений. Рнс. 21. Представление формулы (2) в виде дерева. Обратите внимание на то, что список с отступами, показанный на рис. 20, (с), очень похож на оглавление данной книги.
Действительно, даже сама эта книга обладает древовидной структурой. Например, древовидная структура главы 2 показана на рис. 22. Здесь следует отметить одну важную особенность: нумерация разделов в настоясцей кинге представляет собой еше один способ представления древовидной структуры. Этот метод часто называется десятичной системой обозначений Дьюи (Режеу с1есппа1 паса((оп) по аналогии с подобной классификационной схемой, применяемой в библиотеках. Для дерева, представленного на рис. 19, она будет выглядеть так: 1 А; 1.1 В; 1.1.1 Н; 1.1.2,7; 1.2 С; 1.2.1 Ю; 1.2.2 Е; 1.2.2.1 С; 1.2.3 Г. Десятичную систему обозначений Дьюи можно применять по отношению к любому лесу: корень Й-го дерева леса задается числом й, и, если о — количество узлов степени пэ, его дети будут обозначаться как о.1,а.2,...,а.ги.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
