Деревья

  • Автор темы ermackprogramis
  • Дата начала
Статус
Закрыто для дальнейших ответов.
E

ermackprogramis

#1
Добрый всем день, у меня возникла проблема с работой с деревьями. Нужно сделать так что бы пользователь мог вводить уровень дерева, а програма выдавала сколько на этом уровне элементов и выводила их на экран. Не знаю как это сделать.Пробовал много вариантов но никак не выходит.Помогите пожалуйста. Подскажите как это сделать. Вот код остальной програмы:
C++:
#include <iostream>
#include <conio.h>
#include <stdlib.h>
#include <vector>
#include <iomanip>
#include <math.h>

using namespace std;

struct node
{
int Key;
node *Left;
node *Right;
};
node *Tree; // указатель на корень дерева
int n;
int count=0;

//==вершина дерева==
node** GetTree() 
{
return &Tree;
} 

// прототипи функций
void Search(int,node**);
void BuildTree();
void clean();
void CleanTree(node **);
void level(node **,int);

void Bypass1();
void Bypass_End(node **);
void Bypass2();
void Bypass_Left(node **);
void Bypass3();
void Bypass_Back(node **);

void out_tree();
void output(node**,int);

void h();
int Height(node**);
void choose();

void add();
void Search2(int,node**);

//==главная функция==
int main()
{
while(true)
{
system("cls");

// меню
cout<<"		 Menu"<<endl;
cout<<"1. Create binary tree"<<endl;
cout<<"2. Output binary tree"<<endl;
cout<<"3. Elements on n level"<<endl;
cout<<"4. Height of tree"<<endl;
cout<<"5. Bypass binary tree"<<endl;
cout<<"6. Add elements to tree"<<endl;
cout<<"7. Delete"<<endl;
cout<<"8. Exit"<<endl;

switch((int)getch())
{
case 49: {BuildTree ();break;} // ввод дерева
case 50: {out_tree();break;} // вывод дерева
case 51: {system("cls");cout<<"Enter level of tree"<<endl;cin>>n;level(GetTree(),n);getch();break;} 
case 52: {h();break;} // высота дерева
case 53: {choose();break;} // выбор обхода дерева
case 54: {add();break;} // дополнения дерева
case 55: {clean();break;} // очистка дерева
case 56: {;break;}
case 57: {exit(0);break;} // выход
} 
}
}

//==создание дерева==
void BuildTree ()
{
system("cls");
int element; // ключ дерева

cout<<"Enter elements(to finish press 0)"<<endl;
cin>>element; // ввод элемента

while (element!=0)
{
Search (element,&Tree); cin>>element;
}
}

//==поиск вставки элемента==
void Search (int x,node **p)
// *p - указатель на корень дерева.
{
if (*p==NULL) 
{
*p = new(node);
(**p).Key = x;
(**p).Left = NULL;
(**p).Right = NULL;
}
else
if(x<(**p).Key) 
{
Search (x,&((**p).Left)); // занести в левое поддерево
}
else
if(x>(**p).Key) 
{
Search (x,&((**p).Right)); // занести в правое поддерево
}
}

void out_tree()
{
system("cls");
output(GetTree(),0);
getch();
}

//==вывод дерева==
void output (node **w,int l)
{
if(*w!=NULL)
{
output (&((**w).Right),l+1);
for(int i=1; i<=l; i++) cout<<"  ";
cout<<(**w).Key<<endl;
output (&((**w).Left),l+1); 
}
}

//==элементи на n-ном уровне== 
void level(node **w,int l)
{

}

//==выбор обхода дерева==
void choose()
{
system("cls");

// меню
cout<<"1. Bypass Root->A->B"<<endl;
cout<<"2. Bypass A->B->Root"<<endl;
cout<<"3. Bypass A->Root->B"<<endl;
cout<<"4. Exit"<<endl;

switch((int)getch())
{
case 49: {Bypass1();break;}
case 50: {Bypass2();break;}
case 51: {Bypass3();break;}
case 52: {exit(0);break;}
}
}

//==обход дерева №1==
void Bypass1()
{
system("cls");
cout<<"Bypass Root->A->B"<<endl;
Bypass_Left(GetTree());
getch();
}

//==обход дерева с лева на право==
void Bypass_Left(node **w)
{
if(*w!=NULL)
{
cout<<(**w).Key<<" ";
Bypass_Left (&((**w).Left));
Bypass_Left (&((**w).Right));
}
}

//==обход дерева №2==
void Bypass2()
{
system("cls");
cout<<"Bypass A->B->Root"<<endl;
Bypass_End(GetTree());
getch();
}

//==обхід дерева з права на лево==
void Bypass_End (node **w)
{
if(*w!=NULL)
{
Bypass_End (&((**w).Left));
Bypass_End (&((**w).Right));
cout<<(**w).Key<<" "; 
}
}

//==обход дерева №3==
void Bypass3()
{
system("cls");
cout<<"Bypass A->Root->B"<<endl;
Bypass_Back(GetTree());
getch();
}

//==обход дерева сверху в низ==
void Bypass_Back (node **w)
{
if(*w!=NULL)
{
Bypass_Back (&((**w).Left));
cout<<(**w).Key<<" ";
Bypass_Back (&((**w).Right)); 
}
}

//==дополнение дерева дерева==
void add()
{
system("cls");
int element; 

cout<<"Enter elements(to finish press 0)"<<endl;
cin>>element;

while (element!=0)
{
Search2(element,&Tree); cin>>element; 
}
}

//==поиск вставки элемента==
void Search2(int x,node **p)
// *p - покажчик на корінь дерева.
{
if(x<(**p).Key) 
{
Search (x,&((**p).Left)); /
}
else
if(x>(**p).Key) 
{
Search (x,&((**p).Right)); 
}
}

void clean()
{
system("cls");
CleanTree(GetTree());
cout<<"Done"<<endl;
getch();
}

//==очистка дерева==
void CleanTree (node **w)
{
if(*w!=NULL)
{ 
CleanTree (&((**w).Left));
CleanTree (&((**w).Right));
delete *w; 
}
}

void h()
{
system("cls");
Height(GetTree());
cout<<"Height of tree: "<<Height(GetTree())<<endl;
getch();
}

//==высота дерева==
int Height (node **w)
{
//if(*w==NULL)
//{ cout<<"Tree is empty!!!"<<endl;break; }
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);
}
}
 
Статус
Закрыто для дальнейших ответов.