//implementacija pomocu polja

#include <iostream>
using namespace std;

struct element {
       int label;
       int used;
};

struct bt {
       element elements[1000];
};

typedef int node;

node ParentB(node n, bt* T) {
     if(n==1)
             return 0;
     if(n%2) n--;
     return n/2;
}
     
node LeftChildB(node n, bt* T) {
     if(T->elements[n].used==0)
                               return 0;
     if(T->elements[2*n].used==1)
                                 return 2*n;
     else
         return 0;
}
     
node RightChildB(node n, bt* T) {
     if(T->elements[n].used==0)
                               return 0;
     if(T->elements[2*n+1].used==1)
                                   return 2*n+1;
     else
         return 0;
}

int LabelB(node n, bt* T) {
    return T->elements[n].label;
}
    
void ChangeLabelB(int x, node n, bt* T) {
     if(T->elements[n].used==0)
                               return;
     T->elements[n].label=x;
}
     
node RootB(bt* T) {
     if(T->elements[1].used==0)
                               return 0;
     return 1;
}

void CreateLeftB(int x, node n, bt* T) {
     if(T->elements[n].used==0 || T->elements[2*n].used==1) {
                               cout << "Greska!" << endl;
                               return;
                               }
     T->elements[2*n].used=1;
     T->elements[2*n].label=x;
}
     
void CreateRightB(int x, node n, bt* T) {
     if(T->elements[n].used==0 || T->elements[2*n+1].used==1) {
                               cout << "Pogreska!" << endl;
                               return;
                               }
     T->elements[2*n+1].used=1;
     T->elements[2*n+1].label=x;
}
     
void DeleteB(node n, bt* T) {
     T->elements[n].used=0;
     if(LeftChildB(n,T))
                        DeleteB(LeftChildB(n,T),T);
     if(RightChildB(n,T))
                         DeleteB(RightChildB(n,T),T);
}
     
bt* InitB(int x, bt* T) {
    if(T)
         delete T;
    T=new bt;
    for(int i=0; i<1000; i++)
            T->elements[i].used=0;
    T->elements[1].label=x;
    T->elements[1].used=1;
    return T;
}


//implementacija pomocu pokazivaca

#include <iostream>
using namespace std;

struct element {
       int label;
       element *left, *right;
};

typedef element *node;
typedef element bt;

node ParentB(node n, bt* T) {
     if(n==T)
             return NULL;
     node parent=NULL;
     if(T->left) {
                 if(T->left==n)
                               return T;
                 else 
                      parent=ParentB(n,T->left);
                 }
     if(T->right) {
                  if(T->right==n)
                                 return T;
                  else
                      parent=ParentB(n,T->right);
                  }
     return parent;
}

node LeftChildB(node n, bt* T) {
     if(!n || !n->left)
           return NULL;
     return n->left;
}     
     
node RightChildB(node n, bt* T) {
     if(!n || !n->right)
           return NULL;
     return n->right;
}
     
int LabelB(node n, bt* T) {
     return n->label;
}     
     
void ChangeLabelB(int x, node n, bt* T) {
     if(!n)
           return;
     n->label=x;
}
     
node RootB(bt* T) {
     if(!T)
           return NULL;
     return T;
}
     
void CreateLeftB(int x, node n, bt* T) {
     if(n->left) {
                 cout << "Greska!" << endl;
                 return;
                 }
     node novi=new element;
     n->left=novi;
     novi->label=x;
     novi->left=NULL;
     novi->right=NULL;
}
     
void CreateRightB(int x, node n, bt *T) {
     if(n->right) {
                  cout << "Greska!" << endl;
                  return;
                  }
     node novi=new element;
     n->right=novi;
     novi->label=x;
     novi->left=NULL;
     novi->right=NULL;
}
     
void DeleteB(node n, bt* T) {
     static bool jednom=false;
     if(!jednom) {
                 node parent=ParentB(n,T);
                 if(parent->left==n)
                                      parent->left=NULL;
                 else
                     parent->right=NULL;
                 jednom=true;
                 }
     if(n->left)
                DeleteB(n->left,T);
     if(n->right)
                 DeleteB(n->right,T);
     delete n;
}

bt* InitB(int x, bt* T) {
     T=new element;
     T->label=x;
     T->left=NULL;
     T->right=NULL;
     return T;
}

//main

#include <iostream>
using namespace std;

#include "bstablo_polje.h"
//#include "bstablo_pokazivac.h"

int main() {
    cout<<endl<<"Inicijaliziramo stablo s korijenom 2"<<endl;
    bt* stablo=InitB(2,stablo);
    cout<<endl<<"Korijen novog stabla: "<<LabelB(RootB(stablo),stablo)<<endl;
    
    cout<<endl<<"Stvaranje lijevog djeteta korijenu: 9"<<endl;
    CreateLeftB(9,RootB(stablo),stablo);
    cout<<endl<<"Stvaranje desnog djeteta korijenu: 7"<<endl;
    CreateRightB(7,RootB(stablo),stablo);
    
    cout<<endl<<"Lijevo dijete korijena stabla: "<< LabelB(LeftChildB(RootB(stablo),stablo),stablo)<<endl;
    cout<<endl<<"Desno dijete korijena stabla: "<< LabelB(RightChildB(RootB(stablo),stablo),stablo)<<endl;
    
    cout<<endl<<"Stvaranje lijevog djeteta 11 lijevom djetetu korijenu (cvor 9)"<<endl;
    CreateLeftB(11,LeftChildB(RootB(stablo),stablo),stablo);
    
    cout <<endl<< "Stvaranje desnog djeteta 16 lijevom djetetu korijenu (cvor 9)" << endl;
    CreateRightB(16,LeftChildB(RootB(stablo),stablo),stablo);
    
    cout <<endl<< "Stvaranje lijevog djeteta 12 desnom djetetu korijenu (cvor 7)" << endl;
    CreateLeftB(12,RightChildB(RootB(stablo),stablo),stablo);
    
    cout <<endl<< "Greska kod stvaranja lijevog djeteta 14 desnogdjeteta korijenu (cvor 7)" << endl;
    CreateLeftB(14,RightChildB(RootB(stablo),stablo),stablo);
    
    cout <<endl<< "Stvaranje desnog djeteta 14 desnom djetetu korijenu stabla (cvor 7)" << endl;
    CreateRightB(14,RightChildB(RootB(stablo),stablo),stablo);
    
    cout <<endl<< "Mijenjanje oznake cvoru 16 u 17" << endl;
    ChangeLabelB(17,RightChildB(LeftChildB(RootB(stablo),stablo),stablo),stablo);
    cout <<endl<< "Desno dijete lijevog dijeteta korijena stabla: " << LabelB(RightChildB(LeftChildB(RootB(stablo),stablo),stablo),stablo) << endl;
    
    node pom = RightChildB(RightChildB(RootB(stablo), stablo), stablo);
    cout <<endl<< "Roditelj cvora 14: " << LabelB(ParentB(pom, stablo), stablo) << endl;
    
    cout <<endl<< "Brisanje cvora 9 i njegovih potomaka" << endl;
    DeleteB(LeftChildB(RootB(stablo),stablo),stablo);
    cout <<endl<< "Stvaranje novog cvora 19 umjesto cvora 9" << endl;
    CreateLeftB(19,RootB(stablo),stablo);
    
    system ("pause");
    return 0;
}

Implementacije binarnog stabla

podataka

C++