Схема алгоритма для сьаласировка бинарного дерева.

ОПИСАНИЕ АЛГОРИТМА

• сбалансированное бинарное дерево поиска.

Идеально сбалансированным назовем такое бинарное дерево T , что для каждого его узлаxсправедливо соотношение

|n_L(x) - n_R(x)| £ 1,

где n_L(x) - количество узлов в левом поддереве узлаx, а n_R(x) - количество узлов в правом поддеревеузлаx.

В идеально сбалансированном дереве число узлов n

и высота дерева h связаны соотношением

или h=

Высота дерева определена так, что при n = 0 имеем h = 0, а при n = 1 имеем h = 1

Пусть, например, данные берутся из потока infile.

a,b,c,d,e,f,g,h,I.

Идея (рекурсивного) алгоритма

Здесь nэто количество элементов в файле.

n_L это количество элементов на левой части после того как мы разделили количесво элементов пополам.

n_R это количество элементов на правой части после того как мы разделили количесво элементов пополам.

Дальше мы разделим количесво элементов на левой и правой частей пополам,и продолжаем этот процесс до тех пор n !=0.тот элемента в середине становится главным элементом поддерева или дерева,как показано вниз.

a,b,c,d,e,f,g,h,i. (n=9)

a,b,c,d,(n=4)f,g,h,i.(n=4)

a,b(n=2)d (n=1)f,g,(n=2)i(n=1)

a(n=1)f (n=1)

(здесьn_L = n/2 иn_R = n– n_L – 1, т. е. n = n_L + n_R +1)

Всеэлементывфайлерасположеныпо возразтанию.

• Операция поиска заданного элемента x: base

в непустом БДП b: BSTree производится рекурсивно :

Если k(x) = k(b), то элемент x находится в корне дерева b. Поиск закончен «успешно» – элемент найден.

Если k(x) < k(b), то продолжить поиск в левом поддереве Left (b).

Если k(x) > k(b), то продолжить поиск в правом поддереве Right (b).

Если выбранное поддерево оказывается пустым, то поиск завершается «неудачно» – элемента x в дереве b нет.

Пример:

У нас такое сбалансированное бинарное дерево поиска.

E

CH

BDGI

AF

Сейчас мы пытаемся найти элемент Gв сбалансированномбинарном дереве поиска.

мы проверяем, если G равен первому элементу. Первый элемент это E они не равны. Дальше рассмотриваем если Gбольше или меньше.здесь видно что Gбольше поэтому мы продолжаем поиск в правом поддереве. Потом встречаем новый элемент H. Gменьше этого элемент из-за этого продолжаем поиск в левом поддереве.проверяем если они равны,получается что они равны тогда рекурсия заканчивается и возврашаем TRUE.

• Случайные бинарные деревья поиск .

Случайные бинарные деревья поиск построится из входной последовательности (например из файла (d,b,h,a,c,f,k))

Первый элемент всегда становится перым узлом дерева. Остальные построенны по принципу указано вниз:

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

Например :(d,b,h,a,c)

d–это первы элемент.

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

d

b

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

d

bh

дальше,чертвёртий элемент это a.сейчас сравниваем чертвёртий элемент с первом,так как чертвёртий меньше первого мы продолжаем сравнение на левой части первого,дальше мы встречаем ещё элемент (b) на левой части первого элемента и сравниваем,так как чертвёртий элемент (а) меньше (b)мы продолжаем сравнение на левой части этого элемента .так что у нас больше нет элементов на левой части этого элемента мы построим узел четвёртого элемента на левой части этого элемента.его представление

d

bh

а

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

d

bh

а с

• Случайные бинарные деревья поиск .

Ø Вставка в корень БДП

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

1. Построенные таким образом БДП имеют некоторые полезные свойства.
2. Операция вставки в корень будет использоваться в модификации случайных БДП, рассмотренной далее.

Рекурсивный способ

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

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

Пример:

d

b h

a c f k

при добавлении элмента e,

