10.8.2. Деревья

Бинарное дерево.

Каждая вершина бинарного дерева содержит:

• 2 указателя (на каждый альтернативный путь поиска - на поддерево);

• данные - указатель на объект, содержащий данные, принадлежащие этой вершине.

Для реализации структур данных типа дерева предлагаются 4 варианта (А, Б, В и Г) их организации:

Вариант 1 (А)

Рис. 10.2. Древовидная структура типа А

В древовидной структуре типа А, представленной на рис. 10.2, каждая вершина содержит 3 поля: поле данных и два поля указателей на другие вершины. Левый указатель служит для ссылки на вершину нижнего уровня, а правый - на соседнюю вершину того же уровня. Указателям, не ссылающимся на другие вершины, присваивается значение NULL (на рис. 10.2 они помечены крестиками).

Вариант 2 (Б)

Рис. 10.3. Древовидная структура типа Б

Древовидная структура типа Б (рис. 10.3) строится из вершин, состоящих из двух полей: поля данных и указателя. Указатель ссылается на вспомогательный список, с помощью которого устанавливается связь текущей вершины с вершиной нижнего уровня. Каждый элемент этого списка содержит указатели на соседний элемент вспомогательного списка и на одну вершину нижнего уровня.

Вариант 3 (В)

Рис.10.4. Древовидная структура типа В

В древовидной структуре типа В (рис. 10.4) вершина состоит всегда из 4 элементов: поля данных и 3 указателей на возможные вершины нижнего уровня. Указателям, не ссылающимся на вершины, присваивается значение NULL.

Вариант 4 (Г)

Рис. 10.5. Древовидная структура типа Г

В древовидной структуре типа Г (рис. 10.5) каждая вершина содержит следующие поля:

• поле данных;

• поле, в котором указано число координирующих вспомогательных полей;

• вспомогательные поля, содержащие указатель на вершину более высокого уровня (предыдущую) и указатели на вершины нижнего уровня.

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

Для каждого из приведенных выше вариантов необходимо разработать следующие функции:

1. Создание пустого дерева.

2. Добавление вершины к указанной вершине дерева.

3. Распечатка (вывод на дисплей) структуры дерева.

4. Удаление заданного элемента из дерева с уничтожением поддерева подчиненных вершин.

5. Запись дерева в файл.

6. Уничтожение дерева.

7. Восстановление (чтение) дерева из файла.

8. Изображение структуры дерева на экране.