ОБРАТНЫЙ ОБХОД

⇐ ПредыдущаяСтр 2 из 2

ОБРАТНЫЙ ОБХОД

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

обойдите левое поддерево;
посетите корень дерева;
обойдите правое поддерево.

Применяя этот алгоритм к бинарным деревьям I, II, обойдем вершины в следующем порядке:

Рис.1. Примеры бинарных деревьев

происходит в следующем порядке:

M D N B E A C

D B E C R

Запишем алгоритм в виде рекурсивной функции:

void ObhodBack (node **w)// Обратный обход бинарного дерева.// *w - указатель на корень дерева.{ if (*w!=NULL) { ObhodBack (&((**w).Left)); cout<<(**w).Key<<" "; ObhodBack (&((**w).Right)); }}

АЛГОРИТМ ВЫВОДА БИНАРНОГО ДЕРЕВА.

Алгоритм, связанный с изображением дерева на экране дисплея. Для этого используется обход дерева, который мы назовем обратным обратному.

Взгляните на приведенную ниже функцию:

void 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); }}

Замечание! Само дерево "лежит на левом боку". Сначала выводится правое поддерево, причем очередная вершина "отступает" от левого края окна на величину, равную глубине вершины (расстояние от корня до этой вершины). Этот отступ реализуется циклом:

Приведем пример программы, иллюстрирующей рассмотренные алгоритмы.

struct node{ int Key; int Count; node *Left; node *Right;}; class TREE{ private: node *Tree; //Указатель на корень дерева. void Search (int,node**); public: TREE() {Tree=NULL;} node** GetTree () {return &Tree;} //Получение вершины дерева. void BuildTree (); void CleanTree (node **); void ObhodEnd (node **); void ObhodLeft (node **); void ObhodBack (node **); void Vyvod (node**,int); int Height (node**);}; void main (){ TREE A; A.BuildTree (); cout<<"\nВывод дерева:\n"; A.Vyvod (A.GetTree(),0); cout<<"\nВысота дерева:"<<A.Height(A.GetTree())<<endl; cout<<"\nЛевосторонний обход дерева: "; A.ObhodLeft (A.GetTree()); cout<<"\nКонцевой обход дерева: "; A.ObhodEnd (A.GetTree()); cout<<"\nОбратный обход дерева: "; A.ObhodBack (A.GetTree()); A.CleanTree (A.GetTree());} void TREE::BuildTree ()// Построение бинарного дерева (рекурсивный алгоритм).// Tree - указатель на корень дерева.{ int el; cout<<"Вводите ключи вершин дерева ...\n"; cin>>el; while (el!=0) { Search (el,&Tree); cin>>el; }} void TREE::Search (int x,node **p)// Поиск вершины с ключом x в дереве со вставкой// (рекурсивный алгоритм).// *p - указатель на корень дерева.{ if (*p==NULL) {// Вершины в дереве нет; включить ее. *p = new(node); (**p).Key = x; (**p).Count = 1; (**p).Left = NULL; (**p).Right = NULL; } else if (x<(**p).Key) Search (x,&((**p).Left)); else if (x>(**p).Key) Search (x,&((**p).Right)); else (**p).Count = (**p).Count + 1;} void TREE::ObhodLeft (node **w)//Левосторонний обход дерева.//*w - указатель на корень дерева.{ if (*w!=NULL) { cout<<(**w).Key<<" "; ObhodLeft (&((**w).Left)); ObhodLeft (&((**w).Right)); }} void TREE::ObhodEnd (node **w)//Концевой обход дерева.//*w - указатель на корень дерева.{ if (*w!=NULL) { ObhodEnd (&((**w).Left)); ObhodEnd (&((**w).Right)); cout<<(**w).Key<<" "; }} void TREE::ObhodBack (node **w)//Обратный обход дерева.//*w - указатель на корень дерева.{ if (*w!=NULL) { ObhodBack (&((**w).Left)); cout<<(**w).Key<<" "; ObhodBack (&((**w).Right)); }} void TREE::CleanTree (node **w)//Очистка дерева.//*w - указатель на корень дерева.{ if (*w!=NULL) { CleanTree (&((**w).Left)); CleanTree (&((**w).Right)); delete *w; }} 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); }} int TREE::Height (node **w)//Определение высоты бинарного дерева.//*w - указатель на корень дерева.{ int h1,h2; if (*w==NULL) return (-1); else { h1 = Height (&((**w).Left)); h2 = Height (&((**w).Right)); if (h1>h2) return (1 + h1); else return (1 + h2); }}

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

#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);}

ЗАДАНИЕ:

1) Осуществить изучение материала путем реализации приведенных примеров кода.

2) Написать алгоритм и код рекурсивной функции правостороннего обхода бинарного дерева.

3) Ответить на следующие вопросы:

a) Каков будет порядок посещения вершин при правостороннем обходе следующих деревьев

ЗАДАЧА:

Создать класс бинарного дерева, включающий такие методы как:

1) Левосторонний обход;

2) Правосторонний обход;

3) Концевой обход;

4) Обратный обход;

5) Вывод бинарного дерева;

6) поиск заданной вершины в дереве;

7) добавление вершины в дерево;

8)удаление вершины из дерева.

ВАЖНО! Результат работы должен быть представлен 3-мя отдельными файлами: Заголовочный файл (BTree.h), файлом реализации методов класса (BTree.cpp), файлом исходного кода демонстрирующего возможности данного класса (Работу всех его методов).

Источники:

1) [ЭЛЕКТРОННЫЙ РЕСУРС]: Кафедра ПОАС КГУ; режим доступа: http://it.kgsu.ru/).

2) Вирт H. Алгоритмы + структуры данных = программы. - М.: Мир, 1985. - 406 с

⇐ Предыдущая 12