Стивен Прата - Язык программирования C. Лекции и упражнения (6-е изд.) 2015

Обход дерева

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

• обработать элемент в узле;

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

• обработать правое поддерево (рекурсивный вызов).

Данный процесс можно разбить на две функции: Traverse() и InOrder() . Обратите внимание, что функция InOrder() обрабатывает левое поддерево, затем элемент и после этого правое поддерево. Такая организация обработки приводит к обходу дерева в алфавитном порядке. При желании можете самостоятельно посмотреть, что происходит в случае использования других порядков обработки, скажем, “элемент, левое поддерево, правое поддерево” и “левое поддерево, правое поддерево, элемент”.

Расширенное представление данных 777

Опустошение дерева

По существу опустошение дерева представляет собой тот же самый процесс, что и его обход. Другими словами, коду необходимо посетить каждый узел и применить к нему функцию free(). Код должен также переустановить члены структуры Tree, чтобы отразить пустое дерево. Функция DeleteAll() позаботится о структуре Tree и передаст задачу освобождения памяти функции DeleteAllNodes(). Последняя функция аналогична функции InOrder(). Она сохраняет значение указателя root->right. чтобы он оставался доступным после освобождения корня. Вот код упомянутых двух функций:

void DeleteAll(Tree * ptree)

{

if (ptree != NULL)

DeleteAllNodes(ptree->root); ptree->root = NULL; ptree->size = 0;

}

static void DeleteAllNodes(Trnode * root)

{

Trnode * pright;

if (root != NULL)

{

pright = root->right;

DeleteAllNodes(root->left); free(root);

DeleteAllNodes(pright);

}

1

Завершенный пакет

Полный код файла tree.с представлен в листинге 17.11. Вместе с файлами tree.h и tree, с формируется программный пакет для древовидного представления.

Листинг 17.11. Файл реализации tree.с

778 Глава 17

Расширенное представление данных 77!

780 Глава 17

Расширенное представление данных

781

782 глава 17

Тестирование пакета для древовидного представления

Теперь, когда реализации интерфейса и функций созданы, давайте применим их. В программе в листинге 17.12 используется меню с пунктами, предназначенными для добавления домашних животных в реестр членов клуба, вывода списка членов клуба, вывода количества членов, проверки членства и выхода из программы. Короткая функция main() сосредоточена на основной схеме программы. Большую часть работы выполняют поддерживающие функции.

Листинг 17.12. Программа petclub.с

Расширенное представление данных 783

784 Глава 17

Расширенное представление данных 785

Программа преобразует все буквы в прописные, поэтому СНАФФИ, Снаффи и сна- ффи не считаются разными кличками. Ниже показаны результаты пробного запуска.

Программа членства в клубе Nerfville Pet Club Введите букву, соответствующую вашему выбору: а) добавление животного 1) вывод списка животных n) количество животных f) поиск животных

d) удаление животного q) выход

а

Введите кличку животного:

Куинси

Введите вид животного:

СВИНЬЯ

Программа членства в клубе Nerfville Pet Club Введите букву, соответствующую вашему выбору: а) добавление животного 1) вывод списка животных n) количество животных f) поиск животных d) удаление животного q) выход а