e

d

b h

a c f k

после добавления элемента в правильном месте:

d

b h

a c f k

e

с помощью правого и левого вращения подмем элмемент е в корень дерева:

d

b h

a c f k

e

после правого врашения

d

b h

a c е k

f

после правого врашения

d

b e

a c h

f k

после левого врашения

е

d h

b f k

a ` c

КОД:

Btree.h

// интерфейсАТД "Бинарноедерево"(впроцедурно-модульнойпарадигме)

namespacebinTree_modul

{

//-------------------------------------

typedefchar base;

struct node {

base info;

node *lt;

node *rt;

int count;

// constructor

node () {

lt = NULL; rt = NULL;

count=0;

}

};

typedefnode *binTree; // "представитель" бинарного дерева

binTree Create(void);

boolisNull(binTree);

baseRootBT (binTree); // длянепустогобин.дерева

binTree Left (binTree);// длянепустогобин.дерева

binTree Right (binTree);// длянепустогобин.дерева

binTreeConsBT(const base &x, binTree&lst, binTree&rst);

void destroy (binTree&);

}

bt_implementation.cpp

// Implementation - Реализация АТД "Бинарное дерево" (в процедурно-модульной парадигме)

#include<iostream>

#include<cstdlib>

#include"Btree.h"

usingnamespacestd ;

namespacebinTree_modul

{

//-------------------------------------

binTree Create()

{ return NULL;

}

//-------------------------------------

boolisNull(binTree b)

{ return (b == NULL);

}

//-------------------------------------

baseRootBT (binTree b) // длянепустогобин.дерева

{ if (b == NULL) { cerr<<"Error: RootBT(null) \n"; exit(1); }

elsereturn b->info;

}

//-------------------------------------

binTree Left (binTree b) // длянепустогобин.дерева

{ if (b == NULL) { cerr<<"Error: Left(null) \n"; exit(1); }

elsereturn b ->lt;

}

//-------------------------------------

binTree Right (binTree b) // длянепустогобин.дерева

{ if (b == NULL) { cerr<<"Error: Right(null) \n"; exit(1); }

elsereturn b->rt;

}

//-------------------------------------

binTreeConsBT(const base &x, binTree&lst, binTree&rst)

{ binTree p;

p = new node;

if ( p != NULL) {

p ->info = x;

p ->lt = lst;

p ->rt = rst;

return p;

}

else {cerr<<"Memory not enough\n"; exit(1);}

}

//-------------------------------------

void destroy (binTree&b)

{ if (b != NULL) {

destroy (b->lt);

destroy (b->rt);

delete b;

b = NULL;

}

}

} // end of namespace h_list

idealBlnsTr.cpp

#include<iostream>

#include<fstream>

#include"time.h"

#include<cstdlib>

#include"Btree.h"

#include<windows.h>

usingnamespacestd ;

usingnamespacebinTree_modul;

typedefunsignedintunInt;

voidrotateL (binTree&t);

voidrotateR (binTree&t);

voidinsInRoot (binTree&b, base x);

bool Locate (base x, binTree b);

voidSearchAndInsert (base x, binTree&b);

voiddisplayBt (binTree b, int n);

unInthBT (binTree b);

unIntsizeBT (binTree b);

voiddisplayBt(binTreeq,intlevel,boolleft,bool *mas);

binTreemakeTree (unInt n);

ifstream infile2 ("inputf.txt");

ifstream infile3 ("inputf1.txt");

int main ()

{

restart:

system("cls");

binTree b;

SetConsoleCP(1251); // для вывода кирилицы

SetConsoleOutputCP(1251); // для вывода кирилицы

if (!infile2) cout<<"Входной файл #2 не открыт!"<<endl;

cout<<"Building a perfectly balanced binary tree "<<endl;

cout<<".................MENU..................\n";

cout<<"1)balanced Binary tree search\n2) Element search\n3)cluchainie binary tree search\n4)exit\n5)adding an element in the cluchainie binary tree search c pomoshiufctafki b koren \n";

char s;

cout<<"Enter your choice: \n";

cin>>s;

if(s=='5'|| s=='4'||s=='3'||s=='2'||s=='1'){

;

}else{

cout<<"Enter the right choice!!\n";

goto restart;

}

unInt n=9;

bool mas[1000];

memset(mas,0,1000);

bool p=true;

switch(s){

case'1':

clock_t start;

double duration;

start=clock();

b = makeTree (n);

displayBt(b,0,false,mas);

duration=(clock()-start)/(double)CLOCKS_PER_SEC;

cout<<"Time taken to create and print out the balanced tree: "<<duration<<endl;

cout<<"tree height = "<<hBT(b) <<endl;

cout<<"Size (number of nodes) of the tree = "<<sizeBT(b) <<endl;

//destroy (b);

break;

case'2':

b=makeTree(n);

displayBt(b,0,false,mas);

base x;

cout<<"Enter the elment you are searchin for: \n";

cin>>x;

base r;

double duration1;

clock_t start1;

start1=clock();

p=Locate(x,b);

duration1=(clock()-start1)/(double)CLOCKS_PER_SEC;

cout<<"Time taken to find the elmenet in the balanced tree: "<<duration1<<endl;

if (p){

cout<<"The Element was found!!\n";

}

else{cout<<"Elemnet not found!!\n";

}

;

//destroy (b);

break;

case'4':

exit(0);

break;

case'3':

b=NULL;

base y;

clock_t start2;

double duration2;

start2=clock();

while(infile3>>y){

SearchAndInsert (y,b);

}

displayBt(b,0,false,mas);

duration2=(clock()-start2)/(double)CLOCKS_PER_SEC;

cout<<"Time taken to create cluchainie binary tree and print: "<<duration2<<endl;

break;

case'5':

b=NULL;

clock_t start3;

double duration3;

start3=clock();

while(infile3>>y){

SearchAndInsert (y,b);

}

displayBt(b,0,false,mas);

base g;

cout<<"Enter the element you want to add to the tree: \n";

cin>>g;

insInRoot (b,g);

displayBt(b,0,false,mas);

duration3=(clock()-start3)/(double)CLOCKS_PER_SEC;

cout<<"Time taken to Add element to cluchainie binary tree c pomoshiufctafki b koren and print: "<<duration3<<endl;

break;

default:

break;

}

destroy(b);

system("pause");

}

//---------------------------------------

unInthBT (binTree b)

{

if (isNull(b)) return 0;

elsereturn max (hBT (Left(b)), hBT(Right(b))) + 1;

}

//---------------------------------------

unIntsizeBT (binTree b)

{

if (isNull(b)) return 0;

elsereturnsizeBT (Left(b))+ sizeBT(Right(b)) + 1;

}

//---------------------------------------

binTreemakeTree (unIntn)

// построение идеально сбалансированного дерева

{

unIntnL, nR;

binTree b1, b2;

base x;

if (n==0){

return Create();

}

nL = n/2;

nR = n-nL-1;

b1 = makeTree (nL);

infile2 >> x;

b2 = makeTree (nR);

returnConsBT(x, b1, b2);

}

bool Locate (base x, binTree b)

// b – должно быть БДП

{ baser;

if (isNull(b)) returnfalse;

else {

r = RootBT(b);

if (x==r) returntrue;

elseif (x<r) return Locate(x,Left(b));

elsereturn Locate(x,Right(b));

}

}

voiddisplayBt(binTreeq,intlevel,boolleft,bool *mas)

{

if(q!=0)

{

for(inti=1;i<level*4;i++)

{

if(mas[i]){

cout<< (char)179;

}

else{

cout<<" ";

}

}

if(q->lt!=0||q->rt!=0)

if(level!=0)

{

if(left)

{

cout<<(char)192<<"["<<q->info<<"]"<<(char)191;

mas[level*4]=false;

}

else

{

cout<<(char)195<<"["<<q->info<<"]"<<(char)191;

mas[level*4]=true;

}

}

else

{

cout<<"["<<q->info<<"]"<<(char)191;

}

else

{

if(left)

cout<<(char)192<<"["<< q->info<<"]";

else

cout<<(char)195<<"["<< q->info<<"]";

}

cout<<endl;

displayBt(q->rt,level+1,false,mas);

displayBt(q->lt,level+1,true,mas);

}

}

voidSearchAndInsert (base x, binTree&b)

{ if (b==NULL) {

b = new node;

b ->info = x;

b ->count = 1;

}

elseif(x < b->info) SearchAndInsert (x, b->lt);

elseif(x > b->info) SearchAndInsert (x, b->rt);

else b->count++;

}

voidrotateR (binTree&t)

//b - непусто

{ binTree x;

if (t==NULL){cout<< "rotateR(NULL)"<<endl; }

else {

x = t->lt;

t->lt = x->rt;

x->rt = t;

t =x;

}

}

voidrotateL (binTree&t)

//b - непусто

{ binTreex;

if (t==NULL){

cout<< "rotateL(NULL)"<<endl; }

else {

x = t->rt;

t->rt = x->lt;

x->lt = t;

t =x;

}

}

voidinsInRoot (binTree&b, base x)

{ if (b==NULL) {

b = new node;

if ( b != NULL) {

b ->info = x;

b ->count = 1;

}

else {cerr<<"1 Memory not enough\n"; exit(1);}

} else

if (x < b->info) {insInRoot (b->lt, x); rotateR (b);}

elseif (x > b->info) {insInRoot (b->rt, x); rotateL (b);}

else b->count++;

}

Infile2:Acdefg

БЛОКСХЕМА :

Пример работы программы

ü Исходные данны из файла : a,b,c,d,e,f,g,h,i .

ü Исходные данны из файла : b,d,f,i ,j,m,r,t,w

ü Исходные данны из файла : dbhacfk

ü Исходные данны из файла : ropqcvn

ü Исходные данны из файла : jalzxbs

ü Исходные данны из файла : jalzxbs

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

Поиск элемента всбалансированномбинарном дереве поиска.

Мы ищем элемент “r”

ОПИСАНИЕ АЛГОРИТМА

• сбалансированное бинарное дерево поиска.

Идеально сбалансированным назовем такое бинарное дерево T , что для каждого его узлаxсправедливо соотношение

|n_L(x) - n_R(x)| £ 1,

где n_L(x) - количество узлов в левом поддереве узлаx, а n_R(x) - количество узлов в правом поддеревеузлаx.

В идеально сбалансированном дереве число узлов n

и высота дерева h связаны соотношением

или h=

Высота дерева определена так, что при n = 0 имеем h = 0, а при n = 1 имеем h = 1

Пусть, например, данные берутся из потока infile.

a,b,c,d,e,f,g,h,I.

Идея (рекурсивного) алгоритма

Здесь nэто количество элементов в файле.

n_L это количество элементов на левой части после того как мы разделили количесво элементов пополам.

n_R это количество элементов на правой части после того как мы разделили количесво элементов пополам.

Дальше мы разделим количесво элементов на левой и правой частей пополам,и продолжаем этот процесс до тех пор n !=0.тот элемента в середине становится главным элементом поддерева или дерева,как показано вниз.

a,b,c,d,e,f,g,h,i. (n=9)

a,b,c,d,(n=4)f,g,h,i.(n=4)

a,b(n=2)d (n=1)f,g,(n=2)i(n=1)

a(n=1)f (n=1)

(здесьn_L = n/2 иn_R = n– n_L – 1, т. е. n = n_L + n_R +1)

Всеэлементывфайлерасположеныпо возразтанию.

• Операция поиска заданного элемента x: base

в непустом БДП b: BSTree производится рекурсивно :

Если k(x) = k(b), то элемент x находится в корне дерева b. Поиск закончен «успешно» – элемент найден.

Если k(x) < k(b), то продолжить поиск в левом поддереве Left (b).

Если k(x) > k(b), то продолжить поиск в правом поддереве Right (b).

Если выбранное поддерево оказывается пустым, то поиск завершается «неудачно» – элемента x в дереве b нет.

Пример:

У нас такое сбалансированное бинарное дерево поиска.

E

CH

BDGI

AF

Сейчас мы пытаемся найти элемент Gв сбалансированномбинарном дереве поиска.

мы проверяем, если G равен первому элементу. Первый элемент это E они не равны. Дальше рассмотриваем если Gбольше или меньше.здесь видно что Gбольше поэтому мы продолжаем поиск в правом поддереве. Потом встречаем новый элемент H. Gменьше этого элемент из-за этого продолжаем поиск в левом поддереве.проверяем если они равны,получается что они равны тогда рекурсия заканчивается и возврашаем TRUE.

• Случайные бинарные деревья поиск .

Случайные бинарные деревья поиск построится из входной последовательности (например из файла (d,b,h,a,c,f,k))

Первый элемент всегда становится перым узлом дерева. Остальные построенны по принципу указано вниз:

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

Например :(d,b,h,a,c)

d–это первы элемент.

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

d

b

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

d

bh

дальше,чертвёртий элемент это a.сейчас сравниваем чертвёртий элемент с первом,так как чертвёртий меньше первого мы продолжаем сравнение на левой части первого,дальше мы встречаем ещё элемент (b) на левой части первого элемента и сравниваем,так как чертвёртий элемент (а) меньше (b)мы продолжаем сравнение на левой части этого элемента .так что у нас больше нет элементов на левой части этого элемента мы построим узел четвёртого элемента на левой части этого элемента.его представление

d

bh

а

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

d

bh

а с

• Случайные бинарные деревья поиск .

Ø Вставка в корень БДП

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

1. Построенные таким образом БДП имеют некоторые полезные свойства.
2. Операция вставки в корень будет использоваться в модификации случайных БДП, рассмотренной далее.

Рекурсивный способ

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

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

Пример:

d

b h

a c f k

при добавлении элмента e,

e

d

b h

a c f k

после добавления элемента в правильном месте:

d

b h

a c f k

e

с помощью правого и левого вращения подмем элмемент е в корень дерева:

d

b h

a c f k

e

после правого врашения

d

b h

a c е k

f

после правого врашения

d

b e

a c h

f k

после левого врашения

е

d h

b f k

a ` c

