//implementacija_b_pokazivaci
 
struct element{
    int label;
    struct element *left,*right;
};
typedef struct element *node;
typedef struct element *tr;
 
void InitB(int x,tr *T){
     T = new tr;
     T.label = x;
     T->left = NULL;
     T->right = NULL;
 
}
node RootB(tr *T){
     return T;
}
 
node LeftChildB(node n,tr *T){ 
     return n->left;    
}
node RightChildB(node n,tr *T){
     return n->right; 
}
int LabelB(node n,tr *T){
     return n->label;
}
int CreateLeftB(int x,node n,tr *T){
    if(!n->left){
     element *novi = new element;
     n->left = novi;
     novi->left = NULL;
     novi->right = NULL;
     novi->label = x;
     return 1;
    }
    else return 0;
}
int CreateRightB(int x,node n,tr *T){
    if(!n->right){
     element *novi = new element;
     n->right = novi;
     novi->left = NULL;
     novi->right = NULL;
     novi->label = x;
     return 1;
    }
    else return 0;
}
node ParentB(node n,tr *T){
   node cvor = NULL; 
   if(n == T) return 0;
   if(T->left){
      if(T->left == n){
         cvor = T;
         return cvor;
      }
      cvor = ParentB(n,T->left);
   }
   if(!cvor)
   if(T->right){
      if(T->right == n){
         cvor = T;
         return cvor;
      }
      cvor = ParentB(n,T->right);
   }
   return cvor;
}
void DeleteB(node n,tr *T){
   if(n->left) DeleteB(n->left,T);
   if(n->right) DeleteB(n->right,T);
   node cvor = ParentB(n,T);
   if(cvor!=0){
      if(cvor->left == n) cvor->left = NULL;
      else cvor->right=NULL;
      delete n;
   }
}
void ChangeLabelB(int x,node n,tr *T){
     n->label = x;
    }
//implementacija_b_polje
 
struct elem{
    int label;
    bool used;
};
struct tr{
    struct elem element[10000];
};
typedef struct tr *T;
typedef int node;
 
int ParentB(int n, tr *T){
     if (n=1) return -1;
     if (n%2==0)return n/2; 
        else return n/2-1;
}
 
int LeftChildB(int n, tr *T){
        if(!T->element[n].used) return -1;
        else return n*2;
}
int RightChildB(int n, tr *T){
        if(!T->element[n].used) return -1;
        else return n*2+1;
}
 
int LabelB(int n, tr *T){
        if(T->element[n].used)return T->element[n].label;
        else return -1;
}
 
void ChangeLabelB(int x,int n, tr *T){
        if(T->element[n].used)T->element[n].label=x;
}
 
int RootB(tr *T){
        if(T->element[1].used) return 1;        
        else return -1;
}
 
int CreateLeftB(int x,int n, tr *T){
        if(T->element[n*2].used) return -1;
        T->element[n*2].used=true;
        T->element[n*2].label=x;
}
int CreateRightB(int x,int n, tr *T){
if(T->element[n*2+1].used) return -1;
        T->element[n*2+1].used=true;
        T->element[n*2+1].label=x;
}
 
void DeleteB(int n, tr *T){
        if(LeftChildB(n,T)!=-1)DeleteB(LeftChildB(n,T),T);
        if(RightChildB(n,T)!=-1)DeleteB(RightChildB(n,T),T);
        T->element[n].used = 0;
}
 
void InitB(int x,tr *T){
    for(int i=0;i<10000;i++) T->element[i].used=false;
        T->element[1].label=x;
        T->element[1].used=true;
}
//implementacija obilezenje
 
using namespace std;
 
void Preorder(int i, tr *T) {  
    int c;
    cout<<T->element[i].label<<", ";
    c = T->element[i].firstchild;
    while (c!=-1) {
        Preorder(c,T);
        c = T->element[c].nextsibling;
    }
}
 
void Postorder(int i, tr *T) {  
    int c;
 
    c = T->element[i].firstchild;
    while (c!=-1) {
        Postorder(c,T);
        c = T->element[c].nextsibling;
    }
    cout<<T->element[i].label<<", ";
}
 
void Inorder(int i, tr *T) {  
    int c;    
      c = T->element[i].firstchild;     
    while (c!=-1) {            
        Inorder(c,T);     
        cout<<T->element[i].label<<", ";  
        c = T->element[c].nextsibling;      
   }
 
}
//implementacija opcenito stabla
 
using namespace std;
struct el{
     int label,firstchild,nextsibling;
};
 
struct tr{
    el element[1000];
    int first;       
};
 
tr *InitT(int x,tr *T){    
    T=new tr;
    T->first=0;
    T->element[0].label=x;
    T->element[0].firstchild=-1;
    T->element[0].nextsibling=-1;
    T->first++;   
    return T;
}
 
