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