//opcenito stablo
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;
         }
}


//obilazak stabla
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) << " ";
}



//bin_polje.h

int bin_tree[1000];

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


#include <iostream>
#include "opcenito_stablo.h"
#include "bin_polje.h"
#include "obilazak.h"
using namespace std;

int main () {
    int a, b, c, d;
    bool inicijalizirano=false, inicijalizirano2=false;
    do {
        cout<<"-----------------------------------------------------"<<endl;
        cout << "1. Opcenito stablo (prvo dijete - sljedeci brat).\n";
        cout << "2. Obilazak stabla (preorder, inorder, postorder)\n";
        cout << "3. Binarno stablo\n";
        cout << "0. Izlaz iz programa\n";
        cout << "Izbor: ";
        do{
             cin >> a;} while (a<0 || a>4);
        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 oznake cvora\n";
                    cout << "9. Brisanje cvora\n";
                    cout << "Izbor: ";
                    do {
                         cin >> b; }while (b<1 || b>9);
                    if (b!=1 && !inicijalizirano) {
                       cout << "Stablo nije inicijalizirano!\n";
                       break;
                       }
                    switch (b) {
                           case 1:
                                cout << "Unesite oznaku korijena stabla: ";
                                cin >> c;
                                InitT(c, t);
                                inicijalizirano=true;
                                break;
                           case 2:
                                cout << "Unesite cvor za koji trazite roditelja: ";
                                cin >> c;
                                if (LabelT(c, t)==-1) {
                                   cout << "Cvor ne postoji!\n";
                                   break;
                                   }
                                c=ParentT(c, t);
                                if (c==-1) cout << "Cvor nema roditelja.\n";
                                else cout << "Roditelj ovog cvora je cvor " << c << ".\n";
                                break;
                           case 3:
                                cout << "Unesite cvor za koji trazite prvo dijete: ";
                                cin >> c;
                                if (LabelT(c, t)==-1) {
                                   cout << "Cvor ne postoji!\n";
                                   break;
                                   }
                                c=FirstChildT(c, t);
                                if (c==-1) cout << "Cvor nema potomaka.\n";
                                else cout << "Prvo dijete ovog cvora je cvor " << c << ".\n";
                                break;
                           case 4:
                                cout << "Unesite cvor za koji trazite sljedeceg brata: ";
                                cin >> c;
                                if (LabelT(c, t)==-1) {
                                   cout << "Cvor ne postoji!\n";
                                   break;
                                   }
                                c=NextSiblingT(c, t);
                                if (c==-1) cout << "Cvor nema brace s desna.\n";
                                else cout << "Sljedeci brat ovog cvora je cvor " << c << ".\n";
                                break;
                           case 5:
                                cout << "Unesite cvor za koji zelite vidjeti oznaku: ";
                                cin >> c;
                                if (LabelT(c, t)==-1) {
                                   cout << "Cvor ne postoji!\n";
                                   break;
                                   }
                                cout << "Oznaka ovog cvora je " << LabelT(c, t) << ".\n";
                                break;
                           case 6:
                                cout << "Korijen stabla je cvor " << RootT(t) << ".\n";
                                break;
                           case 7:
                                cout << "Unesite cvor kojem dodajete dijete: ";
                                cin >> d;
                                if (LabelT(d, t)==-1) {
                                   cout << "Cvor ne postoji!\n";
                                   break;
                                   }
                                cout << "Unesite oznaku za cvor koji dodajete: ";
                                cin >> c;
                                cout << "Cvor je stvoren na poziciji " << CreateT(c, d, t) << ".\n";
                                break;
                           case 8:
                                cout << "Unesite cvor kojem mijenjate oznaku: ";
                                cin >> d;
                                if (LabelT(d, t)==-1) {
                                   cout << "Cvor ne postoji!\n";
                                   break;
                                   }
                                cout << "Unesite novu oznaku: ";
                                cin >> c;
                                ChangeLabelT(c, d, t);
                                break;
                           case 9:
                                cout << "Unesite cvor kojeg zelite obrisati: ";
                                cin >> d;
                                if (LabelT(d, t)==-1) {
                                   cout << "Cvor ne postoji!\n";
                                   break;
                                   }
                                DeleteT(d, t);
                                if (!d) inicijalizirano=false;
                           }
                    break;
               case 2:
                    if (!inicijalizirano) {
                       cout << "Cvor nije inicijaliziran!\n";
                       break;
                       }
                    cout << "1. Preorder." <<endl;
                    cout << "2. Inorder." <<endl;
                    cout << "3. Postorder." <<endl;
                    cout <<"Izbor: ";
                    do {
                         cin >> 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";
                    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. Dodavanje lijevog djeteta cvora\n";
                    cout << "9. Dodavanje desnog djeteta cvora\n";
                    cout << "10. Brisanje cvora\n";
                    cout << "Unesite izbor: ";
                    do {
                         cin >> b;} while (b<1 || b>10);
                    if (b!=1 && !inicijalizirano2) {
                       cout << "Binarno stablo nije inicijalizirano!\n";
                       break;
                       }
                    switch (b) {
                           case 1:
                               cout << "Unesite oznaku korijena binarnog stabla: ";
                               cin >> c;
                               InitB(c, bin_tree);
                               inicijalizirano2=true;
                               break;
                           case 2:
                                cout << "Korijen binarnog stabla je cvor " << RootB(bin_tree) << ".\n";
                                break;
                           case 3:
                                cout << "Unesite cvor za koji zelite vidjeti oznaku: ";
                                cin >> c;
                                if (LabelB(c, bin_tree)==-1) {
                                   cout << "Cvor ne postoji!\n";
                                   break;
                                   }
                                cout << "Oznaka ovog cvora je " << LabelB(c, bin_tree) << ".\n";
                                break;
                           case 4:
                                cout << "Unesite cvor za koji zelite naci roditelja: ";
                                cin >> c;
                                if (LabelB(c, bin_tree)==-1) {
                                   cout << "Cvor ne postoji!\n";
                                   break;
                                   }
                                c=ParentB(c, bin_tree);
                                if (c==-1) cout << "Taj cvor nema roditelja.\n";
                                else cout << "Roditelj ovog cvora je cvor " << c << ".\n";
                                break;
                           case 5:
                                cout << "Unesite cvor za koji trazite lijevo dijete: ";
                                cin >> c;
                                if (LabelB(c, bin_tree)==-1) {
                                   cout << "Cvor ne postoji!\n";
                                   break;
                                   }
                                c=LeftChildB(c, bin_tree);
                                if (c==-1) cout << "Cvor nema lijevo dijete.\n";
                                else cout << "Lijevo dijete ovog cvora je cvor " << c << ".\n";
                                break;
                           case 6:
                                cout << "Unesite cvor za koji trazite desno dijete: ";
                                cin >> c;
                                if (LabelB(c, bin_tree)==-1) {
                                   cout << "Cvor ne postoji!\n";
                                   break;
                                   }
                                c=RightChildB(c, bin_tree);
                                if (c==-1) cout << "Cvor nema desno dijete.\n";
                                else cout << "Desno dijete ovog cvora je cvor " << c << ".\n";
                                break;
                           case 7:
                                cout << "Unesite cvor kojem zelite promijeniti oznaku: ";
                                cin >> d;
                                if (LabelB(d, bin_tree)==-1) {
                                   cout << "Cvor ne postoji!\n";
                                   break;
                                   }
                                cout << "Unesite novu oznaku: ";
                                cin >> c;
                                ChangeLabelB(c, d, bin_tree);
                                break;
                           case 8:
                                cout << "Unesite cvor kojem dodajete lijevo dijete: ";
                                cin >> d;
                                if (LabelB(d, bin_tree)==-1) {
                                   cout << "Cvor ne postoji!\n";
                                   break;
                                   }
                                cout << "Unesite oznaku za cvor koji dodajete: ";
                                cin >> c;
                                if (CreateLeftB(c, d, bin_tree)) cout << "Cvor je dodan na poziciju " << d*2 << ".\n";
                                else cout << "Cvor vec ima lijevo dijete!\n";
                                break;
                           case 9:
                                cout << "Unesite cvor kojem dodajete desno dijete: ";
                                cin >> d;
                                if (LabelB(d, bin_tree)==-1) {
                                   cout << "Cvor ne postoji!\n";
                                   break;
                                   }
                                cout << "Unesite oznaku za cvor koji dodajete: ";
                                cin >> c;
                                if (CreateRightB(c, d, bin_tree)) cout << "Cvor je dodan na poziciju " << d*2 << ".\n";
                                else cout << "Cvor vec ima desno dijete!\n";
                                break;
                           case 10:
                                cout << "Unesite cvor kojeg zelite obrisati: ";
                                cin >> d;
                                if (LabelB(d, bin_tree)==-1) {
                                   cout << "Cvor ne postoji!\n";
                                   break;
                                   }
                                DeleteB(d, bin_tree);
                                if (d==1&&a==3)inicijalizirano2=false;
                           }
                    break;             
               }
        } while (a);
    return 0;   
}