Д. Кнут - Искусство программирования том 1 (1119450), страница 87
Текст из файла (страница 87)
Наконец, на рис. 20, (с) показан еще один общий способ представления древовидных структур с использованием отстпупа (шйеп1аИоп), Само по себе количество разных методов представления является прекрасным доказательством важности древовидных структур как в повседневной жизни, так и в программировании. В итоге любая классификация с иерархической структурой имеет древовидную структуру. (а) (с) Рис. 20. Способы изображения древовидных структур: (а) вложенные множества; (Ь) вложенные скобки; (с) список с отступами.
Алгебраическая формула неявным образом определяет древовидную структуру, которая часто обозначается другими средствами, причем либо вместе со скобками, либо совсем без них. Например, на рис. 21 показано дерево, соответствующее арифметическому выражению (2) а — 6(с/Ы+ е//). Согласно стандартным математическим соглашениям операции умножения и деления обладают приоритетом по сравнению с операциями сложения и вычитания. Благодаря атому приведенное выше выражение можно представить в упрощенном виде (2), а не в виде а — (6 х ((с/д) + (е//))), в котором все части выражения заключены в скобки. Эта связь между формулами и деревьями особенно важна при создании приложений.
Рис. 21. Представление формулы (2) в виде дерева. Обратите внимание на то, что список с отступами, показанный на рис. 20, (с), очень похож на оглавление данной книги. Действительно, даже сама зта книга обладает древовидной структурой. Например, древовидная структура главы 2 показана на рис. 22.
Здесь следует отметить одну важную особенностгс нумерация разделов в настоящей книге представляет собой еше один способ представления древовидной структуры. Этот метод часто называется десятичной системой обозначений Дьюи (1)енеу десипа1 по1абоп) по аналогии с подобной классификационной схемой, применяемой в библиотеках. Для дерева, представленного на рис. 19, она будет выглядеть так: 1 А; 1.1 В; 1.1.1 Н; !.1.2,У; 1.2 С; 1.2.1 Ю; 1.2.2 Е; 1.2.2.1 С; 1,2.3 Р.
Десятичную систему обозначений Дьюи можно применять по отношению к любому лесу: корень й-го дерева леса задается числом й, и, если а — количество узлов степени тп, его дети будут обозначаться как а.1,а.2,...,а.т. Десятичная система обозначений Дьюи обладает многими простыми математическими свойствами и является полезным инструментом для анализа деревьев. Одним из примеров является естественное последовательное упорядочение узлов произвольного дерева, которое аналогично упорядочению разделов данной книги.
'Например, раздел 2.3 предшествует разделу 2.3.1 и располагается за разделом 2.2.6. Между системой десятичных обозначений Дьюи и индексной системой обозначения переменных, которая неоднократно использовалась выше, существует довольно близкая связь. Если Р— это лес деревьев, то Г[1] — все множество поддеревьев первого дерева, Е[1][2] = У[1,2] — множество поддеревьев второго поддерева из множества Ц1], а В[1,2, 1] — первое множество поддеревьев первого поддерева из множества Г[1,2] и т. д. Обозначение узла айсс.б в десятичной системе обозначений Дьюи соответствует узлу-родителю множества поддеревьев [г'[а, Ь, с, и]). Это обозначение является расширением обычного индексного обозначения, поскольку допустимый диапазон значений каждого индекса зависит от значений индексов на предыдущих уровнях.
Так, любой прямоугольный массив можно рассматривать как особый случай древовидной структуры, что н проиллюстрировано ниже на примере матрицы размера 3 х 4, < А[1, 1] А[1, 2] А[1, 3] А[1,4] А[2,1] А[2,2] А[2,3] А[2,4] 4[3 1] А[3 2] А[3 3] А[3 4] Я/ )~ у' / ~ ~' у'У/ ~~', Однако здесь следует отметить, что такая древовидная струк~ура не совсем корректно отражает структуру матрицы, поскольку в ней представлены связи между элементами в пределах каждой строки, но отсутствуют связи между элементами в пределах каждого столбца. В свою очередь, лес можно рассматривать как особую структуру списка [Йвс вггиссиге).
Слово "список" здесь применяется в очень специфическом смысле, н, чтобы подчеркнуть это, его пишут с прописной буквы: "Список". Рекурсивно Список определяется как конечная последовательность атомов или Списков, число которых может бытпь больше или равно нулю. Здесь под словом "атом" подразумевается неопределенное понятие, которое может относиться к элементам любой совокупности объектов и которое можно отличить от Списка.
С помощью обычной системы обозначений на основе запятых и скобок можно различать атомы и Списки, а также быстро и просто указывать упорядочение в пределах Списка. 2.1 Введение 2.2.1 Стеки, очереди и деки 2.2.2 Последовательное распределение 2.2 Линейные списки 2.2.5 Дважды связанные списки 2.2.б Массивы и ортогональные списки 2.3.1 Обход бинарных деревьев 2,3.2 Представление деревьев в виде бинарных деревьев 2 Информационные структуры 2.3.3 Другие представлания дерЕвьев 2.3.4.1 Свободные деревья 2.3 Деревья 2.3.4.2 Ориентированные деревья 2.3.4.3 Лемма о бесконечном деРеве 2.3.4.4 Перечисление деревьев 2.3.4.5 Длина пути 2.3.4.6 История и библиография 2.3.б Списки и "сборка мусора" 2.3 Динамическое выделение памяти 2.б История и библиография 2.4 Многосвязные структуры 2.2.3 Связанное распределение 2.2.4 Циклические списки 2.3.4 Основные математические свойства деревьев Рис.
22. Структура главы 2. Рассмотрим, например, Список с пятью элементами Т = (а, (Ь,а,Ь), ( ), с, (((2)))), в котором сначала следует атом а, затем — Список (Ь, а, Ь), после — пустой Список ( ), атом с и, наконец, Список (((2))). Последний Список состоит из Списка ((2)), который включает Список (2), который, в свою очередь, включает атом 2.
Этому Списку соответствует такая древовидная структура: (4) Звездочки используются для обозначения Списков, чтобы их можно было отличить от атомов. Индексные обозначения могут применяться для Списков точно так, как и для леса, например Т,[2] = (Ь, а, Ь) и А[2, 2] = а. Узлы-Списки на схеме (4) не несут никакой другой полезной информации, помимо того, что они являются Списками. Для устранения этого недостатка их можно пометить символами, как было сделано выше для деревьев и других структур. Так, обозначение А = (а: (Ь, с), д: ( )) могло бы соответствовать дереву Важное отличие между Списками и деревьями заключается в том, что Списки могут перекрываться (т. е, подсписки могут пересекаться) и даже быть рекурсивными (т. е.
содержать самих себя). Например, Список (5) ЛХ = (М), как и Список Ж = (а:М, .Ь:М,с, Ю), (б) не соответствует никакой древовидной структуре. (В этих примерах прописными буквами указаны Списки, а строчными — ярлыки и атомы.) Структуры (5) и (6) с помощью звездочки, обозначающей Спигок, можно схематически отобразить таким образом: *[Х] -г'~,~ ая[М] Ьв[М] с [М] ! [М] [ЛХ] На самом деле Списки не так уж сложно устроены, как может показаться после ознакомления с приведенными выше примерами.
По сути, они являются простым обобщением линейных списков, которые рассматривались в разделе 2.2, с дополнительным условием, что элементы линейных Списков могут быть переменными связи, которые указывают на другие линейные Списки (и, возможно, на самих себя). Резюме. Четыре тесно связанных типа информационных структур — деревья, леса, бинарные деревья и Списки — имеют разное происхождение, поэтому они очень важны для компьютерных алгоритмов.
В настоящей главе представлены различные способы схематического изображения этих структур, а также рассмотрены некоторые термины и понятия, используемые при работе с ними. В следующих разделах данные идеи рассматриваются более подробно. УПРАЖНЕНИЯ 1. [1В) Сколько различных деревьев можно создать на основе узлов А, В и С? 2. [20) Сколько разных ориентированных деревьев можно создать на основе узлов А, В н С? 3.
[М00] Докажите, опираясь только на определения, что для каждого узла Х дерева существует единственный путь к корню, а именно — единственная последовательность?» > 1 узлов Х», Хю..., Х», таких, что Х» является корнем узла, Хв = Х, а Х» — родителем Х,+» для 1 < 1 < и. (Этот метод типичен для доказательств почти всех элементарных фактов о древовидных структурах.) Указание. Примените метод индукции по отношению к количеству узлов дерева 4. [01) Верно ли следующее утверждение: "Если в обычной схеме дерева (с корнем сверху) узел Х обладает большим номером уровня, чем узел 1, то узел Х располагается в этой схеме ниже узла у"'э 5. [02] Если узел А имеет трех братьев-сестер, а узел В является родителем узла А, то чему равна степень узла В? 6.
[21] Дайте определение отношения "Х является т-родным кузеном (1-родные кузены--это двоюродные братья, 2-родные кузены — это троюродные братья и т. д.) 1' в и-м колене" (т. е Х на и поколений старше У) для узлов Х н У дерева по аналогии с генеалогическим деревом, если»и > 0 н и > О. (Значения этих терминов в контексте генеалогических деревьев найдите в словаре.) Т. [ЗЗ] Расшнрьте определение нз предыдущего упражнения для всех т > — 1 н для всех целых чисел и > — (т+ 1) таким образом, чтобы для любых двух узлов Х н 1' дерева существовали такие единственные т н и, что Х является т-род»»ь»л» братол»-сестрой узла У в и-м казеые. 8. [ОЗ) Какое бинарное дерево не является деревом'? 9.
[00] Какой узел (В нли А) в двух бинарных деревьях (1) является корнем? 10. [МЗО) Набор непустых множеств называется вложенным. если для заданной нары множеств Х и 1" либо Х С Г, либо Х:» 1', либо Х н У не пересекаются. (Иначе говоря, пересечением Х Г» У является либо Х, либо 1', либо 9) На рнс. 20, (а) показано, то любое дерево соответствует набору вложенных множеств.
Верно ли обратное утверждение: каждый такой набор соответствует дереву? ь 11. [НМЗЗ] Расширим определение дерева для включения понятия бесконечного дерева, рассмотрев наборы вложенных множеств нз упр 10. Можно ли для каждого узла бесконечного дерева определить понятия "уровень", "степень", "родитель" н "ребенок" ? Приведите примеры вложенных лтожеств действительных чисел, соответствующих дереву, в котором а) каждый узел обладает несче»ной степенью н имеется бесконечное множество уровней; Ь) имеются узлы с несчетным уровнем, с) каждый узел имеет по крайней мере степень 2 и существует несчетное чножество уровней 12.
[МВЗ) При каких условиях частично упорядоченное множество соответствует неупорядоченному дереву или лесу» (Частично упорядоченные множества определены в разделе 223) 13. [10] Предположим, что ноллер узла Х в десятичной системе обозначений Дьюи равен ал а» ал Какими тогда будут номера узлов на пути от Х к корню (см упр 3) в этой системе обозначений» 14. [М22] Пусть Я вЂ” зто ллобое непустое множество элементов 1 ал ал, где й > О и аы,ал — положительные целые числа Покажите, что Я соответствует дереву в том случае, когда оно конечно и удовлетворяет следующеллу условию если а т принадлежит этому множеству, то ему также принадлежит а (т — 1), если т > 1, или о, если т = 1 (Это условие, очевидно, выпачняется для дерева в десятичной системе обозначений Дьюи, следовательно, его лложно рассллатривать как еще один способ определения древовидной структуры ) ь 15.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