КОД:

Btree.h

// интерфейсАТД "Бинарноедерево"(впроцедурно-модульнойпарадигме)

namespacebinTree_modul

{

//-------------------------------------

typedefchar base;

struct node {

base info;

node *lt;

node *rt;

int count;

// constructor

node () {

lt = NULL; rt = NULL;

count=0;

}

};

typedefnode *binTree; // "представитель" бинарного дерева

binTree Create(void);

boolisNull(binTree);

baseRootBT (binTree); // длянепустогобин.дерева

binTree Left (binTree);// длянепустогобин.дерева

binTree Right (binTree);// длянепустогобин.дерева

binTreeConsBT(const base &x, binTree&lst, binTree&rst);

void destroy (binTree&);

}

bt_implementation.cpp

// Implementation - Реализация АТД "Бинарное дерево" (в процедурно-модульной парадигме)

#include<iostream>

#include<cstdlib>

#include"Btree.h"

usingnamespacestd ;

namespacebinTree_modul

{

//-------------------------------------

binTree Create()

{ return NULL;

}

//-------------------------------------

boolisNull(binTree b)

{ return (b == NULL);

}

//-------------------------------------

baseRootBT (binTree b) // длянепустогобин.дерева

{ if (b == NULL) { cerr<<"Error: RootBT(null) \n"; exit(1); }

elsereturn b->info;

}

//-------------------------------------

binTree Left (binTree b) // длянепустогобин.дерева

{ if (b == NULL) { cerr<<"Error: Left(null) \n"; exit(1); }

elsereturn b ->lt;

}

//-------------------------------------

binTree Right (binTree b) // длянепустогобин.дерева

{ if (b == NULL) { cerr<<"Error: Right(null) \n"; exit(1); }

elsereturn b->rt;

}

//-------------------------------------

binTreeConsBT(const base &x, binTree&lst, binTree&rst)

{ binTree p;

p = new node;

if ( p != NULL) {

p ->info = x;

p ->lt = lst;

p ->rt = rst;

return p;

}

else {cerr<<"Memory not enough\n"; exit(1);}

}

//-------------------------------------

void destroy (binTree&b)

{ if (b != NULL) {

destroy (b->lt);

destroy (b->rt);

delete b;

b = NULL;

}

}

} // end of namespace h_list

