//Main()
 
 
#include<iostream>
using namespace std;
//#include "pokazivac_three.h"
#include "polje_three.h"
#include "opcenito.h"
 
void opcenitoStablo(){ 
     tree *tree;
     int vrijednost;
     cout<<"Pocetna vrijednost korijena je 1"<<endl;
     tree=InitT(1,tree);
     cout<<"Unesite vrijdnost cvora (cvor 2): ";cin>>vrijednost;         
     CreateT(vrijednost,2,tree);
     cout<<"Unesite jos jednu vrijednost cvora (cvor 3): ";cin>>vrijednost;
     CreateT(vrijednost,3,tree);
 
     cout<<"Vrijednost treceg cvora je: "<<LabelT(2,tree)<<endl<<endl;
 
     cout<<"Prvo dijete od cvora 2: "<<FirstChildT(2,tree)<<endl;
     cout<<"Roditelj od cvora 3: "<<ParentT(3,tree)<<endl;
 
     cout<<"Unesite novu vrijednost treceg cvora: ";cin>>vrijednost;
     ChangeLabelT(vrijednost,2,tree);
 
     cout<<"Nova vrijednost treceg cvora je: "<<LabelT(2,tree)<<endl<<endl;
 
     cout<<"Brisanje cvora 2..."<<endl;
     DeleteT(2,tree);
     cout<<"Cvor 2 izbrisan..."<<endl;
 
     cout<<"Dealokacija stabla..."<<endl<<endl;
 
     delete tree;
}//OpcenitoStablo
 
void binarnoStablo(){
    cout << "Inicijalizacija stabla" << endl;
    bt* stablo = InitB(1, stablo);
    cout << "Korijen: " << LabelB(RootB(stablo), stablo)<< endl << endl;
 
    cout << "Kreiranje lijevog dijeteta 15 " << endl;
    CreateLeftB(15, RootB(stablo), stablo);
    cout << "Kreiranje desnog dijeta 3 " << endl << endl;
    CreateRightB(3, RootB(stablo), stablo);
 
    cout << "Lijevo dijete korijena: " << LabelB(LeftChildB(RootB(stablo), stablo), stablo)<<endl;
    cout << "Desno dijete korijena: " << LabelB(RightChildB(RootB(stablo), stablo), stablo)<<endl<<endl;
 
    cout << "Kreiranje lijevog djeteta 4 lijevom djetetu korijena (cvor 15)" << endl;
    CreateLeftB(4, LeftChildB(RootB(stablo), stablo), stablo);
    cout << "Kreiranje desnog djeteta 5 lijevom djetetu korijana (cvor 15)" << endl;
    CreateRightB(5, LeftChildB(RootB(stablo), stablo), stablo);
 
    cout << "Kreiranje lijevog djeteta 6 desnom djetetu korijana (cvor 3)" << endl;
    CreateLeftB(6, RightChildB(RootB(stablo), stablo), stablo);
 
    cout << "Kreiranje desnog djeteta 7 desnom djetetu korijana (cvor 3)" << endl;
    CreateRightB(7, RightChildB(RootB(stablo), stablo), stablo);
    cout<<endl;
 
    cout << "Lijevo dijete desnog dijeteta korijena: ";
    cout << LabelB(LeftChildB(RightChildB(RootB(stablo), stablo), stablo), stablo) << endl << endl;
 
    cout << "Mijenjanje cvora 6 u 16: " << endl << endl;
    ChangeLabelB(16, LeftChildB(RightChildB(RootB(stablo), stablo), stablo), stablo);
    cout << "Lijevo dijete desnog dijeteta korijena: ";
    cout << LabelB(LeftChildB(RightChildB(RootB(stablo), stablo), stablo), stablo) << endl << endl;
 
    cvor pom = RightChildB(RightChildB(RootB(stablo), stablo), stablo);
    cout << "Roditelj cvora 7 je: " << LabelB(ParentB(pom, stablo), stablo) << endl << endl;     
 
    cout << "Brisanje cvora 3 i svih njegovih potomaka..." << endl;
    DeleteB(RightChildB(RootB(stablo), stablo), stablo);
    cout<<endl;
 
    }//binarnoStablo
 
 
