Практическая работа 7. Операции с деревьями. Примеры деревьев

Поиск заданной вершины в дереве.

Нерекурсивный поиск проводится следующим образом:

#define TRUE 1#define FALSE 0void Poisk (int k, node **Tree, node **Res)// Поиск вершины с ключом k в дереве (нерекурсивный алгоритм).// *Tree - указатель на вершину дерева. // *Res - указатель на найденную вершину// или на лист, если вершины в дереве нет. // B - глобальная булевская переменная: // TRUE, если вершина с ключом k в дереве найдена, // FALSE, в противном случае.{ node *p, *q; B = FALSE; p = q = *Tree; if (*Tree!=NULL)   do {     q = p;     if ((*p).Key==k) B = TRUE;     else     { q = p;       if (k<(*p).Key) p = (*p).Left;       else p = (*p).Right; }   } while (!B && p!=NULL); *Res = q;}

а рекурсивный - так:

node Poisk_1 (int k, node** Tree)// Поиск вершины с ключом k в дереве (рекурсивный алгоритм).// *Tree - указатель на вершину дерева.// Функция возвращает указатель на вершину, // содержащую ключ k.{ if (*Tree==NULL) return (NULL); else     if ((**Tree).Key==k) return (*Tree);     else {       if (k<(**Tree).Key) return Poisk_1 (k,&((**Tree).Left));       else return Poisk_1 (k,&((**Tree).Right)); }}

Д обавление вершины в дерево.

 Перед добавлением вершины в дерево обращаемся к функции Poisk (k,Tree,&r);. Если значение глобальной переменной B, которое вернула функция Poisk, равен FALSE (в дереве нет ключа, равного вновь поступающему), то вершина, после которой будет осуществляться добавление, является листом. Указатель на этот лист хранится в переменной r.

В heap -области резервируем место для динамического объекта:

s = new(node); (*s).Key = Элем; (*s).Count = 1; (*s).Left = (*s).Right = NULL;

и "подвешиваем" вершину:

*Tree = s;.

 Иначе, если вершина, после которой будем прикреплять новую, не является листом дерева, то перед "подвешиванием" определяем, в какое поддерево относительно этой вершины будет включена новая:

if (k<(*r).Key) (*r).Left = s; else (*r).Right = s;

Текст функции добавления:

void Addition (node **Tree, int k)// Добавление вершины k в бинарное дерево.// *Tree - указатель на вершину дерева.// B - глобальная булевская переменная:// TRUE, если вершина с ключом k в дереве найдена, // FALSE, в противном случае.{ node *r, *s; Poisk (k,Tree,&r); if (!B) { s = new(node); (*s).Key = k; (*s).Count = 1;     (*s).Left = (*s).Right = NULL;     if (*Tree==NULL) *Tree = s;     else       if (k<(*r).Key) (*r).Left = s; else (*r).Right = s; } else (*r).Count += 1;}

Удаления из бинарного дерева вершины с заданным ключом
различает три случая:

• вершины с заданным ключом в дереве нет;
• вершина с заданным ключом имеет не более одной исходящей дуги;
• вершина с заданным ключом имеет две исходящие дуги.

Н.Вирт отмечает: "Трудность заключается в удалении элементов с двумя потомками, поскольку мы не можем указать одной ссылкой на два направления. В этом случае удаляемый элемент нужно заменить либо на самый правый элемент его левого поддерева, либо на самый левый элемент его правого поддерева. Ясно, что такие элементы не могут иметь более одного потомка. Подробно это показано в рекурсивной процедуре, называемой Delete()..."

void Delete (node **Tree, int k)

// Удаление вершины k из бинарного дерева.// *Tree - указатель на вершину дерева.{ node *q; if (*Tree==NULL) cout<<"Вершина с заданным ключом не найдена!\n"; else     if (k<(**Tree).Key) Delete (&((**Tree).Left),k);     else       if (k>(**Tree).Key) Delete (&((**Tree).Right),k);       else {           q = *Tree;           if ((*q).Right==NULL) { *Tree = (*q).Left; delete q; }           else             if ((*q).Left==NULL) { *Tree = (*q).Right; delete q;}       else Delete_1 (&((*q).Left),&q); }}

"Вспомогательная рекурсивная процедура Delete_1() вызывается только в 3-м случае. Она "спускается" вдоль самой правой ветви левого поддерева удаляемого узла q и затем заменяет существенную информацию (ключ и счетчик) в q соответствующими значениями самой правой компоненты r этого левого поддерева, после чего от r можно освободиться..." (Н.Вирт). Освобождение памяти, занятой динамической переменной, происходит при помощи конструкции delete.

void Delete_1 (node **r, node **q){ node *s; if ((**r).Right==NULL) { (**q).Key = (**r).Key; (**q).Count = (**r).Count;*q = *r;       s = *r; *r = (**r).Left; delete s; } else Delete_1 (&((**r).Right),q);}

 

Задание 1:

 

Откомпилируйте программу, иллюстрирующую поиск заданной вершины в дереве, добавление вершины в дерево, удаление вершины из дерева. Измените в потоковых операторах вывода текст на русском языке на транслит или на английский язык.

 

