
//#include "binarno_polje.h"
int bin_st[1000];

int RootB (int bin_st[]) {
    return 1;
}
int LabelB (int n, int bin_st[]) {
    return bin_st[n];
}
int ParentB (int n, int bin_st[]) {
    if (n==RootB(bin_st)) return -1;
    if (n%2) return (n-1)/2;
    else return n/2;
}
int LeftChildB (int n, int bin_st[]) {
    if (LabelB(n*2, bin_st)==-1) return -1;
    return n*2;
}
int RightChildB (int n, int bin_st[]) {
    if (LabelB(n*2+1, bin_st)==-1) return -1;
    return n*2+1;
}
void ChangeLabelB (int x, int n, int bin_st[]) {
     bin_st[n]=x;
}
bool CreateLeftB (int x, int n, int bin_st[]) {
    if (LeftChildB(n, bin_st)!=-1) return false;
    bin_st[n*2]=x;
    return true;
}
bool CreateRightB (int x, int n, int bin_st[]) {
    if (RightChildB(n, bin_st)!=-1) return false;
    bin_st[n*2+1]=x;
    return true;
}
void DeleteB (int n, int bin_st[]) {
     if (LeftChildB(n, bin_st)!=-1) DeleteB(LeftChildB(n, bin_st), bin_st);
     if (RightChildB(n, bin_st)!=-1) DeleteB(RightChildB(n, bin_st), bin_st);
     bin_st[n]=-1;
}
void InitB (int n, int bin_st[]) {
     for (int i=0; i<1000; i++) bin_st[i]=-1;
     bin_st[1]=n;
}


//#include "opcenito_stablo.h"
struct elem {
       int lab, ch, sib;
       };
struct tr {
       elem el[1000];
       int first;
       };
tr t;

int FirstChildT (int n, tr t) {
    return t.el[n].ch;
}
int NextSiblingT (int n, tr t) {
    return t.el[n].sib;
}
int LabelT (int n, tr t) {
    return t.el[n].lab;
}
int ParentT (int n, tr t) {
    for (int i=0; i<1000; i++) {
        if (FirstChildT(i, t)==n) return i;
        if (NextSiblingT(i, t)==n) return ParentT(i, t);
        }
    return -1;
}
int RootT (tr t) {
    return t.first;
}
int CreateT (int x, int n, tr &t) {
     int a=0;
     while (LabelT(a, t)!=-1) a++;
     t.el[a].lab=x;
     t.el[a].ch=-1;
     t.el[a].sib=-1;
     if (t.el[n].ch!=-1) {
        n=FirstChildT(n, t);
        while (NextSiblingT(n, t)!=-1) n=NextSiblingT(n, t);
        t.el[n].sib=a;
        }
     else t.el[n].ch=a;
     return a;
}
void ChangeLabelT (int x, int n, tr &t) {
     t.el[n].lab=x;
}
void DeleteT (int n, tr &t) {
     int a;
     if (FirstChildT(n, t)!=-1) {
        a=FirstChildT(n, t);
        DeleteT(a, t);
        while (NextSiblingT(a, t)!=-1) {
              a=NextSiblingT(a, t);
              DeleteT(a, t);
              }
        }
     t.el[n].lab=-1;
     if (n!=RootT(t) && FirstChildT(ParentT(n, t), t)==n) t.el[ParentT(n, t)].ch=NextSiblingT(n, t);
     else if (n!=RootT(t)) {
          a=FirstChildT(ParentT(n, t), t);
          while (NextSiblingT(a, t)!=n) a=NextSiblingT(a, t);
          t.el[a].sib=NextSiblingT(n, t);
          }
}
void InitT (int x, tr &t) {
     t.first=0;
     t.el[0].lab=x;
     t.el[0].ch=-1;
     t.el[0].sib=-1;
     for (int i=1; i<1000; i++) {
         t.el[i].lab=-1;
         t.el[i].ch=-1;
         t.el[i].sib=-1;
         }
}


