3.3. бинарные деревья

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

Напомним, что корнем (root) называется первый элемент дерева. Элементы данных называются узлами (node). Узлы, не имеющие наследников, называются листьями (leaf), фрагмент дерева называется поддеревом (subtree) или ветвью. Высота дерева (height) определяется количеством уровней, на которых располагаются его узлы. Для определения параметризованного класса бинарного дерева будет использоваться следующий шаблон:

template <class DataT>

class tree

{

   DataT info;         // информ. часть

   tree *left, *right; // указатели на поддеревья

   public:

               tree <DataT> *root;              //корень дерева

               tree() { root = NULL;}           //конструктор

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

               void stree(tree <DataT>*,tree <DataT>*,DataT);

               //удаление из дерева

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

               void preorder(tree <DataT>*r);          // обход прямой

               void inorder(tree <DataT>*r);           // симметричный обход

               void postorder(tree <DataT>*r);         // обратный обход

               void print_tree(tree <DataT>*r, int l); // вывод дерева

//поиск в дереве

tree <DataT> * search_tree(tree <DataT>*r, DataT key);

};

Рассмотрим функции для работы с бинарными деревьями. Каждый узел дерева будет объектом класса tree. Наличие указателя *root позволяет определить корень всего дерева, находясь в любом из его узлов.

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

//параметризованная функция добавления элемента в дерево

template <class DataT>

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

