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

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг

Обход чертежа

Из книги AutoCAD 2009 для студента. Самоучитель автора Соколова Татьяна Юрьевна


Обход чертежа

Из книги AutoCAD 2009. Начали! автора Соколова Татьяна Юрьевна

Обход чертежа Команда 3DWALK интерактивно меняет вид трехмерного чертежа, при этом кажется, что наблюдатель обходит модель. Команда вызывается из падающего меню View ? Walk and Fly ? Walk или щелчком на пиктограмме Walk на плавающей панели инструментов Walk and Fly или 3D Navigation.Обход всей


6.2.3. Обход диапазона

Из книги Программирование на языке Ruby [Идеология языка, теория и практика применения] автора Фултон Хэл

6.2.3. Обход диапазона Обычно диапазон можно обойти. Для этого класс, которому принадлежат границы диапазона, должен предоставлять осмысленный метод succ (следующий).(3..6).each {|x| puts x } # Печатаются четыре строки                          # (скобки обязательны).Пока все хорошо. И


8.1.18. Обход массива

Из книги Разработка приложений в среде Linux. Второе издание автора Джонсон Майкл К.

8.1.18. Обход массива Как и следовало ожидать, в классе Array есть стандартный итератор each. Но имеются и другие полезные итераторы.Метод reverse_each обходит массив в обратном порядке. Результат такой же, как если бы мы вызвали сначала метод reverse, а потом each, но работает быстрее.words =


8.2.5. Обход хэша

Из книги Быстрые деньги в Интернете [50 способов заработать, сидя дома у компьютера] автора Парабеллум Андрей Алексеевич

8.2.5. Обход хэша В классе Hash имеется стандартный итератор each, а кроме него итераторы each_key, each_pair и each_value (each_pair — синоним each).{"а"=>3, "b"=>2}.each do |key, val| print val, " из ", key, "; " # 3 из a; 2 из b;endОстальные два итератора передают в блок только ключ или только значение:{"а"=>3,"b"=>2}.each_key do


10.1.30. Обход каталога

Из книги AutoCAD 2009. Учебный курс автора Соколова Татьяна Юрьевна

10.1.30. Обход каталога Метод класса foreach — это итератор, который последовательно передает в блок каждый элемент каталога. Точно так же ведет себя метод экземпляра each.Dir.foreach("/tmp") { |entry| puts entry }dir = Dir.new("/tmp")dir.each { |entry| puts entry }Оба фрагмента печатают одно и то же (имена всех файлов и


11.3.11. Обход пространства объектов

Из книги AutoCAD 2008 для студента: популярный самоучитель автора Соколова Татьяна Юрьевна

11.3.11. Обход пространства объектов Система исполнения Ruby должна отслеживать все известные объекты (хотя бы для того, чтобы убрать мусор, когда на объект больше нет ссылок). Информацию о них можно получить с помощью метода ObjectSpace.each_object.ObjectSpace.each_object do |obj| printf "%20s: %s ", obj.class,


14.7.2. Обход дерева файлов с помощью nft()

Из книги Linux программирование в примерах автора Роббинс Арнольд

14.7.2. Обход дерева файлов с помощью nft() Новая версия ftw() — nftw() — решает неоднозначность символических ссылок, присущих ftw(), и содержит несколько дополнительных свойств. С целью правильного определения nftw() заголовочными файлами значение _XOPEN_SOURCE в приложении должно быть


Обход в ширину, симметричный обход и обход в глубину

Из книги автора

Обход в ширину, симметричный обход и обход в глубину Прежде чем приступить к описанию остальных трех алгоритмов обхода, которые взаимосвязаны, приведем несколько иное определение бинарного дерева. Бинарное дерево состоит из корневого узла, содержащего указатели на


Обход по уровням

Из книги автора

Обход по уровням Мы еще не рассматривали обход по уровням, при котором вначале посещается корневой узел, затем слева направо посещаются два возможных узла на первом уровне, затем слева направо четыре возможных узла на втором уровне и т.д. Этот метод обхода кажется слишком


Обход чертежа

Из книги автора

Обход чертежа Команда 3DWALK интерактивно меняет вид трехмерного чертежа, при этом кажется, что наблюдатель обходит модель. Команда вызывается из падающего меню View ? Walk and Fly ? Walk или щелчком на пиктограмме Walk на плавающей панели инструментов Walk and Fly или 3D Navigation.Обход всей


Обход чертежа

Из книги автора

Обход чертежа Команда 3DWALK интерактивно меняет вид трехмерного чертежа, при этом кажется, что наблюдатель обходит модель. Команда вызывается из падающего меню View ? Walk and Fly ? Walk или щелчком на пиктограмме Walk плавающей панели инструментов Walk and Fly или 3D Navigation.Обход всей


14.4.6. Удаление вершины дерева и удаление дерева: tdelete() и tdestroy()

Из книги автора

14.4.6. Удаление вершины дерева и удаление дерева: tdelete() и tdestroy() Наконец, вы можете удалить элементы из дерева и, на системах GLIBC, удалить само дерево целиком:void *tdelete(const void *key, void **rootp,int (*compare)(const void*, const void*));/* Расширение GLIBC, в POSIX нет: */void tdestroy(void *root, void (*free_node)(void *nodep));Аргументы