Прохождение списков и деревьев

Для прохождения списков и деревьев могут применяться как рекурсивные, так и циклические алгоритмы. В примере представленном далее даются две реализации функции search(), которая выполняет поиск элемента по ключу в однонапрвленном линейном списке. Функция возвращает NULL, если элемент не найден.

typedef struct BOOK {

struct BOOK * succ;

MY_BOOKS bookinf;

} T_NBOOKS;

T_NBOOKS * search (T_NBOOKS * list, char * keystr)

{

while (list != NULL)

if (strcmp(list -> bookinf.author, keystr) ==0) // в качестве ключа используется

return list; // фамилия автора книги

else

list = list -> succ;

return NULL;

}

В рекурсивном варианте функции заголовок функции тот-же, что и в предыдущем случае, а тело функции отличается:

{

if (list == NULL)

return NULL;

else

if (strcmp(list -> bookinf.author, keystr))

return search(last -> succ, keystr);

else

return list;

}

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

Рассмотрим общий случай представления деревьев, когда количество поддеревьев для любого узла дерева не фиксируется.

Пусть имеется дерево следующего вида:

1

2 3

4 5 6 7

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

1 NULL

2 3 NULL

4 5 6 7 NULL

NULL NULL NULL NULL

Рассмотрим процедуру обхода дерева, используя стратегию «слева-направо и вначале в глубину». Следует отметить, что существуют и другие стратегии, например обход дерева по уровням или справа-налево и т.д.

Функция treeSearch() демонстрирует полный обход дерева не возвращая какой-либо результат. В реальных проектах одним из аргументов этой функции должен быть: 1) либо указатель на некоторый узел и тогда функция определяет принадлежность узла дереву сравнивая указатели, 2) либо некоторая строка или число, являющиеся ключом, и тогда указанный ключ сравнивается с хранимыми в узлах дерева ключами, а функция возвращает указатель на найденный узел или NULL.

Соответствующие изменения в определение функции предлагается внести в качестве упражнения!

Запись, используемая для представления узлов дерева:

typedef struct NODE{

struct NODE * subtree;

struct NODE * succ;

void * data; // ссылка на данные

} T_NODE;

void treeSearch( T_NODE * treePtr) // treePtr – узел, с которого начинается обход

{ // это может быть и вершина дерева

T_NODE *next;

next = treePtr -> subtree;

if (next != NULL)

treeSearch (next);

next = treePtr -> succ;

if (next != NULL)

treeSearch (next);

}

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

Вопросы для самоконтроля

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

Вопросы для самостоятельного изучения

• Может ли определение записи (объединения) включать поле такого-же типа, что и сама запись?
• Чем отличаются сети и графы (орграфы) от деревьев?