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

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

Построение дерева. Дерево строится в соответствии с главным правилом. Например, пусть дана следующая последовательность целых чисел {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. Не следует забывать о необходимости оценки размера фрейма активации и соотношения этой оценки с размером стека (с учетов развертывания рекурсии).

 

Задания для самопроверки

Задание 1. Разработайте программу, которая обеспечивает быстрый поиск информации о сотрудниках фирмы с использованием бинарных деревьев: имя, фамилия, отчество, отдел, должность, служебный телефон, домашний адрес и телефон. Определите, во сколько раз быстрее в среднем будет выполняться поиск информации по сравнению с последовательным поиском, если количество сотрудников фирмы 10, 100, 1000 человек.

Задание 2. Для программы предыдущего задания оцените объем оперативной памяти, необходимой для размещения информации о 300 сотрудниках фирмы. Определите долю памяти, отводимой для хранения адресов элементов.

4 Контрольные вопросы

1. Дайте определение рекурсии. Из каких двух частей состоит рекурсивное утверждение?

2. Что такое взаиморекурсия? Как программно ее можно реализовать?

3. Что такое активация рекурсивной программы и фрейм активации? Как он влияет на емкостную сложность программы? Чем опасен большой объем фрейма активации?

4. Как рассчитать объем фрейма активации? Как можно уменьшить фрейм активации?

5. Дайте описание структуры рекурсивной программы.

6. Какова особенность выполнения операторов до и после рекурсивного вызова?

7. Что такое линейная и древовидная рекурсия? Особенности спуска и подъема каждой их этих разновидностей рекурсий.

8. Что такое полный и ограниченный перебор?

9. Особенности задач полного перебора.

10. Способы уменьшения количества рассматриваемых вариантов при полном переборе.

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

       12. Дайте определение бинарного дерева.

        13. Чем отличается рекурсивная процедура построения бинарного дерева?

        14. В чем особенности процедуры удаления вершины бинарного дерева?

 

 

ЗАКЛЮЧЕНИЕ

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

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

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

Рассмотренные материалы помогут студентам выполнять лабораторные работы, домашние задания и контрольные работы по теме «разработка рекурсивных программ»  по дисциплине «Информатика».

 

 

СПИСОК ЛИТЕРАТУРЫ

1. Г.С. Иванова, Т.Н. Ничушкина, Р.С. Самарев. Средства процедурного программирования Microsoft Visual С++ 2008. Учебное пособие. – М.: Издательство МГТУ им. Н.Э. Баумана, 2011.

2. В.В. Подбельский.  Язык С++: Учеб. пособие. – М.: Финансы и статистика, 2006.

3. Г.С. Иванова. Программирование. Учебник для ВУЗов. – М.: Кнорус, 2013.- 432 с.

4. Г.С. Иванова. Технология программирования. Учебник для ВУЗов. – М.: Кнорус, 2013. – 336 с.

5. Н.Вирт. Алгоритмы и структуры данных: перевод с англ. – М.: ДМК Пресс, 2011. – 272 с.

6. Pollice G., Selkow S., George T. Heineman. Algorithms in a Nutshell: O'ReillyMedia Inc., 2008 – 358 p.

7. Steven S Skiena, The Algorithm Design Manual: Springer Science & Business Media, 2009 - 77 p.

8. Программирование на С и С++. [Электронный ресурс] Электрон. текстовые дан. – Онлайн справочник программиста на С и С++. – Режим доступа: http://www.c-cpp.ru/books/rekursiya