Advanced Search

Implementacije binarnog stabla

/ Published in: C++
Save to your folder(s)

Expand | Embed | Plain Text

Copy this code and paste it in your HTML 
  1. //implementacija pomocu polja
  2.  
  3. #include <iostream>
  4. using namespace std;
  5.  
  6. struct element {
  7.        int label;
  8.        int used;
  9. };
  10.  
  11. struct bt {
  12.        element elements[1000];
  13. };
  14.  
  15. typedef int node;
  16.  
  17. node ParentB(node n, bt* T) {
  18.      if(n==1)
  19.              return 0;
  20.      if(n%2) n--;
  21.      return n/2;
  22. }
  23.  
  24. node LeftChildB(node n, bt* T) {
  25.      if(T->elements[n].used==0)
  26.                                return 0;
  27.      if(T->elements[2*n].used==1)
  28.                                  return 2*n;
  29.      else
  30.          return 0;
  31. }
  32.  
  33. node RightChildB(node n, bt* T) {
  34.      if(T->elements[n].used==0)
  35.                                return 0;
  36.      if(T->elements[2*n+1].used==1)
  37.                                    return 2*n+1;
  38.      else
  39.          return 0;
  40. }
  41.  
  42. int LabelB(node n, bt* T) {
  43.     return T->elements[n].label;
  44. }
  45.  
  46. void ChangeLabelB(int x, node n, bt* T) {
  47.      if(T->elements[n].used==0)
  48.                                return;
  49.      T->elements[n].label=x;
  50. }
  51.  
  52. node RootB(bt* T) {
  53.      if(T->elements[1].used==0)
  54.                                return 0;
  55.      return 1;
  56. }
  57.  
  58. void CreateLeftB(int x, node n, bt* T) {
  59.      if(T->elements[n].used==0 || T->elements[2*n].used==1) {
  60.                                cout << "Greska!" << endl;
  61.                                return;
  62.                                }
  63.      T->elements[2*n].used=1;
  64.      T->elements[2*n].label=x;
  65. }
  66.  
  67. void CreateRightB(int x, node n, bt* T) {
  68.      if(T->elements[n].used==0 || T->elements[2*n+1].used==1) {
  69.                                cout << "Pogreska!" << endl;
  70.                                return;
  71.                                }
  72.      T->elements[2*n+1].used=1;
  73.      T->elements[2*n+1].label=x;
  74. }
  75.  
  76. void DeleteB(node n, bt* T) {
  77.      T->elements[n].used=0;
  78.      if(LeftChildB(n,T))
  79.                         DeleteB(LeftChildB(n,T),T);
  80.      if(RightChildB(n,T))
  81.                          DeleteB(RightChildB(n,T),T);
  82. }
  83.  
  84. bt* InitB(int x, bt* T) {
  85.     if(T)
  86.          delete T;
  87.     T=new bt;
  88.     for(int i=0; i<1000; i++)
  89.             T->elements[i].used=0;
  90.     T->elements[1].label=x;
  91.     T->elements[1].used=1;
  92.     return T;
  93. }
  94.  
  95.  
  96. //implementacija pomocu pokazivaca
  97.  
  98. #include <iostream>
  99. using namespace std;
  100.  
  101. struct element {
  102.        int label;
  103.        element *left, *right;
  104. };
  105.  
  106. typedef element *node;
  107. typedef element bt;
  108.  
  109. node ParentB(node n, bt* T) {
  110.      if(n==T)
  111.              return NULL;
  112.      node parent=NULL;
  113.      if(T->left) {
  114.                  if(T->left==n)
  115.                                return T;
  116.                  else 
  117.                       parent=ParentB(n,T->left);
  118.                  }
  119.      if(T->right) {
  120.                   if(T->right==n)
  121.                                  return T;
  122.                   else
  123.                       parent=ParentB(n,T->right);
  124.                   }
  125.      return parent;
  126. }
  127.  
  128. node LeftChildB(node n, bt* T) {
  129.      if(!n || !n->left)
  130.            return NULL;
  131.      return n->left;
  132. }     
  133.  
  134. node RightChildB(node n, bt* T) {
  135.      if(!n || !n->right)
  136.            return NULL;
  137.      return n->right;
  138. }
  139.  
  140. int LabelB(node n, bt* T) {
  141.      return n->label;
  142. }     
  143.  
  144. void ChangeLabelB(int x, node n, bt* T) {
  145.      if(!n)
  146.            return;
  147.      n->label=x;
  148. }
  149.  
  150. node RootB(bt* T) {
  151.      if(!T)
  152.            return NULL;
  153.      return T;
  154. }
  155.  
  156. void CreateLeftB(int x, node n, bt* T) {
  157.      if(n->left) {
  158.                  cout << "Greska!" << endl;
  159.                  return;
  160.                  }
  161.      node novi=new element;
  162.      n->left=novi;
  163.      novi->label=x;
  164.      novi->left=NULL;
  165.      novi->right=NULL;
  166. }
  167.  
  168. void CreateRightB(int x, node n, bt *T) {
  169.      if(n->right) {
  170.                   cout << "Greska!" << endl;
  171.                   return;
  172.                   }
  173.      node novi=new element;
  174.      n->right=novi;
  175.      novi->label=x;
  176.      novi->left=NULL;
  177.      novi->right=NULL;
  178. }
  179.  
  180. void DeleteB(node n, bt* T) {
  181.      static bool jednom=false;
  182.      if(!jednom) {
  183.                  node parent=ParentB(n,T);
  184.                  if(parent->left==n)
  185.                                       parent->left=NULL;
  186.                  else
  187.                      parent->right=NULL;
  188.                  jednom=true;
  189.                  }
  190.      if(n->left)
  191.                 DeleteB(n->left,T);
  192.      if(n->right)
  193.                  DeleteB(n->right,T);
  194.      delete n;
  195. }
  196.  
  197. bt* InitB(int x, bt* T) {
  198.      T=new element;
  199.      T->label=x;
  200.      T->left=NULL;
  201.      T->right=NULL;
  202.      return T;
  203. }
  204.  
  205. //main
  206.  
  207. #include <iostream>
  208. using namespace std;
  209.  
  210. #include "bstablo_polje.h"
  211. //#include "bstablo_pokazivac.h"
  212.  
  213. int main() {
  214.     cout<<endl<<"Inicijaliziramo stablo s korijenom 2"<<endl;
  215.     bt* stablo=InitB(2,stablo);
  216.     cout<<endl<<"Korijen novog stabla: "<<LabelB(RootB(stablo),stablo)<<endl;
  217.  
  218.     cout<<endl<<"Stvaranje lijevog djeteta korijenu: 9"<<endl;
  219.     CreateLeftB(9,RootB(stablo),stablo);
  220.     cout<<endl<<"Stvaranje desnog djeteta korijenu: 7"<<endl;
  221.     CreateRightB(7,RootB(stablo),stablo);
  222.  
  223.     cout<<endl<<"Lijevo dijete korijena stabla: "<< LabelB(LeftChildB(RootB(stablo),stablo),stablo)<<endl;
  224.     cout<<endl<<"Desno dijete korijena stabla: "<< LabelB(RightChildB(RootB(stablo),stablo),stablo)<<endl;
  225.  
  226.     cout<<endl<<"Stvaranje lijevog djeteta 11 lijevom djetetu korijenu (cvor 9)"<<endl;
  227.     CreateLeftB(11,LeftChildB(RootB(stablo),stablo),stablo);
  228.  
  229.     cout <<endl<< "Stvaranje desnog djeteta 16 lijevom djetetu korijenu (cvor 9)" << endl;
  230.     CreateRightB(16,LeftChildB(RootB(stablo),stablo),stablo);
  231.  
  232.     cout <<endl<< "Stvaranje lijevog djeteta 12 desnom djetetu korijenu (cvor 7)" << endl;
  233.     CreateLeftB(12,RightChildB(RootB(stablo),stablo),stablo);
  234.  
  235.     cout <<endl<< "Greska kod stvaranja lijevog djeteta 14 desnogdjeteta korijenu (cvor 7)" << endl;
  236.     CreateLeftB(14,RightChildB(RootB(stablo),stablo),stablo);
  237.  
  238.     cout <<endl<< "Stvaranje desnog djeteta 14 desnom djetetu korijenu stabla (cvor 7)" << endl;
  239.     CreateRightB(14,RightChildB(RootB(stablo),stablo),stablo);
  240.  
  241.     cout <<endl<< "Mijenjanje oznake cvoru 16 u 17" << endl;
  242.     ChangeLabelB(17,RightChildB(LeftChildB(RootB(stablo),stablo),stablo),stablo);
  243.     cout <<endl<< "Desno dijete lijevog dijeteta korijena stabla: " << LabelB(RightChildB(LeftChildB(RootB(stablo),stablo),stablo),stablo) << endl;
  244.  
  245.     node pom = RightChildB(RightChildB(RootB(stablo), stablo), stablo);
  246.     cout <<endl<< "Roditelj cvora 14: " << LabelB(ParentB(pom, stablo), stablo) << endl;
  247.  
  248.     cout <<endl<< "Brisanje cvora 9 i njegovih potomaka" << endl;
  249.     DeleteB(LeftChildB(RootB(stablo),stablo),stablo);
  250.     cout <<endl<< "Stvaranje novog cvora 19 umjesto cvora 9" << endl;
  251.     CreateLeftB(19,RootB(stablo),stablo);
  252.  
  253.     system ("pause");
  254.     return 0;
  255. }

Report this snippet


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.