Глава_02

Назад | Начало урока | Вперед
Содержание

Глава 2 (продолжение 1)

Бинарные деревья

Параметризованный класс дерева
Добавление элементов в дерево
Прохождение дерева
Поиск по дереву
Удаление элемента дерева
Рекомендации для самостоятельной разработки

Параметризованный класс дерева

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

template <class DataT> class tree{



  DataT info;

  tree *left;

  tree *right;


public:


  tree *root;

  tree(){root = NULL;}


  void stree(tree *r,tree *previous,DataT info);

  tree *dtree(tree *r,DataT key);

  void preorder(tree *r);

  void inorder(tree *r);

  void postorder(tree *r);

  void print_tree(tree *r,int l);

  tree *seach_tree(tree &r,DataT key);

Каждый узел дерева будет представлять собой объект типа tree.
Член info будет содержать информацию, хранящуюся в каждом из узлов.
Для каждого из объектов left будет представлять собой указатель на левое
поддерево, right -указатель на правое поддерево, а root _ указатель
на корень всего дерева. Обратите внимание указатель root не является
необходимым (указатель на корень дерева можно хранить в любом другом месте),
но включен для удобства. Его наличие позволяет определить начало всего
дерева ,находясь в любом из его узлов. В некоторых случаях эта возможность
может оказаться очень удобной.

Вверх

Добавление элементов в дерево

Для включения в состав дерева новых элементов используется функция stree()
приведенная ниже :

template <class DataT> void tree<DataT> :: stree( tree *r,tree *previous,DataT info) {



   if(!r) {

     r = new tree;

     if(!r) {
         cout<<"Nedostatochno pamyaty \n";

         exit(1);

     }

     r->left = NULL;

     r->right = NULL;

     r->info = info;

     if(!root) root = r; //первый элемент
     else{
        if(info < previous->info) previous->left = r;

        else previous->right = r;

     }

     return;

   }

   if(info < r->info)

        stree(r->left,r,info);

   else

        stree(r->right, r, info)

Эта функция вставляет объект в бинарное дерево, отслеживая ссылки на
элементы дерева и перемещаясь влево и вправо, в зависимости от содержимого
поля info, до тех пор, пока для элемента не будет найдено соответствующее
ему место в иерархии дерева. Функция stree() представляет собой
рекурсивный алгоритм, как и большинство процедур, связанных с деревьями.

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

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

Вверх

Прохождение дерева

Для прохождения дерева, построенного с помощью функции styree(),
с последующей распечаткой поля info каждого из узлов этого дерева
можно использовать нижеприведенную функцию inorder() :

template <class DataT> void tree<DataT> :: inorder(tree *r) {


   if(!r) return;


   inorder(r->left);

   if(r->info) cout<<r->info<<"  ";

   inorder(r->right);

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

Ниже приведены соответствующие функции для прохождения дерева в нисходящем
и восходящем порядках :

template <class DataT> void tree <DataT> ::preorder(tree *r) {


   if(!r) return;


   if(r->info) cout<<r->info<<"  ";

   preorder(r->left);

   preorder(r->right);

}



template <class DataT> void tree <DataT> ::postorder(tree *r)
{

   if(!r) return;


   postorder(r->left);

   postorder(r->right);

   if(r->info) cout<<r->info<<"  ";

}

Теперь рассмотрим короткую но интересную программу, которая строит
отсортированное дерево, а затем обходит его в последовательном
порядке и выводит на экран. Для того, чтобы программа могла осуществлять
вывод на экран, требуется лишь незначительная модификация функции inorder().
Для того, чтобы распечатанное дерево правильно выглядело на экране,
правое поддерево должно распечатываться раньше левого.(Технически это -
противоположность последовательному прохождению дерева).
Эта новая функция называется print_tree() и приведена ниже :

template <class DataT> void tree<DataT> :: print_tree(tree *r,int l) {


   int i;


   if(!r) return;


   print_tree(r->right,l+1);

   for(i=0; i<l; ++i) cout <<"  ";

   cout<<r->info<<endl;

   print_tree(r->left,l+1);

Ниже приведен полный листинг программы отображения дерева.
Для того, чтобы хорошо понять принцип ее работы, попробуйте вводить
разнообразные деревья.

//программа вывода бинарного дерева

#include<iostream.h> #include<stdlib.h>

template <class DataT> class tree{


  DataT info;
  tree *left;
  tree *right;
public:
  tree *root;
  tree(){root = NULL;}
  void stree(tree *r,tree *previous,DataT info);

  void print_tree(tree *r,int l);

}


template <class DataT> void tree<DataT> :: stree(

        tree *r,tree *previous,DataT info)
{


   if(!r) {

     r = new tree;
     if(!r) {
         cout<<"Nedostatochno pamyaty \n";

         exit(1);

     }

     r->left = NULL;

     r->right = NULL;

     r->info = info;

     if(!root) root = r; //первый элемент
     else{
        if(info < previous->info) previous->left = r;

        else previous -> right = r;

     }

     return;

   }

   if(info< r->info)

        stree(r->left,r,info);

   else

        stree(r->right, r, info)

}



//отображение дерева

template <class DataT> void tree<DataT> :: print_tree(tree *r,int l)
{

   int i;

   if(!r) return;

   print_tree(r->right,l+1);

   for(i=0; i<l; ++i) cout <<"  ";

   cout<<r->info<<endl;

   print_tree(r->left,l+1);

}



main()

{


char s[80];
tree<char> chTree;
do{

cout<<"Vvedite simvol (tochku dlya ostanova) : ";

cin >> s;

if(*s!='.') chTree.stree(chTree.root,NULL,*s);

}while (*s!='.');


chTree.print_tree(chTree.root,0);

return 0;

}

Несколько раз выполнив эту программу, вы заметите что некоторые деревья
сбалансированы - каждое их поддерево имеет такую же или почти такую же
высоту, как и любое другое в то время как другие деревья чрезвычайно
далект от этого. Фактически если вы введете следующее дерево :
a,b,c,d ,оно будет выглядеть примерно так же как на рисунке.
Ни каких левых поддеревьев в этом случае не появится. Такое дерево называется
вырожденным (degenerate tree), так как фактически оно выродилось в линейный
список.

.-.-.-.-.

Вверх

Поиск по дереву

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

template <class DataT> tree<DataT>*tree<DataT> :: search_tree(tree *r,DataT key) {


   if(!r) return r; // пустое дерево
   while(r->info !=key) {
       if(key < r->info) r = r->left;

       else r = r->right;

       if(r==NULL) break;

    }

  return r;

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

Вверх

Удаление элемента дерева

К сожалению удаление узла из дерева не столь простой процесс, как
поиск по дереву. Удаленный узел может быть корневым, левым или правым.
Кроме того узел может давать начало другим поддеревьям (их может быть
от 0 до 2).Процесс переприсваивания значений указателям представляет
собой рекурсивный алгоритм, приведенный ниже.

template <class DataT> tree<DataT> *tree<DataT> :: dtree(tree *r,DataT key) {


  tree *p, *p2;

 if(!r) return r; //элемент не найден

 if(r->info==key) {
 //delete root this means an empty tree

     if(r->left==r->right) {

     free(r);
     if(r==root) root = NULL;
     return NULL;
}



      else if(r->left==NULL) {

         p = r->right;
         free (r);
         if(r==root) root = p;
         return p;
     }


      else if(r->right==NULL) {

         p = r->left;
         free (r);
         if(r==root) root = p;
         return p;
     }


      else {

         p2 = r->right;
         p  = r->right;

         while(p->left) p = p->left;

         p->left = r->left;

         free(r);

         if(r==root) root = p2;

         return p2;

    }


  }


if(r->info<key) r->right = dtree(r->right,key);

else r->left = dtree(r->left.key);

return r;

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

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

Вверх

Рекомендации для самостоятельной разработки

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

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

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

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

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

Назад | Начало урока | Вверх | Вперед
Содержание