#include <iostream>
#include <math.h>
#include <vector>
using namespace std;
int mi=0; //najmniejszy element jaki jest na drzewie
int ma=0; //najwiÍkszy element jaki jest na drzewie
int a=0; //licznik do szukania podanej liczby
int poz=0; //najwyzszy poziom
vector<int> tablica; //tworzenie tablicy wektorůw
//----------------------ZADANIE 1-----------------------------------
class Tree
{
public:
int liczba;
string pozycja; //zapaniÍtuje stringa do wierzcho≥ka
int poziom; //poziom drzewa
int index; //index n-elementu drzewa
Tree *left;
Tree *right;
Tree(int parametrDomyslny) //konstruktor- szuka najwszyŅszego poziomu
{
this->poziom = parametrDomyslny;
this->index = 1;
if(parametrDomyslny>poz) poz=parametrDomyslny;
}
//------a)-------
void tworz(int pol) // int pol parametr funkcji,jest to wartosc ktora jest na szczycie drzewa,ustawia mi strzalki (lewy i prawy) na null
{
this->liczba = pol; // ustawia wartosc na szczycie drzewa
this->left = NULL; // null puste
this->right = NULL;
}
//------b)--------- wstawia
void tworzWierzcholek()
{
if(left == NULL)
{
int x;
cout << "Podaj wartosc dla lewego potomka: ";
cin >> x;
left=new Tree(poziom+1); // tworzy mi drugi poziom wierzcholka
left->tworz(x); // odwo≥anie do funkcji tworz
left->pozycja=pozycja+left->pozycja+"1"; // odwo≥anie do pozycja, pozycja + left i pozycja + 1 to przesuwa w lewo
left->index=2*index; //do zad.4 zwiÍksza index elementu razy 2
tablica[left->index]=x; // do zad.4 taki sam index jak wyŅej, bÍdzie mia≥ element w tablicy
}
else if(right == NULL)
{
int x;
cout << "Podaj wartosc dla prawego potomka: ";
cin >> x;
right=new Tree(poziom+1);
right->tworz(x);
right->pozycja=pozycja+right->pozycja+"2";
right->index=2*index+1; //do zad.4 zwiÍksza index elementu razy 2
tablica[right->index]=x; // do zad.4 taki sam index jak wyŅej, bÍdzie mia≥ element w tablicy
}
else cout << "Ten wierzcholek posiada juz 2 potomki !!\n";
}
//-------c)-------- szuka
int znajdz(Tree *k, int p) //szuka danej wartosci metoda inorder, int p liczba ktorej bedziemy szukac
{
if(!pustedrzewo(k)) // jeŅeli coú bÍdzie na drzewie to wykona
{
znajdz(k->left,p); // rekurencyjne wywo≥anie funkcji znajdz idac na lewo po drzewie
if(k->liczba==p) ++a; // jeŅeli ta liczba k jest růwna p(tej szukanej) to zwiÍkszamy a(zmienna do zwracania czy jest na drzewie czy nie)
znajdz(k->right,p); //
}
return a;
}
//-------d)--------------- usuwa
void usun(Tree *&p) // & przesy≥a, wskazuje na wskaünik p
{
p=NULL;
}
//---------------e)---------
void wyswietl(Tree *k) //wyswietla drzewo metodĻ inorder
{
if(!pustedrzewo(k))
{
wyswietl(k->left);
cout << "\nWartosc o numerze ["<< k->pozycja<< "] wynosi: " << k->liczba <<"\n";
wyswietl(k->right);
}
}
//------------------------------ZADANIE 2-----------------------
void preorder(Tree *&t)
{
if(!pustedrzewo(t))
{
cout << "\nWartosc " << t->liczba;
preorder(t -> left);
preorder(t -> right);
}
}
void postorder(Tree *&t)
{
if(!pustedrzewo(t))
{
postorder(t->left);
postorder(t -> right);
cout << "\nWartosc " << t -> liczba;
}
}
void inorder(Tree *k)
{
if(!pustedrzewo(k))
{
inorder(k->left);
cout << "Wartosc " << k->liczba <<"\n";
inorder(k->right);
}
}
//------------------------------min i max - 2d------------------------------
void minandmax(Tree *k) //szuka najmniejszej i najwiekszej wartosci w
// drzewie metoda inorder, Tree *k wskaznik na element
{
if(!pustedrzewo(k)) // jesli drzewo nie jest puste to przechodze po drzewie
{
minandmax(k->left); // wywo≥uje funkcje rekurencyjnie i przechodzi na lewo
if(k->liczba > ma) ma=k->liczba; // ma => maksymalna bedzie jako k wskaznik (->) liczba
if(k->liczba < mi) mi=k->liczba;
minandmax(k->right);
}
}
//--------------MAIN-----------------------------
main()
{
int c;
Tree *p=new Tree(1); // wskaznik p klasy Tree do main
tablica.reserve((int)(pow(2,10)-1)); //rezerwuje miejsce na tablice 10-poziomowa
for(int i=1; i<=(int)(pow(2,10)-1); i++) tablica[i]= NULL; //wyzerowana zostaje cala tablica
int f; //zad. 1a utworzenie nowego drzewa
cout << "Podaj wartosc dla korzenia: ";
cin >> f;
p->tworz(f);
tablica[1]=f;
p->tworzWierzcholek(); //zad. 1b wstawienie nowego wierzcholka
p->tworzWierzcholek();
p->left->tworzWierzcholek();
p->right->tworzWierzcholek();
cout << " \n\nZad.1c Szukam wierzcholka o podanym kluczu, w tym przypadku jest to 10"; // zad.1c
if(p->znajdz(p,10)>0) cout << "\n\n JEST wierzcholek o podanym kluczu !!!"; // 10 liczba ktorej szukamy po drzewie
if(p->znajdz(p,10)==0) cout << "\n\n NIEMA wierzcholka o poadnym kluczu !!!";
p->wyswietl(p); // zad.1e wyswietlanie drzewa
cout << "\n\nZad.3 \n";
mi=p->liczba; //zad. 3
ma=p->liczba;
p->minandmax(p);
cout << "Najwiekszy element wynosi: " << ma;
cout << "\n";
cout << "Najmniejszy element wynosi: " << mi;
cout <<"\n Zad.4";
p->wyswTablice(); // zad. 4
p->inorder(p);
cout << "\n\n";
p->postorder(p);
cout << "\n\n";
p->preorder(p);
cin >> c;
}