//Implementacija binarnog stabla preko polja
 
struct element{
       int label;
       int used;
};
struct tr{
       element elements[10000];       
};
 
int ParentT(int n,tr *tree){
    if(n==1) return -1;
    else{
         if(!(n%2))return (n/2);
         else return ((n-1)/2);
         }
}
 
int LeftChildT(int n,tr *tree){
    if(tree->elements[2*n].used) return 2*n;
    else cout << "Cvor " << n << " nema lijevo dijete." << endl;
}
 
int RightChildT(int n,tr *tree){
    if(tree->elements[(2*n)+1].used) return ((2*n)+1);
    else cout << "Cvor " << n << " nema desno dijete." << endl;
}
int LabelT(int n,tr *tree){
    if(tree->elements[n].used) return tree->elements[n].label;
    else cout << "Cvor ne postoji." << endl;
}
 
int ChangeLabelT(int x, int n, tr *tree){
    if(tree->elements[n].used) tree->elements[n].label=x;
    else cout << "Cvor ne postoji u stablu." << endl;
}
 
int RootT(tr *tree){
    if(tree->elements[0].used) return 1;
    else cout << "Stablo nema korijen, ne postoji!" << endl;
}
 
int CreateLeftT(int x, int n, tr *tree){
    if(tree->elements[2*n].used==1) cout << "Cvor je vec popunjen" << endl;
    else {
         tree->elements[2*n].label=x;
         tree->elements[2*n].used=1;
         }
}
 
int CreateRightT(int x, int n, tr *tree){
    if(tree->elements[(2*n)+1].used)cout << "Cvor vec ima desno dijete" << endl;
    else{
         tree->elements[(2*n)+1].label=x;
         tree->elements[(2*n)+1].used=1;
         }
}
int ExistsLeftChild(int n,tr *tree){
    if(tree->elements[n*2].used) return 1;
    else return -1;   
}
int ExistsRightChild(int n, tr *tree){
    if(tree->elements[(2*n)+1].used) return 1;
    else return -1;
}
 
int DeleteT(int n, tr *tree){
    int brl_cvora=1;
    int brd_cvora=1;
    if(tree->elements[n].used){
 
                               while(ExistsLeftChild(brl_cvora,tree)==1) brl_cvora=2*brl_cvora;
                               for(brl_cvora;brl_cvora>n;brl_cvora/2)tree->elements[brl_cvora].used=0;
                               while(ExistsRightChild(brd_cvora,tree)==1) brd_cvora=(brd_cvora*2)+1;
                               for(brd_cvora;brd_cvora>n;(brd_cvora-1)/2) tree->elements[brd_cvora].used=0;
                               }
    tree->elements[n].used=0;
}
int InitT(int x, tr *tree){
    if(tree->elements[0].used)
        for(int i=9999;i>=0;i--){
                tree->elements[i].used=0;
                }
    tree->elements[0].label=x;
    tree->elements[0].used=1;
}
 
 
 
 
 
 
 
 
 
 
//Implementacija binarnog stabla preko pokazivaca
 
struct element{
       int label;
       element *left,*right;
};
typedef struct element *elem;
 
elem ParentT(int n, element *tree){
     element *tekucil=tree->left;
     element *tekucid=tree->right;
     bool nadjen =false;
     while(tekucil){
                    if(tekucil->label==n) return tekucil;
                    tekucil=tekucil->left;
                    }
     if(!tekucil){
                  while(tekucid){
                                 if(tekucid->label==n) return tekucid;
                                 tekucid=tekucid->right;
                                 }
                  }
     if(!tekucid && !tekucil) cout << "Cvor ne postoji u stablu!" << endl;
     }
 
elem LeftChildT(element *n, element *tree){
     return n->left;
     }
elem RightChildT(element *n, element *tree){
     return n->right;
     }
int LabelT(element *n, element *tree){
     return n->label;
     }
int ChangeLabelT(int x, element *n, element *tree){
     n->label=x;
     }
elem RootT(element *tree){
     return tree;
     }
elem CreateLeftT(int x, element *n, element *tree){
     if(n->left==NULL){
                       element *novi;
                       novi=new element;
                       n->left=novi;
                       novi->left=NULL;
                       novi->right=NULL;
                       novi->label=x;
                       }
     else cout << "Lijevi cvor vec postoji!" << endl;
     }
elem CreateRightT(int x,element *n, element *tree){
     if(n->right==NULL){
                        element *novi;
                        novi=new element;
                        n->right=novi;
                        novi->left=NULL;
                        novi->right=NULL;
                        novi->label=x;
                        }
     else cout << "Desni cvor je vec popunjen." << endl;
     }
elem DeleteT(element *n, element *tree){
     element *tekucil;
     tekucil=n->left;
     while(tekucil){
                    while(tekucil->left!=NULL)tekucil=tekucil->left;
                    delete tekucil;
                    while(tekucil->right!=NULL)tekucil=tekucil->right;
                    delete tekucil;
                    tekucil=n->left;
                    }
     element *tekucid;
     tekucid=n->right;
     while(tekucid){
                    while(tekucid->left!=NULL)tekucid=tekucid->left;
                    delete tekucid;
                    while(tekucid->right!=NULL)tekucid=tekucid->right;
                    delete tekucid;
                    tekucid=n->right;
                    }
     delete n;
     }
 
