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

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

Построение дерева. Дерево строится в соответствии с главным правилом. Например, пусть дана следующая последовательность целых чисел {5, 2, 8, 7, 2, 9, 1, 5}. Первое число 5 будет записано в корень дерева (см. рисунок 16, а). Второе число 2 меньше значения в корне дерева, следовательно, оно будет записано в левое поддерево (см. рисунок 16, б). Следующее число 8 больше значения в корне, соответственно оно будет записано в правое поддерево (см. рисунок 16, в). Следующее число 7, больше, чем значение в корне дерева, значит, оно должно быть записано в правое поддерево, но правое поддерево уже построено. Сравниваем 7 со значением в корне правого поддерева – числом 8. Так как добавляемое значение меньше значения в корне правого поддерева, то добавляем левое поддерево уже к этому корню (см. рисунок 16, г). 

Полностью сформированное бинарное дерево представлено на рисунке 16, д.

 

Рисунок 16 - Процесс построения сортированного бинарного дерева: первые шаги (а-г) и окончательный вариант (д)

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

Описание элемента бинарного дерева

Struct top_ptr

{ int value;

top_ptr * left;

top_ptr * right;

};

Описание переменных для обработки

int next_number;   // Добаляемое число

top_ptr * r,*pass;;   // Адрес корня дерева, и адрес текущей вершины для добавления

 

Создание вершины

pass=new top_ptr;   // Выделяем память под новую вершину

pass->value=next_number; // Заполняем поле новой вершины новым числом

pass->left=NULL; //  Указатель на левое поддерево

 pass->right=NULL; // Указатель на правое поддерево

Add(&r,pass);         // Вызываем процедуру добавления новой вершины

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

void Add(top_ptr **r,top_ptr *pass)

{

top_ptr * rr;

rr=*r;

if(rr==NULL) *r=pass;

else

  if (pass->value<rr->value)

   Add(&rr->left,pass);

еlse

   Add(&rr->right,pass);

}

 Поиск вершины в сортированном бинарном дереве. Поиск в сортированном бинарном дереве осуществляется следующим образом: вначале значение ключа поиска сравнивается со значением в корне. Если значение ключа в искомой вершине меньше, чем в корневой, то поиск переходит в левую ветвь. Если больше или равно – то в правую ветвь. И так в каждой следующей вершине до тех пор, пока не отыщется искомая. Так, для предыдущего варианта последовательности,  поиск вершины с ключом 7 будет выполнен за три шага (см. рисунок 17).

Рисунок 17 -  Пример поиска в бинарном дереве

 

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

Поиск вершины также можно осуществлять, используя рекурсию. Для удобства использования построим рекурсивную функцию, которая будет возвращать true, если элемент найден и false – в противном случае. Адрес найденного элемента будем возвращать в параметре pass. Ниже приведен текст функции поиска вершины.

bool Find(top_ptr*r,top_ptr **pass, int n)

{ if (r==NULL) return false; //значение не найдено

    else

     if (n==r->value)

     { *pass=r;   // запомнили адрес

     return true; //значение найдено

     }

       else 

          if (n<r->value)

              return Find(r->left,pass,n); // влево

          else

     return Find(r->right,pass,n); //вправо

}

Вызывать такую функцию можно непосредственно в выражении условия оператора условной передачи управления или операторов циклов, например:

if ( Find (r,&pass,n)) < вершина найдена, адрес в pass;

              else < вершина не найдена >...

while ( Find (r,&pass,n)) <пока вершина не найден>;

Удаление вершины с указанным ключом. Удалению вершины с указанным ключом предшествует ее поиск (см. выше). Непосредственное удаление вершины реализуется в зависимости от того, какая вершина удаляется:

а) удаляемая вершина не содержит поддеревьев (лист): просто удаляем ссылку на вершину из корня соответствующего поддерева (см. рисунок 18, б);

Рисунок 18 -  Удаление листа: поиск удаляемой вершины (а), удаление вершины (б)

б) удаляемая вершина содержит одну ветвь: для удаления необходимо скорректировать соответствующую ссылку в корне, заменив адрес удаляемой вершины адресом вершины, из нее выходящей (см. рисунок 19, б);

 

Рисунок 19 - Удаление корня с одним поддеревом: поиск удаляемой вершины (а), удаление вершины (б)

