/ Published in: C++
Expand |
Embed | Plain Text
Copy this code and paste it in your HTML
//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; }