elem InitT(int x, element *tree){
     element *tekucil;
     tekucil=tree->left;
     while(tekucil){
                    while(tekucil->left!=NULL)tekucil=tekucil->left;
                    delete tekucil;
                    while(tekucil->right!=NULL)tekucil=tekucil->right;
                    delete tekucil;
                    tekucil=tree->left;
                    }
     element *tekucid;
     tekucid=tree->right;
     while(tekucid){
                    while(tekucid->left!=NULL)tekucid=tekucid->left;
                    delete tekucid;
                    while(tekucid->right!=NULL)tekucid=tekucid->right;
                    delete tekucid;
                    tekucid=tree->right;
                    }
     delete tree;
     element *novi=new element;
     novi->left=NULL;
     novi->right=NULL;
     novi->label=x;
     cout << "Inicijalizacija gotova!!" << endl;
     }
 
 
 
 
 
 
 
//Implementacija opcenitog stabla
 
struct elem{
       int label;
       int firstchild,nextsibling;
};
struct tr{
       elem elements[10000];
       int first;
};
int ParentT(int n, tr *tree){
     if(n>0)return (n-1);
     else {
          if(n==0)return -1;
          else cout << "Cvor " << n << " ne postoji u stablu." << endl;
          }
     }
 
int FirstChildT(int n,tr *tree){
    if(n<0) cout << "Cvor " << n << " ne postoji u stablu." << endl;
    else{
         if(n>=0 && ((n+1)!=0))return tree->elements[n].firstchild;
         else return -1;
         }
}
 
int NextSiblingT(int n,tr *tree){
    if(n<0)cout <<"Cvor " << n << " ne postoji u stablu." << endl;
    else{
         if(n>=0 && (tree->elements[n].nextsibling!=-1))return tree->elements[n].nextsibling;
         else cout << "Cvor " << n << " je najdesnije dijete." << endl;
         }
}
int LabelT(int n,tr *tree){
     if(n<0)cout << "Cvor " << n << " ne postoji." << endl;
     else{
          if(tree->elements[n].label==-1) cout << "Cvor ne postoji!" << endl;
          else return tree->elements[n].label;
          }
}
int RootT(tr *tree){
    return tree->elements[0].label;
}
int CreateT(int x,int n,tr *tree){
    tree->elements[tree->first].label=n;
    tree->elements[tree->first].firstchild=x;
    tree->first++;
}
int ChangeLabelT(int x,int n,tr *tree){
    if(n<0)cout << "Cvor ne postoji!" << endl;
    else tree->elements[n].label=x;
}
int DeleteT(int n,tr *tree){
    if(n<0) cout << "Cvor ne postoji u stablu." << endl;
    else{
         if(tree->elements[n].firstchild>0)DeleteT(tree->elements[n].firstchild,tree);
         else{
              tree->elements[n].label=-1;
              tree->first--;}
         }
}
int InitT(int x,tr *tree){
    delete [] tree->elements;
    tree->first=0;
    tree->elements[tree->first].label=x;
    tree->first++;
}
 
 
 
 
 
 
 
 
//MAIN
 
 
#include<iostream>
using namespace std;
#include "bstablo_polje.h"
 
int main(){
tr *tree;
tree=new tr;
char dalje;
cout << "----------------------------------" << endl;
cout << "  Dodavanje novog cvora u stablo  " << endl;
cout << "----------------------------------" << endl;
    do{
        cout << endl;
        cout << "Unesite vrijednost lijevog cvora: ";
        int lijevi_cvor;
        cin >>lijevi_cvor;
        cout << "Unesite indeks cvora: ";
        int indeks_cvora;
        cin >> indeks_cvora;
        CreateLeftT(lijevi_cvor,indeks_cvora,tree);
        cout << "Unesite vrijednost desnog cvora: ";
        int desni_cvor;
        cin >> desni_cvor;
        cout << "Unesite indeks cvora: ";
        int ind_c;
        cin >> ind_c;
        CreateRightT(desni_cvor,ind_c,tree);
        cout << "Zelite li jos dijece dodavati? (d/n): ";
        cin >> dalje;
        }while(dalje=='d');
    cout << endl;
    cout << "------------------------" << endl;
    cout << "Roditelj cvora" << endl;
    cout << "------------------------" << endl;
    cout << "Unesite indeks cvora: ";
    int indek;
    cin >> indek;
    ParentT(indek,tree);
    cout << "------------------------" << endl;
    cout << "Lijevo dijete" << endl;
    cout << "------------------------" << endl;
    cout << "Unesite indeks cvora: ";
    cin >> indek;
    LeftChildT(indek,tree);
    cout << "------------------------" << endl;
    cout << "Desno dijete" << endl;
    cout << "------------------------" << endl;
    cout << "Unesite indeks cvora: ";
    cin >> indek;
    RightChildT(indek,tree);
    cout << endl;
    cout << "------------------------" << endl;
    cout << "Vrijednost cvora" << endl;
    cout << "------------------------" << endl;
    cout << "Unesite indeks cvora: ";
    int incv;
    cin >> incv;
    LabelT(incv,tree);
    cout << "------------------------" << endl;
    cout << "Promjena vrijednosti" << endl;
    cout << "------------------------" << endl;
    cout << "Indeks cvora: ";
    cin >> incv;
    cout << "Nova vrijednost: ";
    int nova_vr;
    cin >> nova_vr;
    ChangeLabelT(nova_vr,incv,tree);
    cout << "------------------------" << endl;
    cout << "Korijen cvora" << endl;
    cout << RootT(tree) << endl;
    cout << "------------------------" << endl;
    cout << "Brisanje cvora" << endl;
    cout << "Indeks cvora: ";
    cin >> incv;
    DeleteT(incv,tree);
    cout << "------------------------" << endl;
    cout << "Inicijalizacija cvora" << endl;
    cout << "Nova vrijednost u prvom cvoru: ";
    int nvr_prvi;
    cin >> nvr_prvi;
    InitT(nvr_prvi,tree);
    system("pause");
    return 0;
}