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

Обратите внимание, что функция открытого интерфейса (Deleteltem()) оперирует понятиями, близкими конечному пользователю (элементами и деревьями), а скрытая функция DeleteNode() выполняет будничные действия с указателями.

Обход дерева

Обход дерева является более сложной задачей, чем обход связного списка, поскольку каждый узел имеет две ветви, по которым нужно проследовать. Такая природа ветвления делает естественным методом решения этой задачи рекурсию типа “разделяй и властвуй” (см. главу 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) выход а

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

Бенни Ха-ха

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

попугай

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

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

Дон Бавилио

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

домашний кот

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

n) количество животных f) поиск животных

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

n

3 животных в клубе

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

n) количество животных f) поиск животных

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

Животное: БЕННИ ХА-ХА Животное: ДОН БАЗИЛИО Животное: КУИНСИ

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

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

q

Программа завершена.

786 глава 17

Соображения по поводу дерева

Двоичное дерево поиска обладает рядом недостатков. Например, двоичное дерево поиска эффективно, только если оно полностью заполнено, или сбалансирована Предположим, что вы сохраняете слова, которые вводятся в произвольном порядке. Есть шансы, что результирующее дерево будет иметь довольно небольшую глубину, как на рис. 17.12. Но представим, что вводятся данные в алфавитном порядке. Тогда каждый новый узел будет добавляться справа, и дерево может приобрести вид, показанный на рис. 17.16. Дерево на рис. 17.12 называют сбалансированным, а на рис. 17.16 — несбалансированным. Поиск в несбалансированном дереве не является более эффективным, чем последовательный поиск в связном списке.