Д. Кнут - Искусство программирования том 1 (1119450), страница 86
Текст из файла (страница 86)
Рекурсивный характер деревьев можно наблюдать и в природе, например почки молодых деревьев растут и со временем превращаются в ветви (поддеревья), на которых снова появляются почки, которые также растут и со временем превращаются в ветви (поддеревья). и т. д. В упр. 3 методом индукции по числу узлов дерева доказано несколько важных свойств деревьев на основе приведенного выше рекурсивного определения.
Из этого определения следует, что каждый узел дерева является корнем некоторого поддерева данного дерева, Количество поддеревьев узла называется сглепенью (йедгее) этого узла. Узел со степенью нуль называется концевым узлом (1егпнпа1 поле) или листом (!еау). Неконцевой узел называется узлом вегпеленил (ЬгапсЛ попе). Уровень (1еге0 узла по отношению к дереву Т определяется рекурсивно следующим образом. Уровень корня дерева Т равен нулю, а уровень любого другого узла на единицу выше, чем уровень корня ближайшего поддерева дерева Т, содержащего данный узел. Этн понятия иллюстрируются на рис.
15 на примере дерева с семью узлами. Узел А является корнем, который имеет два поддерева: (В) и (С,.Р,Е,Е,С). Корнем дерева (С,Р,Е,Г,С) является узел С. Уровень узла С равен 1 по отношению ко всему дереву. Он имеет три поддерева, (Р), (Е) и (Г,С), поэтому С имеет степень 3. Концевыми на рис. 15 являютгя узлы В, Р, Е н С. Узел Е— единственный узел со степенью 1, а узел С вЂ” единственный узел со степенью 3.
Если в п. (Ь) данного выше определения имеет значение относительный порядок поддеревьев Ты...,Т,„, то дерево является упорядоченным (огйегеа 1гее). Если. в упорядоченном дереве гп > 2, то имеет смысл назвать поддерево Тз вторым по,здеревом данного корня и т. д. Упорядоченные деревья иногда также называются плоскими деревьями (р1але Сгееэ), поскольку при их упорядочении имеет значение Уровень 3 Уровень 2 Уровень 1 Уровень 0 Рис. 15. Пример дерева, Рис. 16.
Еще один пример дерева. способ размещения дерева на плоскости. Если не считать различными два дерева, которые отличаются только относительным порядком поддеревьев узлов, то дерево называется ориенитированньсм (огзеп1ев), поскольку при этом имеет значение только относительная ориентация узлов, а не их порядок.
Сама природа представления данных в компьютере определяет неявный порядок любого дерева, поэтому в большинстве случаев упорядоченные деревья представляют наибольший интерес. Далее будем неявно предполагать, что все рассматриваемые деревья являются упорядоченными, если явно не указано обратное. Соответственно деревья на рис, 15 и 16 в общем случае рассматриваются как разные, хотя как ориентированные деревья онн совершенно одинаковы.
Лес (~огеа1) — это множество (обычно упорядоченное), не содержащее ни одного непересекающегося дерева нли содержащее несколько непересекающихся деревьев. Тогда еще одна формулировка п. (Ь) в данном выше определении дерева могла бы выглядеть так: узлы дерева при у словии исключения корня образуют лес. Между абстрактными понятиями леса и деревьев существует не очень заметная разница.
При удалении корня дерева получим лес, и наоборот: при добавлении одного узла в лес, все деревья которого рассматриваются как поддеревья нового узла, получим дерево. Поэтому понятия "лес" и "дерево" часто используются как равнозначные при работе со структурами данных. Рис. 17. Как следует рисовать деревья2 Графически деревья можно представить по-разному. Например, для дерева на рис.
15 существует еще три принципиально отличных альтернативных варианта, которые, как показано на рнс. 17, отличаются расположением узлов относительно корня. Правила схематического изображения древовидных структур — это не чьято прихоть, так как довольно часто при работе с ними приходится говорить о том, что один узел находится "над' другим, "выше" другого или является 'крайним справа и т. д, Одни алгоритмы обработки древовидных структур называются нисходящими, а другие — восходящими.
Без строгого соглашения о правилах схематического изображения деревьев такая терминология может привести к путанице. Может показаться, что схема, представленная на рис. 15, выглядит предпочтительнее просто потому, что именно так растут деревья в природе. При отсутствии любых других существенных причин для более предпочтительного выбора следует использовать уже освященную веками традицию природы.
Имея это в виду., автор при работе над данной серией книг следовал правилу изображения деревьев с корнем внизу, но после двух лет работы обнаружилась ошибочность такого выбора. Изучение литературы и многочисленные неформальные обсуждения широкого круга алгоритмов со специалистами в области информатики показали, что в более чем 809о рассмотренных случаев деревья изображаются с корнем вверху. Это не более чем непреодолимая тенденция рисовать от руки по направлению сверху вниз, а не снизу вверх (что вполне объяснимо, если вспомнить, как мы пишем).
Даже термин "поддерево" в противоположность термину "иалдерево" ассоциируется с нисходящим родством. Поэтому будем считать, что ряс 15 просто перевернут "вверх погамв". Впредь почти всегда схема дерева будет выглядеть так, как на рис. 1?, (Ь), т. е. с корнем сверху и листьями внизу. В соответствии с такой ориентацией назовем корневой узел вершиной (орех) дерева и будем характеризовать уровни узлов как мелкие и глубокие. Для рассмотрения деревьев необходимо создать хорошую описательную терминологию. Вместо двусмысленных формулировок наподобие "над" и "под" лучше использовать общепринятые термины, которые применяются при работе с геиеалогическими деревьями. На рис.
18 показаны два наиболее распространенных типа генеалогических деревьев. Они отличаются тем, что в родословкой показаны предки конкретного человека, а в родовой схеме — его наследники. При наличии "скрещивания" родословная уже не является деревом, поскольку разные ветви дерева (как было отмечево выше) не могут соединяться. Для устранения этого несоответствия на рис. 18, (а) королева Виктория и принц Альберт дважды упоминаются в шестом поколении, а король Кристиан 1Х и королева Луиза— дважды в пятом и шестом поколениях.
Родословную следует рассматривать как истинное дерево, если каждый его узел представляет не просто отдельного человека, а человека в качестве матери или отца какого-то другого человека. Стандартная терминология древовидных структур происходит от генеалогических деревьев второго типа, а именно — от родовой схемы. Каждый узел называется родителем (рагеп1) корней его поддеревьев, а сами корни называются братьлмисестрами (гй!туг), а также детьми (сЬь!дгеп) своего родителя. Корень всего дерева не имеет родителя. Например, на рис. 19 узел С имеет трех детей, Р, Е и Г, узел Е является родителем узла С, а узлы В и С являются братьями-сестрами.
Эту терминологию, очевидно, можно расширить. Например, узел А является прапрародителем (т. е. прадедушкой или прабабушкой) узла С, а узел  — двоюродным родителем (т. е. дядей или тетей) узла Е, узлы Н и Е являются двоюродными братьями-сестрами. Одни авторы вместо терминов "родители', "дети", "сестры- братья" предпочитают использовать "мужскую" терминологию: "отец" (1агЬег), "сын' (гоп), "брат" (Ьгогйег), а другие — женскую: "мать" (шогЬег), "дочь" (с1ап8Ь- сег), "сестра" (в1всег). В любом случае узел имеет не более одного родителя или Каролмна Чврл з Фре с Клод Марн ~ Фра « Алемса дра Элу рд РН ю Але са др А е сандре Константин Кристиан гХ Хв Вой А а Эдвмм Анна В л Ге рис та Ос д Шро То а Авгус а Адолаф Клодин А с др Лу за крн гх В торим Ал б р В «торн» А.
бер Елее* е Чврл Г.афм Мор с Вил ге и Луис Н Лу з йозеф Ш рло Нино аЯ ! Ш рла г В ла Л за в Сйсилн Ма! м Георг К! Геор Тг А са Вниторнл Луис !Т *"" ° Олаш Э дрш Луиза Георг ! Ам«з Гомер — Р ф Ивфет — И а Ките~ Фувал дод „„ Мешен Ф рас Сева Р Дедан Са ее Ни род луд А а нм л М ира — Нафту» На рус» Ка«лу Каф р Рис. 18. Генеалогические деревья (а) родословная, (Ь) родовая схема (Источники Внг(се'е Реегаде (1959), А!шанагЬ г/е СоГЬа (1871), Сепеа(ойззс1гее Напг)ЬВСЬ ггее Адей Ротс!>МЛе Наибег 1, Бытие 10 1- 25] С дон Фг Хе Иезус й ,А ррй ф Ген~ сей Х аан Е ей Ар ей С еЯ Ар адей Це аре» Хи аф*й Е А«ур -Фале г~~г и Арф сал — Са — Е ер Смм Иом и «~ ху м Гефр Маш (Ь) предка.
Далее для обозначения родства, которое может простираться на несколько уровней дерева, будут ис- А пользоваться термины "предок" (апсевсог) и "потомок" и с (йеэсепдапг). Например, йотомками узла С на рис. 19 П З О Я Р являются узлы 19, Е, Г и С, а предками узла С вЂ” узлы Е,Си А. с Родословная, показанная на рис. 18., (а), является примером бинарного дерева (бтагу 1~ее) — одного из наиРис. 19. Обычная схема дерева более важных типов деревьев.
Читатель наверняка не рвз встречался с бинарными деревьями в соревнованиях по теннису или других турнирах, которые проводятся по олимпийской системе с выбыванием проигравшего, Каждый узел бинарного дерева имеет не более двух поддеревьев, причем в случае только одного поддерева следует различать левое и правое. Строго говоря, бинарное дерево †э конечное множество узлов, которое является пусты нлп состоят пз корня и двух непересекающихся бинарных деревьев, которые называются левым и правым поддеревьями данного корня.
Тщательно изучим это рекурсивное определение бинарного дерева. Обратите внимание на то, что бинарное дерево не является особым типом ранее определенного обычного дерева. На самом деле это совершенно другое понятие (хотя впоследствии мы увидим, что у них есть много общего). Например, бинарные деревья являются различными, так квк в первом случае корень имеет пустое правое поддерево, а в другом — пустое левое поддерево. Однако как деревья онн совершенно идентичны.
Бинарное дерево может быть пустым, а обычное дерево — нет. Следовательно, при работе с бинарными деревьями нужно не забывать об обязательном эпитете "бинарный", чтобы не путать их с обычными деревьями. Некоторые авторы предлагают несколько иное определение бинарного дерева (см. упр, 20). Древовидную структуру можно представить графически несколькими способами, которые могут выглядеть совершенно не так, как настоящие деревья в природе. На рис. 20 показаны три способа представления структуры с рис. 19: по сути, на рис.
20, (а) дерево с рис. 19 представлено в виде ориентированного дерева (опггкей ггее). Эта схема является частным случаем вложенных мнозкесшв(псз1ей зе1з), а именно — набором множеств. в котором либо каждая пара множеств не пересекается, либо одно множество содержит другое (см. упр, 10). Если на рис. 20, (а) вложенные множества расположены в одной плоскости, то на рис. 20. (Ь) они находятся на одной линии, причем таким образом указывается и упорядочение данного дерева. Схема на рнс. 20, (Ь) может рассматриваться как некая алгебраическая формула с вложенными скобками.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
