Posted By

anton_kvesic on 01/10/11


Tagged

4 Strukture podataka zadatak


Versions (?)

zadatak 4 strukture podataka


 / Published in: C++
 

  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. typedef int labeltype;
  6. struct cvor {
  7. labeltype label;
  8. bool used;
  9. };
  10.  
  11. struct bt {
  12. cvor elementi[10000];
  13. };
  14.  
  15. typedef bt btree;
  16. typedef int node;
  17.  
  18. void InitB(labeltype x, btree *T) {
  19. for (int i = 1; i < 10000; i++) {
  20. T->elementi[i].used = false;
  21. }
  22. T->elementi[1].used = true;
  23. T->elementi[1].label = x;
  24. }
  25.  
  26. labeltype LabelB(node n, btree *T) {
  27. return T->elementi[n].label;
  28. }
  29.  
  30. void ChangeLabelB(labeltype x, node n, btree *T) {
  31. T->elementi[n].label = x;
  32. }
  33.  
  34. node RootB(btree *T) {
  35. return 1;
  36. }
  37.  
  38. node LeftChildB(node n, btree *T) {
  39. if (T->elementi[n*2].used == true)
  40. return n*2;
  41. else
  42. return 0;
  43. }
  44.  
  45. node RightChildB(node n, btree *T) {
  46. if (T->elementi[n*2+1].used == true)
  47. return n*2+1;
  48. else
  49. return 0;
  50. }
  51.  
  52. node ParentB(node n, btree *T) {
  53. return n/2;
  54. }
  55.  
  56. void CreateLeftB(labeltype x, node n, btree *T) {
  57. if (T->elementi[n*2].used == true)
  58. cout << "Taj cvor vec postoji!" << endl;
  59. else {
  60. T->elementi[n*2].used = true;
  61. T->elementi[n*2].label = x;
  62. }
  63. }
  64.  
  65. void CreateRightB(labeltype x, node n, btree *T) {
  66. if (T->elementi[n*2+1].used == true)
  67. cout << "Taj cvor vec postoji!" << endl;
  68. else {
  69. T->elementi[n*2+1].used = true;
  70. T->elementi[n*2+1].label = x;
  71. }
  72. }
  73.  
  74. void DeleteB(node n, btree *T) {
  75. T->elementi[n].used = false;
  76. if (T->elementi[n*2].used == true)
  77. DeleteB(n*2, T);
  78. if (T->elementi[n*2+1].used == true)
  79. DeleteB(n*2+1, T);
  80. }
  81.  
  82.  
  83.  
  84. #include <iostream>
  85. #include <deque>
  86.  
  87. using namespace std;
  88.  
  89. typedef int labeltype;
  90. struct cvor {
  91. labeltype label;
  92. cvor *left, *right; //
  93. };
  94.  
  95. typedef cvor *node;
  96. typedef cvor btree;
  97.  
  98. void InitB(labeltype x, btree *T) {
  99. T->label = x;
  100. T->left = T->right = NULL;
  101. }
  102.  
  103. labeltype LabelB(node n, btree *T) {
  104. return n->label;
  105. }
  106.  
  107. void ChangeLabelB(labeltype x, node n, btree *T) {
  108. n->label = x;
  109. }
  110.  
  111. node RootB(btree *T) { return T; }
  112.  
  113. node LeftChildB(node n, btree *T) {
  114. return n->left;
  115. }
  116.  
  117. node RightChildB(node n, btree *T) {
  118. return n->right;
  119. }
  120.  
  121. node ParentB(node n, btree *T) {
  122. // ako zelis parent od korijena, odmah gotovo
  123. if (n == T)
  124. return NULL;
  125. // ako ne, idemo traziti
  126. deque<node> red;
  127. red.push_back(RootB(T));
  128. node temp;
  129. // Ovdje njime simuliramo red, dodajemo nepregledane
  130. // cvorove na kraj, a s pocetka pregledavamo i vadimo
  131. while (red.size()) {
  132. temp = red[0];
  133. red.pop_front();
  134.  
  135. // je li temp roditelj nasemu n?
  136. if (temp->left == n || temp->right == n)
  137. return temp;
  138. // ako nije, gledaj dalje potomstvo...
  139. // na kraj reda dodajemo djecu temp-a da se njih pregleda
  140. if (temp->left)
  141. red.push_back(temp->left);
  142. if (temp->right)
  143. red.push_back(temp->right);
  144. }
  145.  
  146. // ako nije nadjeno (nepostojeci cvor zadan)
  147. return NULL;
  148. }
  149.  
  150. void CreateLeftB(labeltype x, node n, btree *T) {
  151. if (n->left != NULL) {
  152. cout << "LeftChild vec postoji" << endl;
  153. return;
  154. }
  155. else {
  156. node temp = new cvor;
  157. temp->label = x;
  158. temp->left = temp->right = NULL;
  159. n->left = temp;
  160. }
  161. }
  162.  
  163. void CreateRightB(labeltype x, node n, btree *T) {
  164. if (n->right != NULL) {
  165. cout << "RightChild vec postoji" << endl;
  166. return;
  167. }
  168. else {
  169. node temp = new cvor;
  170. temp->label = x;
  171. temp->left = temp->right = NULL;
  172. n->right = temp;
  173. }
  174. }
  175.  
  176. void DeleteB(node n, btree *T) {
  177. if (n->left)
  178. DeleteB(n->left, T);
  179. if (n->right)
  180. DeleteB(n->right, T);
  181.  
  182. node r = ParentB(n, T);
  183. if (r->right == n)
  184. r->right = NULL;
  185. else
  186. r->left = NULL;
  187.  
  188. delete n;
  189. }
  190.  
  191.  
  192. #include "c.h"
  193. //#include "b.h"
  194.  
  195. int main() {
  196.  
  197. cout << endl << "Testiranje b i c zadatka: binarno stablo." << endl;
  198. btree bin;
  199. cout << "*Inicijalizacija*" << endl;
  200. InitB(100, &bin);
  201. ChangeLabelB(200, RootB(&bin), &bin);
  202. cout << "Treba pisati 200: " << LabelB(RootB(&bin), &bin) << endl;
  203. cout << "*Dodavanje djece.*" << endl;
  204. CreateRightB(300, RootB(&bin), &bin);
  205. CreateLeftB(301, RootB(&bin), &bin);
  206. node bin_root_lchild = LeftChildB(RootB(&bin), &bin);
  207. node bin_root_rchild = RightChildB(RootB(&bin), &bin);
  208. CreateRightB(311, bin_root_lchild, &bin);
  209. CreateLeftB(321, bin_root_lchild, &bin);
  210. CreateRightB(310, bin_root_rchild, &bin);
  211. CreateLeftB(320, bin_root_rchild, &bin);
  212. cout << "Treba pisati 300: " << LabelB(bin_root_rchild, &bin) << endl;
  213. cout << "Treba pisati 301: " << LabelB(bin_root_lchild, &bin) << endl;
  214. cout << "*Brisanje*" << endl;
  215. cout << "Adresa lchilda korijena: " << LeftChildB(bin_root_lchild, &bin) << endl;
  216. DeleteB(bin_root_lchild, &bin);
  217. cout << "Adresa lchilda korijena (nakon brisanja): " << LeftChildB(bin_root_lchild, &bin) << endl;
  218. cout << "Ima li root sad lchild: ";
  219. if (LeftChildB(RootB(&bin), &bin)) {
  220. cout << "ima" << endl;
  221. }
  222. else {
  223. cout << "nema" << endl;
  224. }
  225. system ("pause");
  226. return 0;
  227. }

Report this snippet  

You need to login to post a comment.