# Posted By

anspevec on 01/06/11

# Statistics

Viewed 366 times
Favorited by 0 user(s)

# Implementacije binarnog stabla

/ Published in: C++
`//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;}`