14.4.5. Обход дерева: twalk()
14.4.5. Обход дерева: twalk()
Функция twalk() объявлена в <search.h> следующим образом:
typedef enum { preorder, postorder, endorder, leaf } VISIT;
void twalk(const void *root,
void (*action)(const void *nodep, const VISIT which,
const int depth));
Первый параметр является корнем дерева (не указателем на корень). Второй является указателем на функцию обратного вызова, которая вызывается с тремя аргументами, указателем на исследуемую вершину дерева; типом перечисления, указывающим, как осуществляется обход данной вершины; и целого, обозначающего глубину текущей вершины (корень находится на глубине 0, как объяснялось ранее).
Использование функции обратного вызова здесь такое же, как для nftw() (см. раздел 8.4.3.2 «Функция обратного вызова nftw()»). Там функция обратного вызова вызывается для каждого объекта в файловой системе. Здесь функция обратного вызова вызывается для каждого объекта, хранящегося в дереве.
Есть несколько способов прохождения, или «обхода», двоичного дерева:
• Левая вершина, родительская вершина, правая вершина.
• Родительская вершина, левая вершина, правая вершина.
• Левая вершина, правая вершина, родительская вершина.
Функция GLIBC twalk() использует второй способ: сначала родительская вершина, затем левая, затем правая. Каждый раз при встрече с вершиной говорят, что она посещается.[159] В ходе посещения порожденной вершины функция должна посетить и родительскую. Соответственно, значения типа VISIT указывают, на какой стадии произошла встреча с этой вершиной:
preorder До посещения порожденных.
postorder После посещения первой, но до посещения второй порожденной вершины.
endorder После посещения обеих порожденных.
leaf Эта вершина является концевой, не имеющей порожденных вершин.
ЗАМЕЧАНИЕ. Использованная здесь терминология не соответствует точно той, которая используется в формальных руководствах по структурированию данных. Там используются термины inorder, preorder и postorder для обозначения соответствующих трех перечисленных ранее способов прохождения дерева. Таким образом, twalk() использует прохождение по типу preorder, но использует именованные константы preorder и т.д. для обозначения того, на какой стадии была посещена вершина. Это может сбивать с толку.
Следующая программа, ch14-tsearch.c, демонстрирует построение и обход дерева. Она повторно использует структуру struct employee и функцию emp_name_id_compare() из раздела 6.2 «Функции сортировки и поиска».
1 /* ch14-tsearch.c --- демонстрация управления деревом */
2
3 #include <stdio.h>
4 #include <search.h>
5 #include <time.h>
6
7 struct employee {
8 char lastname[30];
9 char firstname[30];
10 long emp_id;
11 time_t start_date;
12 };
13
14 /* emp_name_id_compare --- сравнение по имени, затем no ID */
15
16 int emp_name_id_compare(const void *e1p, const void *e2p)
17 {
18 const struct employee *e1, *e2;
19 int last, first;
20
21 e1 = (const struct employee*)e1p;
22 e2 = (const struct employee*)e2p;
23
24 if ((last = strcmp(e1->lastname, e2->lastname)) != 0)
25 return last;
26
27 /* фамилии совпадают, проверить имена */
28 if ((first = strcmp(e1->firstname, e2->firstname)) != 0)
29 return first;
30
31 /* имена совпадают, проверить ID */
32 if (e1->emp_id < e2->emp_id)
33 return -1;
34 else if (e1->emp_id == e2->emp_id)
35 return 0;
36 else
37 return 1;
38 }
39
40 /* print_emp --- вывод структуры employee во время обхода дерева */
41
42 void print_emp(const void *nodep, const VISIT which, const int depth)
43 {
44 struct employee *e = *((struct employee**)nodep);
45
46 switch (which) {
47 case leaf:
48 case postorder:
49 printf("Depth: %d. Employee: ", depth);
50 printf(" %s, %s %d %s ", e->lastname, e->firstname,
51 e->emp_id, ctime(&e->start_date));
52 break;
53 default:
54 break;
55 }
56 }
Строки 7–12 определяют struct employee, а строки 14–38 определяют emp_name_id_compare().
Строки 40–56 определяют print_emp(), функцию обратного вызова, которая выводит struct employee наряду с глубиной дерева в текущей вершине. Обратите внимание на магическое приведение типа в строке 44 для получения указателя на сохраненные данные.
58 /* main --- демонстрация хранения данных в двоичном дереве */
59
60 int main(void)
61 {
62 #define NPRES 10
63 struct employee presidents[NPRES];
64 int i, npres;
65 char buf[BUFSIZ];
66 void *root = NULL;
67
68 /* Очень простой код для чтения данных: */
69 for (npres = 0; npres < NPRES && fgets(buf, BUFSIZ, stdin) != NULL;
70 npres++) {
71 sscanf(buf, "%s %s %ld %ld ",
72 presidents[npres].lastname,
73 presidents[npres].firstname,
74 &presidents[npres].emp_id,
75 &presidents[npres].start_date);
76 }
77
78 for (i = 0; i < npres; i++)
79 (void)tsearch(&presidents[i], &root, emp_name_id_compare);
80
81 twalk(root, print_emp);
82 return 0;
83 }
Целью вывода дерева является вывод содержащихся в нем элементов в отсортированном порядке. Помните, что twalk() посещает промежуточные вершины по три раза и что левая вершина меньше родительской, тогда как правая больше. Таким образом, оператор switch выводит сведения о вершине, лишь если which равно leaf, является концевой вершиной, или postorder, что означает, что была посещена левая вершина, а правая еще не была посещена.
Используемые данные представляют собой список президентов, тоже из раздела 6.2 «Функции сортировки и поиска». Чтобы освежить вашу память, полями являются фамилия, имя, номер сотрудника и время начала работы в виде временной отметки в секундах с начала Эпохи:
$ cat presdata.txt
Bush George 43 980013600
Clinton William 42 727552800
Bush George 41 601322400
Reagan Ronald 40 348861600
Carter James 39 222631200
Данные сортируются на основе сначала фамилии, затем имени, а затем старшинства. При запуске[160] программа выдает следующий результат:
$ ch14-tsearch < presdata.txt
Depth: 1. Employee:
Bush, George 41 Fri Jan 20 13:00:00 1989
Depth: 0. Employee:
Bush, George 43 Sat Jan 20 13:00:00 2001
Depth: 2. Employee:
Carter, James 39 Thu Jan 20 13:00:00 1977
Depth: 1. Employee:
Clinton, William 42 Wed Jan 20 13:00:00 1993
Depth: 2. Employee:
Reagan, Ronald 40 Tue Jan 20 13:00:00 1981