idealBlnsTr.cpp

#include<iostream>

#include<fstream>

#include"time.h"

#include<cstdlib>

#include"Btree.h"

#include<windows.h>

usingnamespacestd ;

usingnamespacebinTree_modul;

typedefunsignedintunInt;

voidrotateL (binTree&t);

voidrotateR (binTree&t);

voidinsInRoot (binTree&b, base x);

bool Locate (base x, binTree b);

voidSearchAndInsert (base x, binTree&b);

voiddisplayBt (binTree b, int n);

unInthBT (binTree b);

unIntsizeBT (binTree b);

voiddisplayBt(binTreeq,intlevel,boolleft,bool *mas);

binTreemakeTree (unInt n);

ifstream infile2 ("inputf.txt");

ifstream infile3 ("inputf1.txt");

int main ()

{

restart:

system("cls");

binTree b;

SetConsoleCP(1251); // для вывода кирилицы

SetConsoleOutputCP(1251); // для вывода кирилицы

if (!infile2) cout<<"Входной файл #2 не открыт!"<<endl;

cout<<"Building a perfectly balanced binary tree "<<endl;

cout<<".................MENU..................\n";

cout<<"1)balanced Binary tree search\n2) Element search\n3)cluchainie binary tree search\n4)exit\n5)adding an element in the cluchainie binary tree search c pomoshiufctafki b koren \n";

char s;

cout<<"Enter your choice: \n";

cin>>s;

if(s=='5'|| s=='4'||s=='3'||s=='2'||s=='1'){

;

}else{

cout<<"Enter the right choice!!\n";

goto restart;

}

unInt n=9;

bool mas[1000];

memset(mas,0,1000);

bool p=true;

switch(s){

case'1':

clock_t start;

double duration;

start=clock();

b = makeTree (n);

displayBt(b,0,false,mas);

duration=(clock()-start)/(double)CLOCKS_PER_SEC;

cout<<"Time taken to create and print out the balanced tree: "<<duration<<endl;

cout<<"tree height = "<<hBT(b) <<endl;

cout<<"Size (number of nodes) of the tree = "<<sizeBT(b) <<endl;

//destroy (b);

break;

case'2':

b=makeTree(n);

displayBt(b,0,false,mas);

base x;

cout<<"Enter the elment you are searchin for: \n";

cin>>x;

base r;

double duration1;

clock_t start1;

start1=clock();

p=Locate(x,b);

duration1=(clock()-start1)/(double)CLOCKS_PER_SEC;

cout<<"Time taken to find the elmenet in the balanced tree: "<<duration1<<endl;

if (p){

cout<<"The Element was found!!\n";

}

else{cout<<"Elemnet not found!!\n";

}

;

//destroy (b);

break;

case'4':

exit(0);

break;

case'3':

b=NULL;

base y;

clock_t start2;

double duration2;

start2=clock();

while(infile3>>y){

SearchAndInsert (y,b);

}

displayBt(b,0,false,mas);

duration2=(clock()-start2)/(double)CLOCKS_PER_SEC;

cout<<"Time taken to create cluchainie binary tree and print: "<<duration2<<endl;

break;

case'5':

b=NULL;

clock_t start3;

double duration3;

start3=clock();

while(infile3>>y){

SearchAndInsert (y,b);

}

displayBt(b,0,false,mas);

base g;

cout<<"Enter the element you want to add to the tree: \n";

cin>>g;

insInRoot (b,g);

displayBt(b,0,false,mas);

duration3=(clock()-start3)/(double)CLOCKS_PER_SEC;

cout<<"Time taken to Add element to cluchainie binary tree c pomoshiufctafki b koren and print: "<<duration3<<endl;

break;

default:

break;

}

destroy(b);

system("pause");

}