#include<iostream.h>#define TRUE 1#define FALSE 0struct node{ int Key; int Count; node *Left; node *Right;}; class TREE{ private: node *Tree;//Указатель на корень дерева. node *Res;//Указатель на найденную вершину. int B; //Признак нахождения вершины в дереве. //Поиск вершины в дереве (рекурсивный алгоритм). void Search (int, node**); void Delete_1 (node**,node**); public: TREE() { Tree = NULL;} node** GetTree() {return &Tree;} void BuildTree ();//Построение бинарного дерева. //Вывод дерева на экран (рекурсивный алгоритм). void Vyvod (node**,int); //Поиск вершины в дереве (нерекурсивный алгоритм). int Poisk (int); //Поиск вершины в дереве (рекурсивный алгоритм). node *Poisk_1 (int,node **); //Добавление вершины в дерево (нерекурсивный алгоритм). void Addition (int); // Удаление вершины из дерева. void Delete (node**, int);}; void main (){ TREE A; int el; A.BuildTree (); A.Vyvod (A.GetTree(),0); cout<<"Введите ключ вершины, которую нужно найти в дереве: "; cin>>el; if (A.Poisk (el)) cout<<"В дереве есть такая вершина!\n"; else cout<<"В дереве нет такой вершины!\n"; cout<<"Введите ключ вершины, которую нужно найти в дереве: "; cin>>el; if (A.Poisk_1 (el,A.GetTree())!=NULL)     cout<<"В дереве есть такая вершина!\n"; else cout<<"В дереве нет такой вершины!\n"; cout<<"Введите ключ добавляемой вершины: "; cin>>el; A.Addition (el); A.Vyvod (A.GetTree(),0); cout<<"Введите ключ удаляемой вершины: "; cin>>el; A.Delete (A.GetTree(),el); A.Vyvod (A.GetTree(),0);} void TREE::BuildTree ()//Построение бинарного дерева.//Tree - указатель на вершину дерева.{ int el; cout<<"Вводите ключи вершин дерева: \n"; cin>>el; while (el!=0) { Search (el,&Tree);cin>>el; }} void TREE::Vyvod (node **w,int l)//Изображение дерева w на экране дисплея//    (рекурсивный алгоритм).//*w - указатель на корень дерева.{ int i; if (*w!=NULL) { Vyvod (&((**w).Right),l+1); for (i=1; i<=l; i++) cout<<" "; cout<<(**w).Key<<endl; Vyvod (&((**w).Left),l+1); }} void TREE::Search (int x,node **p)//Поиск звена x в бинарном дереве со вставкой//       (рекурсивный алгоритм).//*p - указатель на вершину дерева.{ if (*p==NULL) { // Вершины в дереве нет; включить ее. *p = new(node); (**p).Key = x; (**p).Count = 1; (**p).Left = (**p).Right = NULL; } else if (x<(**p).Key) Search (x,&((**p).Left)); else if (x>(**p).Key) Search (x,&((**p).Right)); else (**p).Count += 1;} void TREE::Addition (int k)// Поиск звена k в бинарном дереве со вставкой//    (нерекурсивный алгоритм).// Tree - указатель на вершину дерева.{ node *s; Poisk (k); if (!B) { s = new(node); (*s).Key = k; (*s).Count = 1; (*s).Left = (*s).Right = NULL; if (Tree==NULL) Tree = s; else if (k<(*Res).Key) (*Res).Left = s; else (*Res).Right = s; } else (*Res).Count += 1;} int TREE::Poisk (int k)// Поиск вершины с ключом k в дереве// (нерекурсивный алгоритм).// Tree - указатель на бинарное дерево.// Res - указатель на найденную вершину// или на лист, к которому можно присоединить новую вершину.{ node *p,*q; B = FALSE; p = Tree; if (Tree!=NULL) do { q = p; if ((*p).Key==k) B = TRUE; else {  q = p;  if (k<(*p).Key) p = (*p).Left;  else p = (*p).Right; } } while (!B && p!=NULL); Res = q; return B;} node *TREE::Poisk_1 (int k,node **p)// Поиск вершины с ключом k в дереве//   (рекурсивный алгоритм).// *p - указатель на корень дерева.{ if (*p==NULL) return (NULL); else   if ((**p).Key==k) return (*p);   else      if (k<(**p).Key) return Poisk_1 (k,&((**p).Left));      else return Poisk_1 (k,&((**p).Right));} void TREE::Delete (node **p,int k)// Удаление вершины k из бинарного дерева.// *p - указатель на корень дерева.{ node *q; if (*p==NULL) cout<<"Вершина с заданным ключом не найдена!\n"; else   if (k<(**p).Key) Delete (&((**p).Left),k);   else          if (k>(**p).Key) Delete (&((**p).Right),k);          else          {                  q = *p;               if ((*q).Right==NULL) {*p = (*q).Left; delete q;}               else                if ((*q).Left==NULL) { *p = (*q).Right; delete q; }                else Delete_1 (&((*q).Left),&q);          }} void TREE::Delete_1 (node **r,node **q){ node *s; if ((**r).Right==NULL) { (**q).Key = (**r).Key; (**q).Count = (**r).Count; *q = *r; s = *r; *r = (**r).Left; delete s; } else Delete_1 (&((**r).Right), q);}