Posted By

anspevec on 01/06/11


Tagged

Strukture podataka binarno stablo


Versions (?)

Implementacije binarnog stabla


 / Published in: C++
 

  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  

You need to login to post a comment.