//#include "ophodjenje_stabla.h"
using namespace std;

void PreOrder (int a) {
     cout << LabelT(a, t) << " ";
     if (FirstChildT(a, t)!=-1) PreOrder(FirstChildT(a, t));
     if (NextSiblingT(a, t)!=-1) PreOrder(NextSiblingT(a, t));
}
void InOrder (int a) {
     if (FirstChildT(a, t)!=-1) InOrder(FirstChildT(a, t));
     cout << LabelT(a, t) << " ";
     if (FirstChildT(a, t)!=-1) {
        a=FirstChildT(a, t);
        while (NextSiblingT(a, t)!=-1) {
              a=NextSiblingT(a, t);
              InOrder(a);
              }
        }
}
void PostOrder (int a) {
     if (FirstChildT(a, t)!=-1) PostOrder(FirstChildT(a, t));
     int b=a;
     if (FirstChildT(b, t)!=-1) {
        b=FirstChildT(b, t);
        while (NextSiblingT(b, t)!=-1) {
              b=NextSiblingT(b, t);
              PostOrder(b);
              }
        }
     cout << LabelT(a, t) << " ";
}


//main
#include 

#include "binarno_polje.h"
#include "opcenito_stablo.h"
#include "ophodjenje_stabla.h"
using namespace std;
int main () {
    int a, b, c, d;
    bool v=false, w=false, z=false;
    do {
        system ("cls");
        cout << "1. Implementacija opcenitog stabla pomocu polja\n";
        cout << "2. Implementacija algoritama ophodjenja stabla\n";
        cout << "3. Implementacija binarnog stabla pomocu polja\n";
        cout << "0. Izlaz iz programa\n";
        cout << "Vas izbor: ";
        do cin >> a; while (a<0 || a>4);
        system ("cls");
        switch (a) {
               case 1:
                    cout << "1. Inicijalizacija polja\n";
                    cout << "2. Roditelj cvora\n";
                    cout << "3. Prvo dijete cvora\n";
                    cout << "4. Sljedeci brat cvora\n";
                    cout << "5. Oznaka cvora\n";
                    cout << "6. Korijen stabla\n";
                    cout << "7. Novi cvor\n";
                    cout << "8. Promjena labele\n";
                    cout << "9. Brisanje cvora\n";
                    cout << "Vas izbor: ";
                    do cin >> b; while (b<1 || b>9);
                    system ("cls");
                    if (b!=1 && !v) {
                       cout << "Stablo nije inicijalizirano!\n";
                       system ("pause");
                       break;
                       }
                    switch (b) {
                           case 1:
                                cout << "Unesite oznaku korijena stabla: ";
                                cin >> c;
                                InitT(c, t);
                                v=true;
                                break;
                           case 2:
                                cout << "Unesite cvor kojem zelite naci roditelja: ";
                                cin >> c;
                                if (LabelT(c, t)==-1) {
                                   cout << "Cvor ne postoji!\n";
                                   system ("pause");
                                   break;
                                   }
                                c=ParentT(c, t);
                                if (c==-1) cout << "Cvor nema roditelja.\n";
                                else cout << "Roditelj tog cvora je cvor " << c << ".\n";
                                system ("pause");
                                break;
                           case 3:
                                cout << "Unesite cvor kojem zelite naci prvo dijete: ";
                                cin >> c;
                                if (LabelT(c, t)==-1) {
                                   cout << "Cvor  ne postoji!\n";
                                   system ("pause");
                                   break;
                                   }
                                c=FirstChildT(c, t);
                                if (c==-1) cout << "Ccvor nema potomaka.\n";
                                else cout << "Prvo dijete tog cvora je cvor " << c << ".\n";
                                system ("pause");
                                break;
                           case 4:
                                cout << "Unesite cvor kojem zelite naci sljedeceg brata: ";
                                cin >> c;
                                if (LabelT(c, t)==-1) {
                                   cout << "Taj cvor ne postoji!\n";
                                   system ("pause");
                                   break;
                                   }
                                c=NextSiblingT(c, t);
                                if (c==-1) cout << "Cvor nema brace s desna.\n";
                                else cout << "Sljedeci brat tog cvora je cvor " << c << ".\n";
                                system ("pause");
                                break;
                           case 5:
                                cout << "Unesite cvor kojem zelite vidjeti labelu: ";
                                cin >> c;
                                if (LabelT(c, t)==-1) {
                                   cout << "Cvor ne postoji!\n";
                                   system ("pause");
                                   break;
                                   }
                                cout << "Labela tog cvora je " << LabelT(c, t) << ".\n";
                                system ("pause");
                                break;
                           case 6:
                                cout << "Korijen stabla je cvor " << RootT(t) << ".\n";
                                system ("pause");
                                break;
                           case 7:
                                cout << "Unesite cvor kojem stvarate dijete: ";
                                cin >> d;
                                if (LabelT(d, t)==-1) {
                                   cout << "Cvor ne postoji!\n";
                                   system ("pause");
                                   break;
                                   }
                                cout << "Unesite oznaku za cvor koji stvarate: ";
                                cin >> c;
                                cout << "Cvor je stvoren na poziciji " << CreateT(c, d, t) << ".\n";
                                system ("pause");
                                break;
                           case 8:
                                cout << "Unesite cvor kojem zelite promijeniti labelu: ";
                                cin >> d;
                                if (LabelT(d, t)==-1) {
                                   cout << "Cvor ne postoji!\n";
                                   system ("pause");
                                   break;
                                   }
                                cout << "Unesite novu labelu: ";
                                cin >> c;
                                ChangeLabelT(c, d, t);
                                break;
                           case 9:
                                cout << "Unesite cvor kojeg zelite obrisati sa njegovim potomcima: ";
                                cin >> d;
                                if (LabelT(d, t)==-1) {
                                   cout << "Taj cvor ne postoji!\n";
                                   system ("pause");
                                   break;
                                   }
                                DeleteT(d, t);
                                if (!d) v=false;
                           }
                    break;
               case 2:
                    if (!v) {
                       cout << "Cvor nije inicijaliziran!\n";
                       system ("pause");
                       break;
                       }
                    cout << "1.preorder "<> b;}
 while (b<1 || b>3);
                    switch (b) {
                           case 1:
                                PreOrder(RootT(t));
                                break;
                           case 2:
                                InOrder(RootT(t));
                                break;
                           case 3:
                                PostOrder(RootT(t));
                           }
                    cout << "\n";
                    system ("pause");
                    break;
               case 3:
                    cout << "1. Inicijalizacija binarnog stabla.\n";
                    cout << "2. Korijen binarnog stabla\n";
                    cout << "3. Oznaka cvora\n";
                    cout << "4. Roditelj cvora\n";
                    cout << "5. Lijevo dijete cvora\n";
                    cout << "6. Desno dijete cvora\n";
                    cout << "7. Promjena oznake cvora\n";
                    cout << "8. Stvaranje lijevog djeteta cvora\n";
                    cout << "9. Stvaranje desnog djeteta cvora\n";
                    cout << "10. Brisanje cvora\n";
                    cout << "Unesite izbor: ";
                    do cin >> b; while (b<1 || b>10);
                    system ("cls");
                    if (b!=1 && !w) {
                       cout << "Binarno stablo nije inicijalizirano!\n";
                       system ("pause");
                       break;
                       }
                    switch (b) {
                           case 1:
                               cout << "Unesite labelu korijena binarnog stabla: ";
                               cin >> c;
                               InitB(c, bin_st);
                               w=true;
                               break;
                           case 2:
                                cout << "Korijen binarnog stabla je cvor " << RootB(bin_st) << ".\n";
                                system ("pause");
                                break;
                           case 3:
                                cout << "Unesite cvor kojem zelite vidjeti labelu: ";
                                cin >> c;
                                if (LabelB(c, bin_st)==-1) {
                                   cout << "Taj cvor ne postoji!\n";
                                   system ("pause");
                                   break;
                                   }
                                cout << "Oznaka tog cvora je " << LabelB(c, bin_st) << ".\n";
                                system ("pause");
                                break;
                           case 4:
                                cout << "Unesite cvor kojem zelite naci roditelja: ";
                                cin >> c;
                                if (LabelB(c, bin_st)==-1) {
                                   cout << "Taj cvor ne postoji!\n";
                                   system ("pause");
                                   break;
                                   }
                                c=ParentB(c, bin_st);
                                if (c==-1) cout << "Taj cvor nema roditelja.\n";
                                else cout << "Roditelj tog cvora je cvor " << c << ".\n";
                                system ("pause");
                                break;
                           case 5:
                                cout << "Unesite cvor kojem zelite naci lijevo dijete: ";
                                cin >> c;
                                if (LabelB(c, bin_st)==-1) {
                                   cout << "Taj cvor ne postoji!\n";
                                   system ("pause");
                                   break;
                                   }
                                c=LeftChildB(c, bin_st);
                                if (c==-1) cout << "Taj cvor nema lijevo dijete.\n";
                                else cout << "Lijevo dijete tog cvora je cvor " << c << ".\n";
                                system ("pause");
                                break;
                           case 6:
                                cout << "Unesite cvor kojem zelite naci desno dijete: ";
                                cin >> c;
                                if (LabelB(c, bin_st)==-1) {
                                   cout << "Taj cvor ne postoji!\n";
                                   system ("pause");
                                   break;
                                   }
                                c=RightChildB(c, bin_st);
                                if (c==-1) cout << "Taj cvor nema desno dijete.\n";
                                else cout << "Desno dijete tog cvora je cvor " << c << ".\n";
                                system ("pause");
                                break;
                           case 7:
                                cout << "Unesite cvor kojem zelite promijeniti labelu: ";
                                cin >> d;
                                if (LabelB(d, bin_st)==-1) {
                                   cout << "Taj cvor ne postoji!\n";
                                   system ("pause");
                                   break;
                                   }
                                cout << "Unesite novu labelu: ";
                                cin >> c;
                                ChangeLabelB(c, d, bin_st);
                                break;
                           case 8:
                                cout << "Unesite cvor kojem stvarate lijevo dijete: ";
                                cin >> d;
                                if (LabelB(d, bin_st)==-1) {
                                   cout << "Taj cvor ne postoji!\n";
                                   system ("pause");
                                   break;
                                   }
                                cout << "Unesite oznaku za cvor koji stvarate: ";
                                cin >> c;
                                if (CreateLeftB(c, d, bin_st)) cout << "Cvor je stvoren na poziciji " << d*2 << ".\n"; 
                                else cout << "Cvor vec ima lijevo dijete!\n";
                                system ("pause");
                                break;
                           case 9:
                                cout << "Unesite cvor kojem stvarate desno dijete: ";
                                cin >> d;
                                if (LabelB(d, bin_st)==-1) {
                                   cout << "Taj cvor ne postoji!\n";
                                   system ("pause");
                                   break;
                                   }
                                cout << "Unesite labelu za cvor koji stvarate: ";
                                cin >> c;
                                if (CreateRightB(c, d, bin_st)) cout << "Cvor je stvoren na poziciji " << d*2 << ".\n"; 
                                else cout << "Cvor vec ima desno dijete!\n";
                                system ("pause");
                                break;
                           case 10:
                                cout << "Unesite cvor kojeg zelite obrisati sa njegovim potomcima: ";
                                cin >> d;
                                if (LabelB(d, bin_st)==-1) {
                                   cout << "Taj cvor ne postoji!\n";
                                   system ("pause");
                                   break;
                                   }
                                DeleteB(d, bin_st);
                                if (d==1&& a==3) w=false;                           }
                    break;
                           
                           
               }
        } while (a);
    return 0;   
}