//---------------------------------------

unInthBT (binTree b)

{

if (isNull(b)) return 0;

elsereturn max (hBT (Left(b)), hBT(Right(b))) + 1;

}

//---------------------------------------

unIntsizeBT (binTree b)

{

if (isNull(b)) return 0;

elsereturnsizeBT (Left(b))+ sizeBT(Right(b)) + 1;

}

//---------------------------------------

binTreemakeTree (unIntn)

// построение идеально сбалансированного дерева

{

unIntnL, nR;

binTree b1, b2;

base x;

if (n==0){

return Create();

}

nL = n/2;

nR = n-nL-1;

b1 = makeTree (nL);

infile2 >> x;

b2 = makeTree (nR);

returnConsBT(x, b1, b2);

}

bool Locate (base x, binTree b)

// b – должно быть БДП

{ baser;

if (isNull(b)) returnfalse;

else {

r = RootBT(b);

if (x==r) returntrue;

elseif (x<r) return Locate(x,Left(b));

elsereturn Locate(x,Right(b));

}

}

voiddisplayBt(binTreeq,intlevel,boolleft,bool *mas)

{

if(q!=0)

{

for(inti=1;i<level*4;i++)

{

if(mas[i]){

cout<< (char)179;

}

else{

cout<<" ";

}

}

if(q->lt!=0||q->rt!=0)

if(level!=0)

{

if(left)

{

cout<<(char)192<<"["<<q->info<<"]"<<(char)191;

mas[level*4]=false;

}

else

{

cout<<(char)195<<"["<<q->info<<"]"<<(char)191;

mas[level*4]=true;

}

}

else

{

cout<<"["<<q->info<<"]"<<(char)191;

}

else

{

if(left)

cout<<(char)192<<"["<< q->info<<"]";

else

cout<<(char)195<<"["<< q->info<<"]";

}

cout<<endl;

displayBt(q->rt,level+1,false,mas);

displayBt(q->lt,level+1,true,mas);

}

}