в) удаляемая вершина содержит две ветви: в этом случае нужно найти подходящую вершину, которую можно вставить на место удаляемой, причем эта подходящая вершина должна легко перемещаться. Такая вершина всегда существует: это либо самый правый  элемент левого поддерева, либо самый левый элемент правого поддерева удаляемой вершины (см. рисунок 20, б).

Рисунок 20 - Удаление корня с двумя поддеревьями: поиск удаляемой вершины и вершин-кандидатов на замещение (а), замена вершины самой правой вершиной левого поддерева (б), замена вершины самой левой вершиной правого поддерева (в)

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

Ниже представлена рекурсивная процедура удаления вершины с указанным значением. Параметры: r - адрес корня дерева, k – значение в удаляемой вешине.

// Основная процедура удаления

void udaldr(top_ptr **d,int k)

{ top_ptr *q;

     top_ptr * dd=*d;

if (*d==NULL) // Первый случай – дерево пусто или вершина не найдена

puts(" Element not found or tree is empty");

else // Вершина есть - ищем ее

if (k<dd->value) udaldr(&dd->left,k);

else

  if (k>dd->value) udaldr(&dd->right,k);

  else { // Элемент найден - удаляем его

     q=*d; // Второй случай

     if (q->right==NULL){ *d=q->left;delete q;}

     else

        if (q->left==NULL){*d=q->right;delete q;}

       else // Третий случай удаления

         ud(&q->left,&q); // удаление вершины q)

      }

 }

//  Вспомогательная процедура удаления,

// вызывается из основной процедуры удаления

void ud(top_ptr **r,top_ptr **q)

{ top_ptr * rr;

if((*r)->right==NULL)

{

(*q)->value=(*r)->value;

 *q=*r;

  rr=*r;

  (*r)=(*r)->left;

   delete rr;

}

else

ud(&((*r)->right),q);

}

Сортировка с использованием дерева. Так как дерево формируется по определенным выше правилам, то сортировка по возрастанию осуществляется обходом дерева «слева направо». В литературе его еще называют «симметричным». Обход начинается с самого нижнего левого листа или, если такого листа нет, корня. Вывод значений выполняется в следующем порядке: сначала выводится значение самого нижнего левого поддерева, затем корня, затем самого нижнего левого поддерева правого поддерева и т.д. (см. рисунок 21).

 

Рисунок 21 - Обход дерева «слева направо»

 

Пример 14.  Разработать программу сортировки заданной последовательности целых чисел с использованием сортированного бинарного дерева.

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

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

Обход дерева «слева направо»  также будем осуществлять рекурсивно.

Полностью текс программы приведен ниже.

#include "stdafx.h"

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

#define lim 100 // Описание максимальной глубины дерева

// Описание вершины дерева

Struct top_ptr

{int value;

top_ptr * left;

top_ptr * right;};

// Описание переменных программы

int next_number;

top_ptr * r,*pass;

// Процедура добавления вершины к дереву

void Add(top_ptr **r,top_ptr *pass)

{ top_ptr * rr;

rr=*r;

if(rr==NULL) *r=pass;

Else

if (pass->value<rr->value)

 Add(&rr->left,pass);

Еlse

Add(&rr->right,pass);

}

// Процедура обхода дерева

void Tree(top_ptr *r)

{

if(r!=NULL)

{

Tree(r->left);

printf("%4d",r->value);

Tree(r->right);

}

}

// Основная программа

int main(int argc, char* argv[])

{ r=NULL;

puts("input number or 1000 for end");

scanf("%d",&next_number);

while(next_number!=1000)

{

pass= new top_ptr;

pass->value=next_number;

pass->left=NULL;

pass->right=NULL;

Add(&r,pass);

scanf("%d",&next_number);

}

puts(" == Result==");

Tree(r);

printf("\n");

return 0;

}

Как показывает опыт, использование сортированных бинарных деревьев достаточно эффективно с точки зрения временных оценок. А применение рекурсивных процедур упрощает процесс программирования.

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

Одним из способов разбора выражения является представление его в виде дерева. При этом каждое поддерево этого дерева отображает одну операцию выражения в порядке убывания приоритета операции. В корнях такого дерева хранится знак операции, а каждое поддерево представляет собой операнд.

Выводы

1. Рекурсию следует использовать тогда, когда рекурсивный алгоритм значительно проще нерекурсивного.

2. При использовании рекурсии следует обязательно проверять наличие и правильность условия выхода из рекурсии.

3. Не следует забывать о необходимости оценки размера фрейма активации и соотношения этой оценки с размером стека (с учетов развертывания рекурсии).