{

   if (!r)

   {

               //если в качестве дерева для вставки передан NULL то

               r = new tree <DataT>;   //выделим память

               if (!r)

               {

                           cout<< " Недостаточно памяти"; exit(1);

               }

               //создаётся новое дараво

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

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

//параметризованная функция обхода дерева в симметричном порядке

template <class DataT>

void tree <DataT>::inorder(tree <DataT> *r)

{

   if(!r) return;                                                     //если дерево пусто

   inorder (r -> left);                                            //посетим левое поддерево

   if(r -> info) cout << r -> info << " ";   //вывод элемента

   inorder (r -> right);                                          //посетим правое поддерево

}

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

Приведем соответствующие функции для обхода дерева в прямом и обратном порядках, описанные в теле класса как preorder и postorder соответственно:

//параметризованная функция обхода дерева в прямом порядке

template <class DataT>

void tree <DataT>::preorder(tree <DataT>*r)

{

   if(!r) return;                             //если дерево пусто

   if(r -> info) cout << r -> info << " ";   //вывод элемента

   preorder (r -> left);                                          //посетим левое поддерево

   preorder (r -> right);                                        //посетим правое поддерево

}

//параметризованная функция обхода дерева в обратном порядке

template <class DataT>

void tree <DataT>::postorder(tree <DataT>*r)

{

   if(!r) return;                          //если дерево пусто

   postorder (r -> left);                  //посетим левое поддерево

   postorder (r -> right);                 //посетим правое поддерево

   if (r -> info) cout << r -> info << " ";//вывод элемента

}

Для вывода дерева на экран, можно применить следующую подпрограмму, описанную в теле класса как print_tree:

//параметризированная функция печати дерева на экране

template <class DataT>

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

{

   int i;

   if(!r) return;                      //если дерево пусто

   print_tree(r -> right, l+1);        //распечатаем правое поддерево на

                                                               //l+1 уровне

   for (i = 0; i < l; i++) cout << " ";//вывод необходимого

                                                                           //количества пробелов

   cout << r -> info << endl;                   //вывод информационной части

   print_tree(r -> left, l+1);  //распечатаем правое поддерево на

                                                               //l+1 уровне

}

Для полноты приведём подпрограммы поиска элемента (search_tree) и удаления (dtree) элемента бинарного дерева.

//параметризованная функция поиска поддерева с корнем, равным key

template <class DataT>

tree <DataT> *tree<DataT>::search_tree(tree <DataT>*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;

}

Если элемент не найден, то эта подпрограмма возвратит NULL.

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

//параметризованная функция получения нового дерева из имеющегося

//путём удаления некоторого узла

template <class DataT>

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

{

   tree <DataT> *p;

   tree <DataT> *p2;                  // r - корень дерева

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

   if (r -> info == key)              //элемент это корень-?

   {

               if (r -> left == r -> right) // если 1 элемент

               {                            //вернём пустое дерево

                           if (root==r) root = NULL;

                           return NULL;           // пустое дерево

               }

               else if(r -> left == NULL)   //если левое поддерево пусто

               {

                           p = r -> right;        // нет левого поддерева

                           if (root == r) root = p;

                           return p;

               }

               else if (r -> right == NULL) //если правое поддерево пусто

               {

                           p = r -> left;         // нет правого поддерева

                           if (r == root) root = p;

                           return p;

               }

               else                       //в противном случае

               {

                           p2 = r -> right;//как минимум дерево из правого поддерева

                           p = r -> right; //правые поддеревья

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

                           p -> left = r -> left;

                           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;

   }

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

#include <iostream.h> //библиотека потокового ввода-вывода

#include <conio.h>    //библиотека консольного ввода-вывода

#include <process.h>  //необходимо для использования функции exit

template <class DataT>

class tree

{

   DataT info;         // информ. часть

   tree *left, *right; // указатели на поддеревья

   public:

               tree <DataT> *root;              //корень дерева

               tree() { root = NULL;}           //конструктор

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

               void stree(tree <DataT>*,tree <DataT>*,DataT);

               //удаление из дерева

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

               void preorder(tree <DataT>*r);          // обход прямой

               void inorder(tree <DataT>*r);           // симметричный обход

               void postorder(tree <DataT>*r);         // обратный обход

               void print_tree(tree <DataT>*r, int l); // вывод дерева

//поиск в дереве

tree <DataT> * search_tree(tree <DataT>*r, DataT key);

};

//параметризованная функция добавления элемента в дерево

template <class DataT>

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

{

   if (!r)

   {

               //если в качестве дерева для вставки передан NULL то

               r = new tree <DataT>;   //выделим память

               if (!r)

               {

                           cout<< " Недостаточно памяти"; exit(1);

               }

               //создаётся новое дараво

               r -> left = 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>::inorder(tree <DataT> *r)

{

   if(!r) return;                                                     //если дерево пусто

   inorder (r -> left);                                            //посетим левое поддерево

   if(r -> info) cout << r -> info << " ";   //вывод элемента

   inorder (r -> right);                                          //посетим правое поддерево

}

//параметризованная функция обхода дерева в прямом порядке

template <class DataT>

void tree <DataT>::preorder(tree <DataT>*r)

{

   if(!r) return;                             //если дерево пусто

   if(r -> info) cout << r -> info << " ";   //вывод элемента

   preorder (r -> left);                                          //посетим левое поддерево

   preorder (r -> right);                                        //посетим правое поддерево

}

//параметризованная функция обхода дерева в обратном порядке

template <class DataT>

void tree <DataT>::postorder(tree <DataT>*r)

{

   if(!r) return;                          //если дерево пусто

   postorder (r -> left);                  //посетим левое поддерево

   postorder (r -> right);                 //посетим правое поддерево

   if (r -> info) cout << r -> info << " ";//вывод элемента

}

//параметризованная функция печати дерева на экране

template <class DataT>

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

{

   int i;

   if(!r) return;                      //если дерево пусто

   print_tree(r -> right, l+1);        //распечатаем правое поддерево на

                                                               //l+1 уровне

   for (i = 0; i < l; i++) cout << " ";//вывод необходимого

                                                                           //количества пробелов

   cout << r -> info << endl;                   //вывод информационной части

   print_tree(r -> left, l+1);  //распечатаем правое поддерево на

                                                               //l+1 уровне

}

//параметризованная функция поиска поддерева с корнем, равным key

template <class DataT>

tree <DataT> *tree<DataT>::search_tree(tree <DataT>*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;

}

//параметризованная функция получения нового дерева из имеющегося

//путём удаления некоторого узла

template <class DataT>

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

{

   tree <DataT> *p;

   tree <DataT> *p2;                  // r - корень дерева

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

   if (r -> info == key)              //элемент это корень-?

   {

               if (r -> left == r -> right) // если 1 элемент

               {                            //вернём пустое дерево

                           if (root==r) root = NULL;

                           return NULL;           // пустое дерево

               }

               else if(r -> left == NULL)   //если левое поддерево пусто

               {

                           p = r -> right;        // нет левого поддерева

                           if (root == r) root = p;

                           return p;

               }

               else if (r -> right == NULL) //если правое поддерево пусто

               {

                           p = r -> left;         // нет правого поддерева

                           if (r == root) root = p;

                           return p;

               }

               else                       //в противном случае

               {

                           p2 = r -> right;//как минимум дерево из правого поддерева

                           p = r -> right; //правые поддеревья

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

                           p -> left = r -> left;

                           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;

   }

int main(void)

{

   char stemp[80];                       //символьная строка

   int i=0;                //счётчик

   tree <char> ch;         //дерево

   tree <char> *ch1;       //указатель на дерево

   ch1=new tree <char>;    //выделим память для дерева

   clrscr();               //очистим экран

   cout << "Введите строку (она должна завершаться точкой):";

   cin >> stemp;

   do

   {

   //пока не встретилась точка, вставляем каждый элемент строки

   //в дерево ch

               if (stemp[i]!='.') ch.stree(ch.root, NULL, stemp[i]);

               i++;

   }

   while (stemp[i] != '.');

cout <<"Обход первоначального дерева в прямом порядке: ";

ch.preorder(ch.root);

cout <<' ';

cout <<"Обход первоначального дерева в обратном порядке: ";

ch.postorder(ch.root);

cout <<' ';

cout <<"Обход первоначального дерева в симметричном порядке: ";

ch.inorder(ch.root);

ch1->root=ch.dtree(ch.root,stemp[0]); //получение нового дерева

cout <<' ';

cout <<"Обход дерева в прямом порядке после удаления первого введённого элемента: ";

ch1->preorder(ch1->root);

cout <<' ';

cout <<"Печать окончательного вида дерева: ";

ch.print_tree(ch.root,0);

return 0;

}

Результат работы программы

Введите строку (она должна завершаться точкой):123321453754.

Обход первоначального дерева в прямом порядке:

1 2 1 3 2 3 4 3 5 4 7 5

Обход первоначального дерева в обратном порядке:

1 2 3 4 5 7 5 4 3 3 2 1

Обход первоначального дерева в симметричном порядке:

1 1 2 2 3 3 3 4 4 5 5 7

Обход дерева в прямом порядке после удаления первого введённого элемента:

2 1 3 2 3 4 3 5 4 7 5

Печать окончательного вида дерева:

     7

      5

    5

     4

   4

    3

  3

 3

  2

2

 1