int main() {
    int izbor;
    do{
    cout<<"0. Izlaz iz programa"<<endl;
    cout<<"1. Binarno stablo"<<endl;
    cout<<"2. Opcenito stablo"<<endl;
 
    cout<<"Vas izbor je: ";
 
    cin >> izbor;
    cout<<endl;
    if(izbor == 1) binarnoStablo();
    if(izbor == 2) opcenitoStablo();
    }while(izbor != 0);
 
    system("pause");
    return 0;
}
 
 
//Implementacija opcenitog stabla
 
 
struct Cvor
{
 int Label;
 int PrvoDijete;
 int SljedeciBrat;
};//struct
 
struct tree
{
 Cvor element[1000];
 int first;       
};//struct1
 
tree *InitT(int x,tree *stablo)//inicijalizacija
{
 delete [] stablo->element;
 stablo=new tree;
 stablo->first=0;
 stablo->element[x].Label=x;
 stablo->first++;   
}//InitT
 
int FirstChildT(int x, tree *stablo)
{
 if(x<0) return -1;
 else
 {
  if(x>=0 && ((x+1)!=0)) return stablo->element[x].PrvoDijete;
  else return -1;    
 }   
}//FirstCildT
 
int NextSiblingT(int x, tree *stablo)
{
 if(x<0) return -1;
 else
 {
  if(stablo->element[x].SljedeciBrat!=-1)return stablo->element[x].SljedeciBrat;
  else return -1;    
 }   
}//NextSiblingT
 
int ParentT(int x, tree *stablo)
{
 if(x>0) return x-1;
 else
 {
  if(x==0) return -1;
  else cout<<"Cvor ne postoji"<<endl;    
 }   
}//ParentT
 
int LabelT(int x, tree *stablo)//vratiVrijednost
{
 if(x<0) cout<<"Pogreska"<<endl;
 else
 {
  return stablo->element[x].Label;
 }   
}//LabelT
 
int ChangeLabelT(int x, int y, tree *stablo)
{
 if(x<0) return -1;
 else stablo->element[y].Label=x;   
}//changeLabel
 
int RootT(tree *stablo)
{
 return stablo->element[0].Label;   
}//RootT
 
int CreateT(int x, int y, tree *stablo)//dodavanje
{
 stablo->element[stablo->first].Label=x;
 stablo->element[stablo->first].PrvoDijete=y;
 stablo->first++;
}//CreateT
 
int DeleteT(int x, tree *stablo)//brisanje
{
 if(x<0) return -1;
 else
 {
  if(stablo->element[x].PrvoDijete>0) DeleteT(stablo->element[x].PrvoDijete,stablo);
  else
  {
   stablo->element[x].Label=-1;
   stablo->first--;    
  }    
 }   
}//DeleteT
 
//Implementacija binarnog (polje)
 
 
struct element {
       int label;
       int koristeno;
};
 
struct bt {
       element elements[10000];
};
 
typedef int cvor;
 
bt* InitB(int x, bt* T) {//incijalizacija
    if(T) delete T;
    T = new bt;
    for(int i = 0; i < 10000; i++)
        T->elements[i].koristeno = 0;
    T->elements[1].label = x;
    T->elements[1].koristeno = 1; 
    return T;
}//initB
 
void CreateLeftB(int x, cvor n, bt* T) {//kreiraj lijevo
     if(T->elements[n].koristeno == 0 || T->elements[2*n].koristeno == 1) {
           cout << "Greska" << endl << endl;
           return;
     }
     T->elements[2*n].koristeno = 1;
     T->elements[2*n].label = x;
}//CreateLeftB
 
