Деревья общего вида (не двоичные).

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

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

Исходное недвоичное дерево	Представление в виде списка списков

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

TypeTp = ^ TNode;

TNode = record

Inf : <описание>;

NextParent, NextChild : Tp;

end;

В списках потомков ссылочное поле NextParent в простейшем случае просто не используется (устанавливается в nil). Как вариант, можно в этом поле хранить указатель на одноименную вершину в родительском списке.

Схематично рассмотрим реализацию основных операций с подобным списковым представлением недвоичных деревьев.

1. Вывод списка родителей с соответствующими списками потомков реализуется двойным циклом: внешний цикл идет по списку родителей, а внутренний позволяет для каждого родителя вывести список его потомков

PCurrentParent := pRoot;

While pCurrentParent <> nil do

Begin

“обработка вершины pCurrentParent^”;

pCurrentChild := pCurrentParent^.NextChild;

while pCurrentChild <> nil do

Begin

“обработка вершины pCurrentChild^”;

pCurrentChild := pCurrentChild^.NextChild;

end;

pCurrentParent := pCurrentParent^.NextParent;

end;

2. Добавление вершины X как потомка вершины Y:

· “поиск вершины Y обходом всех вершин”;

· if “вершина Y найдена в списке родителей” then “добавляем X в список потомков вершины Y”;

· if “вершина Y найдена в списке потомков” then

ü “добавляем Y в список родителей”;

ü “создаем у вершины Y список потомков с вершиной X”;

3. Удаление вершины X, если она не корневая для всего дерева:

· “поиск вершины X обходом всех вершин”;

· if “вершина X найдена в списке родителей” then

ü “просмотром всех списков найти родителя вершины X”;

ü “удалить X из списка потомков”;

ü “к родителю X добавить список всех потомков X”;

· if “вершина X есть только в списке потомков” then

ü “удалить X из списка потомков”;

ü if “список потомков пуст, то удалить родителя из списка родителей”;