tsearch, tfind, tdelete, twalk - управление бинарными "деревьями"

НАЗВАНИЕ
tsearch, tfind, tdelete, twalk - управление бинарными
"деревьями"

СИНТАКСИС
#include

void *tsearch(const void *key, void **rootp,
int(*compar)(const void *, const void *));

void *tfind(const void *key, const void **rootp,
int(*compar)(const void *, const void *));

void *tdelete(const void *key, void **rootp,
int(*compar)(const void *, const void *));

void twalk(const void *root, void(*action)(const void *nodep,
const VISIT which,
const int depth));

#define _GNU_SOURCE
#include

void tdestroy (void *root, void (*free_node)(void *nodep));

ОПИСАНИЕ
Функции tsearch, tfind, twalk и tdelete позволяют
управлять бинарными "деревьями". Они были написаны по
книге профессора Knuth (6.2.2) "Algorithm Theory". Первое
поле в каждом узле "дерева" является указателем на
соответствующий элемент данных. Вызывающая программа
должна сохранить действительные данные. compar указывает
на процедуру сравнения, которая ставит указатели на два
элемента данных. Эта процедура должна возвращать
отрицательное, положительное или нулевое значение, если
первый элемент меньше, больше второго или равен ему.

tsearch производит поиск элемента данных в "дереве". key
указывает на искомый элемент. rootp указывает на
переменную, являющуюся, в свою очередь, указателем на
корень "дерева". Если "дерево" пусто, то переменная rootp
должна указывать на значение NULL. Если данные найдены, то
tsearch возвращает на них указатель. Если данные не
найдены, то tsearch добавляет их и возвращает указатель на
новый элемент.

tfind похожа на tsearch, только в случае, если элемент не
найден, возвращается значение NULL.

tdelete удаляет значение из "дерева". Аргументы аналогичны
функции tsearch.

twalk предоставляет Вам средство для последовательного
курсирования по всему "дереву". root указывает на
начальный элемент обхода. Если этот узел не является
корневым, то будет пройдена только часть дерева. twalk
вызывает пользовательскую функцию action каждому
посещаемому узлу (то есть три раза внутреннему узлу и один
- конечному узлу "листвы"). action каждый раз получает три
аргумента. Первый - указатель на посещаемый узел. Второй -
целое число, принимающее значения preorder, postorder и
endorder (в зависимости от того, в первый, второй или
третий раз посещается внутрений узел) или leaf, если это
единственый визит конечного узла. Эти символы определены в
. Третий аргумент - это глубина текущего
"погружения" в "дерево", для корня она равна нулю.

(В общем случае, функции preorder, postorder и endorder
известны как preorder, inorder и postorder: перед
посещением узлов, после первого посещения и перед вторым,
и после посещения. Таким образом, выбор имени postorder
приводит к путанице.)

Функция tdestroy() удаляет все дерево rootp, высвобождая
все ресурсы занятые функцией tsearch(). Для получения
данных о каждом узле дерева вызывается функция free_node.
Указатель на данные является аргументом функции. Функция
вызывается в любом случае.

ВОЗВРАЩАЕМОЕ ЗНАЧЕНИЕ
tsearch возвращает указатель на соответствующий элемент
дерева или добавляет элемент и возвращает указатель на
него, а также возвращает NULL, если для нового элемента
недостаточно памяти. tfind возвращает указатель на
элемент или NULL, если совпадений не найдено. Если есть
несколько элементов с одинаковым ключом, то неизвестно,
какой из них будет возвращен.

tdelete возвращает указатель на родительский элемент
удаленного элемента или NULL, если элемент не найден.

tsearch, tfind и tdelete также возвращают NULL, если rootp
- это запись, указывающая на NULL.

ПРЕДУПРЕЖДЕНИЯ
twalk ставит указатель на корневой элемент, в то время как
другие функции ставят указатель на переменную, содержащую
ссылку на корень.

twalk использует postorder, это значит "после левого
"поддерева", но перед правым "поддеревом". Некоторые
назовут это "inorder" и будут использовать "postorder",
что значит "после обоих "поддеревьев".

tdelete освобождает память, необходимую для хранения
элемента "дерева". Пользователь отвечает за освобождение
памяти, использованной для хранения соответствующих
данных.

На описанную в примере программу влияет то, что twalk не
делает различий между узлом после вызова пользовательской
функции с аргументом "endorder" или "leaf". Он работает в
соответствии с реализацией GNU-библиотеки, но может и не
работать, согласно документации SysV.

ПРИМЕР
Приведенная ниже программа вставляет двенадцать случайных
чисел в бинарное "дерево", в котором повторяющиеся числа
удаляются, а затем печатает их по порядку.

void *root=NULL;

void *xmalloc(unsigned n) {
void *p;
p = malloc(n);
if(p) return p;
fprintf(stderr, "недостаточно памяти\n");
exit(1);
}

int compare(const void *pa, const void *pb) {
if(*(int *)pa *(int *)pb) return 1;
return 0;
}

void action(const void *nodep, const VISIT which, const int depth) {
int *datap;

switch(which) {
case preorder:
break;
case postorder:
datap = *(int **)nodep;
printf("%6d\n", *datap);
break;
case endorder:
break;
case leaf:
datap = *(int **)nodep;
printf("%6d\n", *datap);
break;
}
return;
}
int main() {
int i, *ptr;
void *val;
srand(time(NULL));
for (i = 0; i < 12; i++) {
if(val == NULL) exit(1);
}
twalk(root, action);
return 0;
}

СООТВЕТСТВИЕ СТАНДАРТАМ
SVID. Функция tdestroy() явлется расширением GNU.