К двоичным деревьям применяют следующие операции:
Добавление к дереву нового элемента.
Нахождение элемента в дереве.
Удаление элемента из дерева.
Осуществление какой-либо операции с каждым хранящимся в дереве элементом. Прохождение дерева называют также
Только что описанные операции соответствуют следующим функциям:
#include
void *tsearch(const void *key, void **rootp,
int (*compare)(const void*, const void*));
void *tfind(const void *key, const void **rootp,
int (*compare)(const void*, const void*));
void *tdelete(const void *key, void **rootp,
int (*compare)(const void*, const void*));
typedef enum { preorder, postorder, endorder, leaf } VISIT;
void twalk(const void *root,
void (*action)(const void *nodep, const VISIT which,
const int depth));
void tdestroy(void *root, void (*free_node)(void *nodep)); /* GLIBC*/
Эти функции были впервые определены для System V, а теперь формально стандартизованы POSIX. Они следуют структуре других, которые мы видели в разделе 6.2 «Функции сортировки и поиска»: использование указателей void* для указания на произвольные типы данных и предоставляемые пользователем функции сравнения для определения порядка. Как и для qsort() и bsearch(), функции сравнения должны возвращать отрицательное/нулевое/положительное значение, когда key сравнивается со значением в вершине дерева.
Эти процедуры выделяют память для вершин дерева. Для их использования с несколькими деревьями нужно предоставить им указатель на переменную void*, в которую они заносят адрес корневой вершины. При создании нового дерева инициализируйте этот указатель в NULL:
void *root = NULL; /* Корень нового дерева */
void *val; /* Указатель на возвращенные данные */
extern int my_compare(const void*, const void*); /* Функция сравнения */
extern char key[], key2[]; /* Значения для ввода в дерево */
val = tsearch(key, &root, my_compare);
/* Ввести в дерево первый элемент */
/* ...заполнить key2 другим значением. НЕ изменять корень... */
val = tsearch(key2, &root, my_compare);
/* Ввести в дерево последующий элемент */
Как показано, в переменной root должен быть NULL лишь в первый раз, после чего нужно оставить ее как есть. При каждом последующем вызове tsearch() использует ее для управления деревом.
Когда разыскиваемый key найден, как tsearch(), так и tfind() возвращают указатель на содержащую его вершину. Поведение функций различно, когда key не найден: tfind() возвращает NULL, a tsearch() вводит в дерево новое значение и возвращает указатель на него. Функции tsearch() и tfind() возвращают указатели на внутренние вершины дерева. Они могут использоваться в последующих вызовах в качестве значения root для работы с поддеревьями. Как мы вскоре увидим, значение key может быть указателем на произвольную структуру; он не ограничен символьной строкой, как можно было бы предположить из предыдущего примера.
Эти процедуры сохраняют лишь указатели на данные, использующиеся в качестве ключей. Соответственно это ваше дело управлять памятью для хранения значений данных, обычно с помощью malloc().
