Осуществление какой-либо операции с каждым хранящимся в дереве элементом. Прохождение дерева называют также обходом дерева (tree walk). Есть разнообразные способы «посещения» хранящихся в дереве элементов. Обсуждаемые здесь функции реализуют лишь один из таких способов. Мы дополнительно расскажем об этом позже.
14.4.2. Функции управления деревьями
Только что описанные операции соответствуют следующим функциям:
Эти функции были впервые определены для System V, а теперь формально стандартизованы POSIX. Они следуют структуре других, которые мы видели в разделе 6.2 «Функции сортировки и поиска»: использование указателей
void*
для указания на произвольные типы данных и предоставляемые пользователем функции сравнения для определения порядка. Как и для
qsort
и
bsearch
, функции сравнения должны возвращать отрицательное/нулевое/положительное значение, когда
key
сравнивается со значением в вершине дерева.
14.4.3. Ввод элемента в дерево:
tsearch
Эти процедуры выделяют память для вершин дерева. Для их использования с несколькими деревьями нужно предоставить им указатель на переменную
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
.
ЗАМЕЧАНИЕ. Поскольку функции деревьев хранят указатели, тщательно позаботьтесь о том, чтобы не использовать
realloc
для значений, которые были использованы в качестве ключей!
realloc
может переместить данные, вернув новый указатель, но процедуры деревьев все равно сохранят висящие (dangling) указатели на старые данные.
14.4.4. Поиск по дереву и использование возвращенного указателя:
tfind
и
tsearch
Функции
tfind
и
tsearch
осуществляют поиск в двоичном дереве по данному ключу. Они принимают тот же самый набор аргументов: ключ для поиска
key
. указатель на корень дерева,
rootp
; и
compare
, указатель на функцию сравнения. Обе функции возвращают указатель на вершину, которая соответствует
key
.
Как именно использовать указатель, возвращенный
tfind
и
tsearch
? Во всяком случае, на что именно он указывает? Ответ заключается в том, что он указывает на вершину в дереве. Это внутренний тип; вы не можете увидеть, как он определен. Однако, POSIX гарантирует, что этот указатель может быть приведен к указателю на указатель на что бы то ни было, что вы используете в качестве ключа. Вот обрывочный код для демонстрации, а затем мы покажем, как это работает:
struct employee { /* Из главы 6 */
char lastname[30];
char firstname[30];
long emp_id;
time_t start_date;
};
/* emp_name_id_compare --- сравнение по имени, затем no ID */
int emp_name_id_compare(const void *e1p, const void *e2p) {
/* ...также из главы 6, полностью представлено позже... */