5.81 Покажите, что прямой обход бора равноценен прямому обходу соответствующего бинарного дерева (см. лемму 5.4), а обратный обход бора совпадает с поперечным обходом бинарного дерева.

о 5.82 Приведите нерекурсивную реализацию поперечного обхода.

5.83 Приведите нерекурсивную реализацию обратного обхода.

5.84 Создайте программу, которая преобразует прямой и поперечный обходы бинарного дерева в обход дерева по уровням.

5.7 Рекурсивные алгоритмы бинарных деревьев

Алгоритмы обхода дерева, рассмотренные в разделе 5.6, наглядно демонстрируют необходимость рассмотрения рекурсивных алгоритмов бинарных деревьев, что обусловлено самой рекурсивной структурой этих деревьев. Для решения многих задач можно непосредственно применять рекурсивные алгоритмы типа разделяй и властвуй , которые, по существу, обобщают алгоритмы обхода деревьев. Обработка дерева выполняется посредством обработки корневого узла и (рекурсивно) его поддеревьев; вычисление можно выполнять перед, между или после рекурсивных вызовов (или же использовать все три метода).

Часто требуется определять различные структурные параметры дерева, имея только ссылку на дерево. Например, программа 5.17 содержит рекурсивные функции для вычисления количества узлов и высоту заданного дерева. Функции определяются непосредственно исходя из определения 5.6. Ни одна из этих функций не зависит от порядка обработки рекурсивных вызовов: они обрабатывают все узлы дерева и возвращают одинаковый результат, если, например, рекурсивные вызовы поменять местами. Не все параметры дерева вычисляются так легко: например, программа для эффективного вычисления длины внутреннего пути бинарного дерева является более сложной (см. упражнения 5.88-5.90).

Программа 5,17 Вычисление параметров дерева

Для выяснения базовых структурных свойств дерева можно использовать простые рекурсивные процедуры, подобные следующим.

int count(link h) {

if (h == 0) return 0;

return count(h->l) + count(h->r) + 1 ;

int height(link h) {

if (h == 0) return -1;

int u = height(h->l), v = height(h->r); if (u > v) return u+1; else return v+1 ;

Еще одна функция, которая полезна при создании программ, обрабатывающих деревья, - функция, которая выводит на печать структуру или рисует дерево. Например, программа 5.18 - рекурсивная процедура, выводящая дерево в формате, приведенном на рис. 5.29. Эту же базовую рекурсивную схему можно использовать для

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

Программа 5.18 Функция быстрого вывода дерева

Эта рекурсивная программа отслеживает высоту дерева и использует эту информацию для вывода его представления, которое можно использовать при отладке программ обработки деревьев (см. рис. 5.29). В программе предполагается, что элементы в узлах имеют тип Item, для которого определена перегруженная операция .

void printnode (Item х, int h)

{ for (int i = 0; i < h; i++) cout ; cout X endl;

void show (link t, int h) {

if (t == 0) { printnode (*, h) ; return; }

show(t->r, h+1); printnode(t->item, h); show(t->l, h+1);

РИСУНОК 5.29 ВЫВОД ДЕРЕВА (ПРИ ПОПЕРЕЧНОМ ОБХОДЕ И ПРЯМОМ ОБХОДЕ)

Вывод, приведенный на рисунке слева, получен в результате использования программы 5.18 применительно к примеру дерева, приведенному на рис. 5.26, и он демонстрирует структуру дерева аналогично использованному графическому представлению, повернутому на 90 градусов. Вывод, показанный на рисунке справа, получен в результате выполнения этой же программы при перемещении оператора вывода в начало программы; он демонстрирует структуру дерева в привычном формате.

Программа 5.18 выполняет поперечный обход, но если выводить элемент перед рекурсивными вызовами, получаем прямой обход; этот вариант также приведен на рис. 5.29. Этот формат привычен, например, при отображении генеалогического дерева, списка файлов в файловой структуре в виде дерева или при создании структуры печатного документа. Например, выполнение прямого обхода дерева, отображенного на рис. 5.19, приводит к выводу варианта таблицы оглавления этой книги.

Вначале рассмотрим пример программы, которая строит явную структуру дерева, связанного с приложением определения максимума, которая была рассмотрена в разделе 5.2. Наша цель - построение турнира - бинарного дерева, в котором элементом каждого внутреннего узла является копия большего из элементов его двух дочерних элементов. В частности, элемент в корне - копия наибольшего элемента в турнире. Элементы в листья (узлах, которые не имеют дочерних узлов) образуют представляюшие интерес данные, а остальная часть дерева - структура данных, которая позволяет эффективно находить наибольший из элементов.

Программа 5.19 - рекурсивная программа, которая строит турнир из элементов массива. Будучи расширенной версией профаммы 5.6, она использует стратегию разделяй и властвуй : чтобы построить турнир для единственного элемента, программа создает лист, содержащий этот элемент, и выполняет возврат. Чтобы посфоить турнир для > 1 элементов, в программе используется сфатегия разделяй и властвуй : программа делит все множество элементов пополам, строит турнир для каждой половины и создает новый узел со связями с двумя турнирами и с элементом, который является копией большего элемента в корнях обоих турниров.

Программа 5.19 Конструирование турнира

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

struct node { Item item; node *1, *r; node (Item x) { item = x; 1 = 0; r = 0; }

typedef node* link; link max (Item a[], int 1, int r) { int m = (l+r)/2;

link X = new node (a [m]) ;

if (1 = r) return x;

x->l = max (a, 1, m) ;

x->r = max (a, m+1, r) ;

Item u = x->l->item, v = x->r->item;

if (u > V)

x->item = u; else x->item - v;

return x;

Ha рис. 5.30 приведен пример явной структуры дерева, построенной программой 5.19. Построение таких рекурсивных структур - вероятно, предпочтительней отысканию максимума путем просмотра данных, как это было сделано в программе 5.6, поскольку структура дерева обеспечивает определенную гибкость для выполнения других операций. Важным примером служит и сама операция, использованная для построения турнира. При наличии двух турниров их можно объединить в один турнир, создав новый узел, левая связь которого указывает на один турнир, а правая на другой, и приняв больший из двух элементов (помещенных в корнях двух данных турниров) в качестве наибольшего элемента объединенного турнира. Можно также рассмотреть алгоритмы добавления и удаления элементов и выполнения других операций. Здесь мы не станем рассматривать такие операции, поскольку аналогичные структуры данных, обладающие подобной гибкостью, исследуются в главе 9.

ЙЕ-п ЕШВ ЕЕШ ШШ

РИСУНОК 5.30 ЯВНОЕ ДЕРЕВО ДЛЯ ОТЫСКАНИЯ МАКСИМУМА (ТУРНИР)

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