ном участке памяти. Рассмотрим реализацию списка с помощью нескольких массивов. Перепишите процедуры Allocate-Object и Free-Object таким образом, чтобы элементы списка занимали позиции 1.. то, где то - число элементов списка. (Указание: воспользуйтесь реализацией стека на базе массива.)

11.3-5 Пусть двусторонне связанный список L длины то представлен с помощью трех массивов key, prev и next длины п, а процедуры выделения и освобождения места поддерживают двусторонне связанный список свободных позиций.

Напишите процедуру Compactify-List (сжатие списка), которая переписывает список L длины то в первые то позиций массивов, сохраняя его структуру (и изменяя список свободных позиций нужным образом). Время работы алгоритма должно быть О (то), размер используемой памяти (сверх занятой массивами) должен быть 0(1). Не забудьте доказать правильность своего алгоритма.

11.4. Представление корневых деревьев

Описанные в предыдущем разделе способы представления списков применимы и к другим структурам данных, составленным из однотипных элементов. В этом разделе мы научимся использовать указатели для представления деревьев. Начнём мы с двоичных деревьев, а затем объясним, как представлять деревья с произвольным ветвлением.

Каждая вершина дерева будет записью с несколькими полями. Одно из этих полей содержит ключ, как и в случае со списками. Остальные поля предназначены для хранения дополнительных данных и, главное, указателей на другие вершины. Как конкретно устроены эти поля, зависит от типа дерева.

Двоичные деревья

Как показано на рис. 11.9, при представлении двоичного дерева Г мы используем поля р, left и right, в которых хранятся указатели на родителя, левого и правого ребёнка вершины х соответственно. Если р[х] = nil, то ж - корень; если у ж нет левого или правого ребёнка, то left[x] или right[x] есть nil. С деревом Г связан атрибут root[T] - указатель на его корень. Если root[T] = nil, то дерево Г пусто.

Рис. 11.9 Представление двоичного дерева Т. Каждая вершина х включает поля р[х] (сверху), left[x] (внизу слева) и right[x] (внизу справа). Ключи на схеме не показаны.

Корневые деревья с произвольным ветвлением

Если известно, что число детей каждой вершины ограничено сверху константой к, то такое дерево можно реализовать аналогично двоичному дереву, помещая указатели на детей в поля childi, child2,..., child, заменяющие поля left и right. Если количество детей может быть любым, так делать нельзя: заранее неизвестно, сколько полей (или массивов - при представлении с помощью нескольких массивов) надо выделить.

Проблема может возникнуть и в том случае, если количество детей ограничено заранее известным числом к, но у большинства вершин число детей много меньше к: описанная реализация тратит много памяти зря.

Как же быть? Заметим, что любое дерево можно преобразовать в двоичное. При этом у каждой вершины будет не более двух детей: левый ребёнок останется тем же, но правым ребёнком станет вершина, которая была правым соседом (непосредственно следующим ребёнком того же родителя). Теперь это двоичное дерево можно хранить описанным выше способом.

Опишем схему хранения деревьев с произвольным ветвлением, основанную на этой идее, более подробно. Она называется «левый ребёнок - правый сосед» (left-child, right-sibling representation) и показана на рис. 11.10. По-прежнему в каждой вершине хранится указатель р на родителя и атрибут root[T] является указателем на корень дерева. Кроме р, в каждой вершине хранятся ещё два указателя:

1. left-child[x] указывает на самого левого ребёнка вершины ж;

Рис. 11.10 Представление дерева Т по схеме «левый ребёнок - правый сосед». В каждой записи х присутствуют поля р[х] (сверху), left-chila\x] (внизу слева) и right-sibling[x] (внизу справа). Ключи не показаны.

2. right-sibling[x] указывает на ближайшего справа соседа вершины х («следующего по старшинству брата»)

Вершина х не имеет детей тогда и только тогда, когда left-child[x] = NIL. Если вершина х - крайний правый ребенок своего родителя, то right-sibling[x] = NIL.

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

Иногда встречаются другие способы представления деревьев. Например, в главе 7 при реализации кучи не надо было хранить указателей на родителя и детей, поскольку их номера получались умножением и делением на 2. В главе 22 нам встретятся деревья, по которым двигаются от листьев к корню (и потому указатели на детей или соседей не нужны). Конкретный выбор представления дерева определяется спецификой задачи.

Упражнения

11.4-1 Нарисуйте двоичное дерево, представленное следующим образом: