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

Функции Seekltem(), MakeNode() и AddNode() не являются частью открытого интерфейса для типа Tree. Вместо этого они представляют собой статические функции, скрытые в файле tree.с, которые имеют дело с такими не относящимися к открытому интерфейсу деталями реализации, как узлы, указатели и структуры.

Функция MakeNode() довольно проста. Она обеспечивает динамическое выделение памяти и инициализацию узла. Аргументом функции является указатель на новый элемент, а ее возвращаемым значением — указатель на новый узел. Вспомните, что функция malloc() возвращает нулевой указатель, если она не может выделить запрошенную память. Функция MakeNode() инициализирует новый узел только в случае успешного выделения памяти. Вот код функции MakeNode():

static Trnode * MakeNode(const Item * pi)

{

Trnode * new_node;

new_node = (Trnode *) malloc(sizeof(Trnode) );

if (new_node != NULL)

{

new_node->item = *pi; new_node->left = NULL; new_node->right = NULL;

}

return new_node;

)

Функция AddNode() является второй по сложности в пакете двоичного дерева поиска. Она должна определить, куда должен быть помещен новый узел, и затем добавить его. В частности, ей необходимо сравнить новый элемент с корневым элементом, чтобы выяснить, в какое поддерево должен быть помещен новый элемент — левое или правое.

770 Глава 17

Если бы элемент был числом, то для выполнения сравнений можно было бы использовать операции < и >, а если бы строкой, то функцию strcmp(). Но элемент является структурой, содержащей две строки, так что для выполнения сравнений придется предусмотреть собственные функции. Функция ToLeft(), которая будет определена позже, возвращает значение True, если новый элемент должен быть помещен в левое поддерево, а функция ToRight() возвращает значение True, если новый элемент должен войти в правое поддерево. Эти две функции представляют собой аналоги операций < и >. Предположим, что новый элемент должен быть помещен в левое поддерево. Оно вполне может оказаться пустым. В таком случае функция просто устанавливает указатель на левый дочерний узел так, чтобы он ссылался на новый узел. А что, если левое поддерево не пустое? Тогда функция должна сравнить новый элемент с элементом в левом дочернем узле, чтобы выяснить, в какое поддерево дочернего узла должен быть помещен новый узел — левое или правое. Этот процесс должен продолжаться до тех пор, пока функция не достигнет пустого поддерева, в которое может быть добавлен новый узел. Один из возможных способов реализации такого поиска связан с рекурсией — применением функции AddNode() к дочернему, а не корневому узлу. Рекурсивная последовательность вызовов функции завершается, когда левое или правое поддерево оказывается пустым, т.е. когда root->left или root->right равно NULL. Имейте в виду, что root — это указатель на верхушку текущего поддерева, поэтому в каждом рекурсивном вызове он указывает на новое, расположенное на более низком уровне, поддерево. (Рекурсия обсуждалась в главе 9.)

Функции ToLeft() и ToRight() зависят от сущности типа Item. Члены клуба Nerfville Pet Club будут упорядочены в алфавитном порядке по кличкам. Если двое животных имеют одинаковые клички, они должны быть упорядочены по виду. Если их вид также совпадает, то два элемента являются дубликатами, что в базовом дереве поиска не допускается. Вспомните, что функция strcmp() из стандартной библиотеки С возвращает отрицательное число, если строка, представленная ее первым аргументом, предшествует строке во втором аргументе, ноль, если обе строки совпадают, и положительное число, если первая строка следует за второй. Функция ToRight() содержит аналогичный код. Использование этих двух функций вместо выполнения срав-

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

нений непосредственно в AddNode() упрощает адаптацию кода к новым требованиям. Вместо того чтобы переписывать функцию AddNode(), когда требуется другая форма сравнения, достаточно модифицировать функции ToLeft() и ToRight().

static bool ToLeft(const Item * il, const Item * 12)

{

int compl;

if ((compl = strcmp(il->petname, i2->petname)) < 0) return true; else if (compl == 0 &&

strcmp(il->petkind, i2->petkind) < 0 ) return true; else

return false;

}

Поиск элемента

В трех функциях интерфейса — Addltem(), InTree() и Deleteltem() — предусмотрен поиск в дереве конкретного элемента. В рассматриваемой реализации для этого используется функция Seekltem(). С функцией Deleteltem() связано дополнительное требование: она должна знать родительский узел удаляемого элемента, чтобы дочерний указатель родительского узла можно было обновить, когда удаляется дочерний элемент. Таким образом, функция Seekltem() спроектирована так, чтобы возвращать структуру, содержащую два указателя: один указывает на узел, который содержит искомый элемент (NULL, если элемент не найден), а другой указывает на родительский узел (NULL, если данный узел является корневым и не имеет родительского узла). Тип структуры определен следующим образом:

typedef struct pair {

Trnode * parent;

Trnode * child;

} Pair;

Функцию Seekltem() можно реализовать рекурсивно. Однако чтобы ознакомить вас с разными приемами программирования, для нисходящего обхода дерева мы применим цикл while. Подобно AddNode(), для навигации по дереву функция Seekltem() использует ToLeft() и ToRight(). Первоначально Seekltem() устанавливает указатель look.child так, чтобы он ссылался на корень дерева, а затем, по мере прохода по пути к возможному местонахождению элемента, переустанавливает этот указатель на последующие поддеревья. Одновременно указатель look.parent устанавливается для ссылки на последующие родительские узлы. Если подходящего элемента не найдено, значением указателя look, child будет NULL. Если искомый элемент находится в корневом узле, look.parent равно NULL, т.к. корневой узел не имеет родительского узла. Ниже приведен код функции Seekltem().

static Pair Seekltem(const Item * pi, const Tree * ptree)

{

Pair look; look.parent = NULL; look.child = ptree->root; if (look.child == NULL)

return look; /* преждевременный возврат */ while (look.child != NULL)

{

if (ToLeft (pi, & (look.child->item) ) )

глава 17

{

look.parent = look.child; look.child = look.child->left;

}

else if (ToRight(pi, &(look.child->item)))

{

look.parent = look.child; look.child = look.child->right;

}

else /* если элемент не расположен ни слева,

ни справа, он должен быть таким же */ break; /* look.child - это адрес узла, содержащего элемент */

}

return look; /* возврат в случае успеха */

}

Обратите внимание, что поскольку функция Seekltem() возвращает структуру, ее можно применять с операцией членства в структуре. Например, в функции Addltem() используется следующий код:

if (Seekltem(pi, ptree).child != NULL)

При наличии Seekltem() написание кода функции InTree() открытого интерфейса не составит труда:

bool InTree(const Item * pi, const Tree * ptree)

{

return (Seekltem(pi, ptree).child == NULL) ? false : true;

}

Соображения по поводу удаления элемента