void CreateRightB(int x, cvor n, bt* T) {//kreiraj desno
        if(T->elements[n].koristeno == 0 || T->elements[2*n+1].koristeno == 1)
        {
        cout << "Greska" << endl << endl;
        return;
    }
    T->elements[2*n+1].koristeno = 1;
    T->elements[2*n+1].label = x;
}//CreateRightB
 
cvor LeftChildB(cvor n, bt* T) {//lijevo dijete
     if(T->elements[n].koristeno == 0) 
           return 0;
     if(T->elements[2*n].koristeno == 1) 
           return 2*n;
     else return 0;
}//LeftCildB
 
cvor RightChildB(cvor n, bt* T) {//desno dijete
     if(T->elements[n].koristeno == 0) return 0;
     if(T->elements[2*n+1].koristeno == 1) return 2*n+1;
     else return 0;
}//RightCildB
 
cvor ParentB(cvor n, bt* T) {
     if(n == 1) return 0;
     if(n%2) n--;
     return n/2;
}//ParentB
 
int LabelB(cvor n, bt* T) {
          return T->elements[n].label;
}//LabelB
 
void ChangeLabelB(int x, cvor n, bt* T) {//zamjena
     if(T->elements[n].koristeno == 0) return;
     T->elements[n].label = x;
}//ChangeLabelB
 
cvor RootB(bt* T) {
     if(T->elements[1].koristeno == 0) return 0;
     return 1;
}//RootB
 
void DeleteB(cvor n, bt* T) {
    T->elements[n].koristeno = 0;
        if (LeftChildB(n, T)) DeleteB(LeftChildB(n, T), T);
        if (RightChildB(n, T)) DeleteB(RightChildB(n, T), T);
}//DeleteB
 
 
//Implementacija binarnog (pokazivac)
 
 
struct element {
    int label;
    element *left,*right;
};
 
typedef element *cvor;
typedef element bt;
 
bt* InitB(int x, bt* T) {//inicijalizacija
    T = new element;
    T->label = x;
    T->left = NULL;
    T->right = NULL;
    return T;
}//initB
 
void CreateLeftB(int x, cvor n, bt* T) {//novi lijevi
    if(n->left) {
        cout << "Greska" << endl << endl;
        return;
    }
    cvor novi = new element;
    n->left = novi;
    novi->label = x;
    novi->left = NULL;
    novi->right = NULL;
}//CreateLeftB
 
void CreateRightB(int x, cvor n, bt* T) {//novi desni
    if(n->right) {
        cout << "Greska" << endl << endl;
        return;
    }
    cvor novi = new element;
    n->right = novi;
    novi->label = x;
    novi->left = NULL;
    novi->right = NULL;
}//createRightB
 
cvor ParentB(cvor n, bt* T) {
    if (n == T) return NULL;
        cvor roditelj = NULL;
        if (T->left) {
                if (T->left == n) return T;
                else roditelj =  ParentB(n, T->left);
        }
        if(T->right) {
                if (T->right == n) return T;
                else roditelj = ParentB(n, T->right);
        }       
        return roditelj;
}//parentB
 
int LabelB(cvor n, bt* T) {//vrati oznaku
    return n->label;
}//labelB
 
void ChangeLabelB(int x, cvor n, bt* T) {
    if(!n) return;
    n->label = x;
}//changeLabelB
 
cvor LeftChildB(cvor n, bt* T) {//lijevo dijete
    if(!n || !n->left) return NULL;
    return n->left;  
}//leftCildB
 
cvor RightChildB(cvor n, bt* T) {//desno dijete
    if(!n || !n->right) return NULL;
    return n->right;  
}//rightCildB
 
cvor RootB(bt* T) {
    if(!T) return NULL;
    return T;
}//rootB
 
void DeleteB(cvor n, bt* T) {
    static bool jednom = false;
    if(!jednom) {
      cvor roditelj = ParentB(n, T);
      if(roditelj->left == n) roditelj->left = NULL;
      else roditelj->right = NULL;
      jednom = true;
    }
 
    if(n->left) DeleteB(n->left, T);
    if(n->right) DeleteB(n->right, T);
    delete n;
}//deleteB