2 Информационные структуры

2.2 Линейные списки

2.3 Деревья

2.2.1 Стеки, очереди и деки

2.2.2 Последовательное распределение

2.2.3 Связанное

распределение

2.2.4 Циклические списки

2.2.5 Дважды

связанные списки

2.2.6 Массивы и ортогональные списки

2.3.1 Обход бинарных деревьев

2.3.2 Представление деревьев в виде бинарных деревьев

2.3.3 Другие представления деревьев

2.3.4 Основные К математические свойства деревьев /

2.3.4.1 Свободные деревья

2.3.4.2 Ориентированные деревья

2.3.4.3 Лемма о бесконечном дереве

2.3.4.4 Перечисление деревьев

2.3.4.5 Длина пути

2.3.4.6 История и библиография

2.3.5 Списки и

"сборка мусора"

2.4 Многосвязные структуры

2.5 Динамическое выделение памяти

2.6 История и библиография

Рис. 22. Структура главы 2.

Рассмотрим, например, Список с пятью элементами

Ь = {а, (Ь,а,Ь), {), с, т)))), (3)

в котором сначала следует атом а, затем - Список (b,a,b), после - пустой Список ( ), атом с и, наконец, Список (((2))). Последний Список состоит из Списка ((2)), который включает Список (2), который, в свою очередь, включает атом 2. Этому Списку соответствует такая древовидная структура:

Звездочки используются для обозначения Списков, чтобы их можно было отличить от атомов. Индексные обозначения могут применяться для Списков точно так, как и для леса, например L[2] = (Ь, а, Ь) и L[2,2] = а.

Узлы-Списки на схеме (4) не несут никакой другой полезной информации, помимо того, что они являются! Списками. Для устранения этого недостатка их можно пометить символами, как было сделано выше для деревьев и других структур. Так, обозначение

A=(a:(b,c),d:()) могло бы соответствовать дереву

а* а*

Важное отличие между Списками и деревьями заключается в том, что Списки могут перекрываться (т. е. подсписки могут пересекаться) и даже быть рекурсивными (т. е. содержать самих себя). Например, Список

М = (Л/), (5)

как и Список

N = {a:M,b:M,c,N), (6)

не соответствует никакой древовидной структуре. (В этих примерах прописными буквами указаны Списки, а строчными - ярлыки и атомы.) Структуры (5) и (6) с помощью звездочки, обозначающей Список, можно схематически отобразить таким образом:

*[7V]

а*[М] Ь*[М] с [N] (7)

I I [М] [М]

На самом деле Списки не так уж сложно устроены, как может показаться после ознакомления с приведенными выше примера.ми. По сути, они являются простым

обобщением линейных списков, которые рассматривались в разделе 2.2, с дополнительным условием, что элементы линейных Списков могут быть переменными связи, которые указывают на дрхгие линейные Списки (и, возможно, на самих себя).

Резюме. Четыре тесно связанных типа информационных структур-деревья, леса, бинарные деревья и Списки - имеют разное происхождение, поэтому они очень важны для компьютерных алгоритмов. В настоящей главе представлены различные способы схематического изображения этих структур, а также рассмотрены некоторые термины и понятия, используемые при работе с ними. В следующих разделах данные идеи рассматриваются более подробно.

УПРАЖНЕНИЯ

1. [18] Сколько различных деревьев можно создать на основе узлов А, В и С!

2. [20] Сколько разных ориентированных деревьев можно создать на основе узлов А, В и С?

3. [Л/20] Докажите, опираясь только на определения, что для каждого узла X дерева существует единственный путь к корню, а именно - единственная последовательность к > I узлов Xl, Хг,. , Хк, таких, что Xi является корнем узла, Хк = X, а Xj-родителем Xj+i для \ < j < к. (Этот метод типичен для доказательств почти всех элементарных фактов о древовидных структурах.) Указание. Примените метод индукции по отношению к количеству узлов дерева

4. [01] Верно ли следующее утверждение: "Если в обычной схеме дерева (с корнем сверху) узел X обладает большим номером уровня, чем узел У, то узел X располагается в этой схеме ниже узла У"

5. [02] Если узел А имеет трех братьев-сестер, а узел В является родителем узла А, то чему равна степень узла Bl

► 6. [21] Дайте определение отношения "Л является та-родным кузеном (1-родные кузены- это двоюродные братья, 2-родные кузены - это троюродные братья и т. д.) У в п-м колене" (т. е X на п поколений старше Y) для узлов А и Y дерева по аналогии с генеалогически.м деревом, если m > О и п > 0. (Значения этих терминов в контексте генеалогических деревьев найдите в словаре.)

7. [23] Расширьте определение из предыдущего упражнения для всех m > -1 и для всех целых чисел п > -(т-(-1) таким образом, чтобы для любых двух узлов А и Y дерева существовали такие единственные тип, что А является т-родным братом-сестрой узла Y в п-м колене.

► 8. [03] Какое бинарное дерево не является деревом?

9. [00] Какой узе.д (В или А) в двух бинарных деревьях (1) является корнем?

10. [М20] Набор непустых множеств называется вложенным, если для заданной пары множеств X и У либо X С У, либо А 3 Y, либо X и У не пересекаются. (Иначе говоря, пересечением X П У является либо А, либо У, либо 0 ) На рис. 20, (а) показано, что любое дерево соответствует набору вложенных множеств. Верно ли обратное утверждение: каждый такой набор соответствует дереву?

► 11. [НМ32] Расширим определение дерева для включения понятия бесконечного дерева, рассмотрев наборы вложенных множеств из упр 10. Можно ли для каждого узла бесконечного дерева определить понятия "уровень", "степень", "родитель" и "ребенок"? Приведите примеры вложенных множеств действительных чисел, соответствующих дереву, в котором

а) каждый узел обладает несчетной степенью и имеется бесконечное множество уровней;