Posted By

thekmetko on 01/06/11


Tagged

stablo


Versions (?)

Zad 4 Bstablo


 / Published in: C++
 

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

Report this snippet  

You need to login to post a comment.