int FirstChildT(int x, tr *T){
    return T->element[x].firstchild;
}
 
int NextSiblingT(int x, tr *T){            
            return T->element[x].nextsibling;        
}
 
int ParentT(int x, tr *T){
    if(x==T->first) return -1;
    for(int i=0;i<T->first;i++){
        if(T->element[i].firstchild==x) return i;
        if(T->element[T->element[i].firstchild].nextsibling==x) return i;   
    }   
}
 
int LabelT(int x, tr *T){
  return T->element[x].label;
 
}
 
int ChangeLabelT(int x, int y, tr *T){
         if(x<0) return -1;
         else T->element[y].label=x;   
}
 
int RootT(tr *T){
    return 0;   
}
 
 
void CreateT(int x,int n,tr *T){    
    if(T->element[n].firstchild==-1){       
        T->element[T->first].label=x;
        T->element[n].firstchild=T->first;
        T->element[T->first].nextsibling=-1;
        T->element[T->first++].firstchild=-1;        
        }
    else{        
        T->element[T->first].label=x;
        T->element[T->first].firstchild=-1;       
        T->element[T->first].nextsibling=T->element[T->element[n].firstchild].nextsibling;
        T->element[T->element[n].firstchild].nextsibling=T->first++;    
    } 
}
int DeleteT(int x, tr *T){
    if(x<0) return -1;
    else{
        if(T->element[x].firstchild>0) DeleteT(T->element[x].firstchild,T);
        else{
            T->element[x].label=-1;
            T->first--;    
        }    
    }   
}
//main
 
#include<iostream>
using namespace std;
 
#include "implementacija_b_pokazivaci.h"
#include "implementacija_opcenito_stablo.h"
#include "implementacija_obilazenje.h"
#include "implementacija_b_polje.h"
void prvi(){ 
     tr *T;
     int vrijednost;
     cout<<"Korijen je 1"<<endl;
     T=InitT(1,T);
 
     cout<<"Unesi (cvor 1, dijete 0): ";cin>>vrijednost;         
     CreateT(vrijednost,0,T);     
     cout<<"Unesi (cvor 2, dijete 0): ";cin>>vrijednost;
     CreateT(vrijednost,0,T);    
     cout<<"Unesi (cvor 3, dijete 1): ";cin>>vrijednost;
     CreateT(vrijednost,1,T);    
     cout<<"Unesi (cvor 3,dijete 1): ";cin>>vrijednost;
     CreateT(vrijednost,1,T);
 
     for(int i=0;i<T->first;i++){
            cout<<i<<"  : "<<LabelT(i,T)<<"  "<<FirstChildT(i,T)<<"  "<<NextSiblingT(i,T)<<endl;
        }
 
     cout<<"Preorder: ";
     Preorder(0,T);
     cout<<"\nPostorder: ";Postorder(0,T);
     cout<<"\nInorder: ";Inorder(0,T);
     cout<<endl;
 
     cout<<"Unesite novu vrijednost treceg cvora: ";cin>>vrijednost;
     ChangeLabelT(vrijednost,3,T);
 
     cout<<"Brisanje cvora 2"<<endl;
     DeleteT(2,T);
 
    for(int i=0;i<T->first;i++){
            cout<<i<<"  : "<<LabelT(i,T)<<"  "<<FirstChildT(i,T)<<"  "<<NextSiblingT(i,T)<<endl;
        }
    cout<<"Dealokacija stabla..."<<endl<<endl;
    DeleteT(0,T);
}
 
void drugi(){
    int x;
    cout << "Inicijalizacija stabla" << endl;
    tr *T=InitB(1,T);
    cout << "Korijen: " << LabelB(RootB(T), T)<< endl << endl;
 
    cout << "Lijevo dijete: ";cin>>x;
    CreateLeftB(x, RootB(T), T);
    cout << "Desno dijete";cin>>x;
    CreateRightB(x, RootB(T), T);
    cout << "Lijevo dijete od 1: ";cin>>x;
    CreateLeftB(x, RootB(T), T);
      cout << "Desno dijete od 1";cin>>x;
    CreateRightB(x, RootB(T), T);
 
    cout << "Mijenjanje cvora 2: "; cin>>x;
    ChangeLabelB(x, LeftChildB(RightChildB(RootB(T), T), T), T);
 
 
    cout << "Brisanje cvora 0" << endl;
    DeleteB(RootB(T), T);
 
    }
 
int main() {
    int izbor;
    do{
 
    cout<<"1. Opcenito stablo i algoritmi prohodjenja\n"
        <<"2. binarno stablo\n\n"
        <<"9. Izlaz iz programa\n"; 
 
    cin >> izbor;
 
    if(izbor == 1) prvi();
    else drugi();
    }while(izbor != 0);
 
    return 0;
}