Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
Топ:
Основы обеспечения единства измерений: Обеспечение единства измерений - деятельность метрологических служб, направленная на достижение...
Оценка эффективности инструментов коммуникационной политики: Внешние коммуникации - обмен информацией между организацией и её внешней средой...
Интересное:
Берегоукрепление оползневых склонов: На прибрежных склонах основной причиной развития оползневых процессов является подмыв водами рек естественных склонов...
Мероприятия для защиты от морозного пучения грунтов: Инженерная защита от морозного (криогенного) пучения грунтов необходима для легких малоэтажных зданий и других сооружений...
Как мы говорим и как мы слушаем: общение можно сравнить с огромным зонтиком, под которым скрыто все...
Дисциплины:
 2018-01-04 |
 148 |
из
5.00
|
Заказать работу |
|
|
|
|
ОПИСАНИЕ АЛГОРИТМА
Идеально сбалансированным назовем такое бинарное дерево T, что для каждого его узлаx справедливо соотношение
| nL (x) - nR (x)| £ 1,
где nL (x) - количество узлов в левом поддереве узла x, а nR (x) - количество узлов в правом поддеревеузла x.
В идеально сбалансированном дереве число узлов n
и высота дерева h связаны соотношением
или h= 
Высота дерева определена так, что при n = 0 имеем h = 0, а при n = 1 имеем h = 1
Пусть, например, данные берутся из потока infile.
a,b,c,d,e,f,g,h,I.
Идея (рекурсивного) алгоритма
Здесь nэто количество элементов в файле.
nL это количество элементов на левой части после того как мы разделили количесво элементов пополам.
nR это количество элементов на правой части после того как мы разделили количесво элементов пополам.
Дальше мы разделим количесво элементов на левой и правой частей пополам,и продолжаем этот процесс до тех пор 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)
(здесь nL = n /2 и nR = n – nL – 1, т. е. n = nL + nR +1)
Всеэлементывфайлерасположеныпо возразтанию.
в непустом БДП 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. Если вставляемый элемент меньше корня БДП, то его место в левом поддереве. Поэтому сначала рекурсивно вставим этот элемент в качестве корня левого поддерева, а затем с помощью правого вращения поднимем его в корень дерева.
Пример:
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 справедливо соотношение
| nL (x) - nR (x)| £ 1,
где nL (x) - количество узлов в левом поддереве узла x, а nR (x) - количество узлов в правом поддеревеузла x.
В идеально сбалансированном дереве число узлов n
и высота дерева h связаны соотношением
или h=
Высота дерева определена так, что при n = 0 имеем h = 0, а при n = 1 имеем h = 1
Пусть, например, данные берутся из потока infile.
a,b,c,d,e,f,g,h,I.
Идея (рекурсивного) алгоритма
Здесь nэто количество элементов в файле.
nL это количество элементов на левой части после того как мы разделили количесво элементов пополам.
nR это количество элементов на правой части после того как мы разделили количесво элементов пополам.
Дальше мы разделим количесво элементов на левой и правой частей пополам,и продолжаем этот процесс до тех пор 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)
(здесь nL = n /2 и nR = n – nL – 1, т. е. n = nL + nR +1)
Всеэлементывфайлерасположеныпо возразтанию.
в непустом БДП 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. Если вставляемый элемент меньше корня БДП, то его место в левом поддереве. Поэтому сначала рекурсивно вставим этот элемент в качестве корня левого поддерева, а затем с помощью правого вращения поднимем его в корень дерева.
Пример:
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
БЛОКСХЕМА:
Схема алгоритма для сьаласировка бинарного дерева.
|
|
|
Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...
Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
Автоматическое растормаживание колес: Тормозные устройства колес предназначены для уменьшения длины пробега и улучшения маневрирования ВС при...
Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!