voidSearchAndInsert (base x, binTree&b)

{ if (b==NULL) {

b = new node;

b ->info = x;

b ->count = 1;

}

elseif(x < b->info) SearchAndInsert (x, b->lt);

elseif(x > b->info) SearchAndInsert (x, b->rt);

else b->count++;

}

voidrotateR (binTree&t)

//b - непусто

{ binTree x;

if (t==NULL){cout<< "rotateR(NULL)"<<endl; }

else {

x = t->lt;

t->lt = x->rt;

x->rt = t;

t =x;

}

}

voidrotateL (binTree&t)

//b - непусто

{ binTreex;

if (t==NULL){

cout<< "rotateL(NULL)"<<endl; }

else {

x = t->rt;

t->rt = x->lt;

x->lt = t;

t =x;

}

}

voidinsInRoot (binTree&b, base x)

{ if (b==NULL) {

b = new node;

if ( b != NULL) {

b ->info = x;

b ->count = 1;

}

else {cerr<<"1 Memory not enough\n"; exit(1);}

} else

if (x < b->info) {insInRoot (b->lt, x); rotateR (b);}

elseif (x > b->info) {insInRoot (b->rt, x); rotateL (b);}

else b->count++;

}

Infile2:Acdefg

БЛОКСХЕМА :

Схема алгоритма для сьаласировка бинарного дерева.