Поиск по дереву и использование возвращенного указателя: и

 

Функции и осуществляют поиск в двоичном дереве по данному ключу. Они принимают тот же самый набор аргументов: ключ для поиска. указатель на корень дерева,; и, указатель на функцию сравнения. Обе функции возвращают указатель на вершину, которая соответствует.

Как именно использовать указатель, возвращенный и? Во всяком случае, на что именно он указывает? Ответ заключается в том, что он указывает на вершину в дереве. Это внутренний тип; вы не можете увидеть, как он определен. Однако, POSIX гарантирует, что этот указатель может быть приведен к указателю на указатель на что бы то ни было, что вы используете в качестве ключа. Вот обрывочный код для демонстрации, а затем мы покажем, как это работает:

 

 

Как можно указатель на вершину использовать как указатель на указатель данных? Рассмотрим, как была бы реализована вершина двоичного дерева. В каждой вершине хранится по крайней мере указатель на элемент данных пользователя и указатели на потенциальные порожденные вершины справа и слева. Поэтому она должна выглядеть примерно так.

 

 

С и C++ гарантируют, что поля внутри структуры располагаются в порядке возрастания адресов. Таким образом, выражение '' истинно. Более того, адрес структуры является также адресом ее первого поля (другими словами, игнорируя проблемы типов, '').

Следовательно, концептуально '' означает:

1. является, то есть общим указателем. Это адрес внутренней вершины дерева, но это также адрес части вершины (скорее всего, другого), которая указывает на данные пользователя.

2. '' приводит адрес внутреннего указателя к нужному типу; он остается указателем на указатель, но в этот раз на. Помните, что приведение одного типа указателя к другому не изменяют значения (паттерна битов); оно меняет лишь способ интерпретации компилятором значения для анализа типов.

3. '' разыменовывает вновь созданный, возвращая годный к употреблению указатель.

4. ' сохраняет это значение в для непосредственного использования позже.

Идея проиллюстрирована на рис. 14.2.

Рис. 14.2. Вершины дерева и их указатели

Для упрощения использования возвращенного указателя вы могли бы рассмотреть определение макроса:

 

Обход дерева:

 

Функция объявлена в следующим образом:

 

 

Первый параметр является корнем дерева (не указателем на корень). Второй является указателем на функцию обратного вызова, которая вызывается с тремя аргументами, указателем на исследуемую вершину дерева; типом перечисления, указывающим, как осуществляется обход данной вершины; и целого, обозначающего глубину текущей вершины (корень находится на глубине 0, как объяснялось ранее).

Использование функции обратного вызова здесь такое же, как для (см. раздел 8.4.3.2 «Функция обратного вызова»). Там функция обратного вызова вызывается для каждого объекта в файловой системе. Здесь функция обратного вызова вызывается для каждого объекта, хранящегося в дереве.

Есть несколько способов прохождения, или «обхода», двоичного дерева:

• Левая вершина, родительская вершина, правая вершина.

• Родительская вершина, левая вершина, правая вершина.

• Левая вершина, правая вершина, родительская вершина.

Функция GLIBC использует второй способ: сначала родительская вершина, затем левая, затем правая. Каждый раз при встрече с вершиной говорят, что она посещается. [159] В ходе посещения порожденной вершины функция должна посетить и родительскую. Соответственно, значения типа указывают, на какой стадии произошла встреча с этой вершиной:

До посещения порожденных.

После посещения первой, но до посещения второй порожденной вершины.

После посещения обеих порожденных.

 Эта вершина является концевой, не имеющей порожденных вершин.

 

ЗАМЕЧАНИЕ. Использованная здесь терминология не соответствует точно той, которая используется в формальных руководствах по структурированию данных. Там используются термины inorder, preorder и postorder для обозначения соответствующих трех перечисленных ранее способов прохождения дерева. Таким образом, использует прохождение по типу, но использует именованные константы preorder и т.д. для обозначения того, на какой стадии была посещена вершина. Это может сбивать с толку.

 

Следующая программа,, демонстрирует построение и обход дерева. Она повторно использует структуру и функцию из раздела 6.2 «Функции сортировки и поиска».

 

 

Строки 7–12 определяют, а строки 14–38 определяют.

Строки 40–56 определяют, функцию обратного вызова, которая выводит наряду с глубиной дерева в текущей вершине. Обратите внимание на магическое приведение типа в строке 44 для получения указателя на сохраненные данные.

 

 

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

Используемые данные представляют собой список президентов, тоже из раздела 6.2 «Функции сортировки и поиска». Чтобы освежить вашу память, полями являются фамилия, имя, номер сотрудника и время начала работы в виде временной отметки в секундах с начала Эпохи:

Cat presdata.txt

 

Данные сортируются на основе сначала фамилии, затем имени, а затем старшинства. При запуске[160] программа выдает следующий результат:

ch14‑tsearch < presdata.txt