implementacija binarnog stabla pomocu B.polja i C.pokazivaca


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



Copy this code and paste it in your HTML
  1. #include "c_zadatak.h"
  2. //#include "b_zadatak.h"
  3. #include <iostream>
  4.  
  5. using namespace std;
  6.  
  7.  
  8. int main(void) {
  9. btree T;
  10. cout << "Test 1, init" << endl;
  11. InitB(1, &T);
  12. cout << "Test gotov " << endl;
  13.  
  14. cout << "Test 2, init, label, root (ispis: 1)" << endl;
  15. cout << LabelB(RootB(&T), &T) << endl;
  16.  
  17. cout << "Test gotov " << endl;
  18.  
  19. cout << "Test 3, create left, create right (ispis: 1, 1, 0)" << endl;
  20. cout << CreateLeftB(42, RootB(&T), &T) << endl;
  21. cout << CreateRightB(43, RootB(&T), &T) << endl;
  22.  
  23.  
  24. cout << CreateLeftB(42, RootB(&T), &T) << endl;
  25. cout << "Test gotov " << endl;
  26. cout << "Test 4, delete" << endl;
  27. DeleteB(LeftChildB(RootB(&T), &T), &T);
  28. cout << "Test gotov " << endl;
  29.  
  30. cout << "Test 5, delete (ispisuje 1)" << endl;
  31. cout << CreateLeftB(7, RootB(&T), &T) << endl;
  32. cout << "Test gotov " << endl;
  33.  
  34. cout << "Test 6, parent (ispisuje 1)" << endl;
  35. cout << LabelB(ParentB(RightChildB(RootB(&T), &T), &T), &T) << endl;
  36. cout << "Test gotov " << endl;
  37.  
  38. cout << "Test 7, change label (ispisuje 666)" << endl;
  39. ChangeLabelB(666, RootB(&T), &T);
  40. cout << LabelB(RootB(&T), &T) << endl;
  41. cout << "Test gotov " << endl;
  42. return 0;
  43. }
  44.  
  45.  
  46. //Biblioteka B.polja ///
  47.  
  48. struct element {
  49. int label;
  50. int used;
  51. };
  52.  
  53. struct bt {
  54. element elements[10000];
  55. };
  56.  
  57. typedef bt btree;
  58. typedef int node;
  59.  
  60.  
  61.  
  62. node ParentB(node n, btree *T) {
  63. return n/2;
  64. }
  65.  
  66. node RootB(btree *T) {
  67. return 1;
  68. }
  69.  
  70. void InitB(int x, btree *T) {
  71. T->elements[1].used = 1;
  72. T->elements[1].label = x;
  73. for (int i = 2; i < 10000; i++) {
  74. T->elements[i].used = 0;
  75. }
  76. }
  77.  
  78. node LeftChildB(node n, btree *T) {
  79. if (T->elements[n*2].used == 1)
  80. return n*2;
  81. else
  82. return 0;
  83. }
  84.  
  85. node RightChildB(node n, btree *T) {
  86. if (T->elements[n*2 +1].used == 1)
  87. return n*2 +1;
  88. else
  89. return 0;
  90. }
  91.  
  92. int LabelB(node n, btree *T) {
  93. return T->elements[n].label;
  94. }
  95.  
  96. void ChangeLabelB(int x, node n, btree *T) {
  97. T->elements[n].label = x;
  98. }
  99.  
  100. void DeleteB(node n, btree *T) {
  101. if (LeftChildB(n, T)) {
  102. DeleteB(LeftChildB(n, T), T);
  103. }
  104. if (RightChildB(n, T)) {
  105. DeleteB(RightChildB(n, T), T);
  106. }
  107. T->elements[n].used = 0;
  108. }
  109.  
  110. bool CreateLeftB(int x, node n, btree *T) {
  111. if (LeftChildB(n, T) != 0) {
  112. return false;
  113. }
  114. else {
  115. T->elements[n*2].used = 1;
  116. T->elements[2*n].label = x;
  117. return true;
  118. }
  119. }
  120.  
  121. bool CreateRightB(int x, node n, btree *T) {
  122. if (RightChildB(n, T) != 0) {
  123. return false;
  124. }
  125. else {
  126. T->elements[n*2 +1].used = 1;
  127. T->elements[2*n +1].label = x;
  128. return true;
  129. }
  130. }
  131.  
  132.  
  133.  
  134. Biblioteka C.pokazivaca
  135.  
  136.  
  137. #include <cstdlib>
  138.  
  139. struct element {
  140. int label;
  141. element *left,*right;
  142. };
  143.  
  144. typedef element *node;
  145. typedef element btree;
  146.  
  147.  
  148.  
  149.  
  150. node RootB(btree *T) {
  151. return T;
  152. }
  153.  
  154. void InitB(int x, btree *T) {
  155. T->label = x;
  156. T->left = NULL;
  157. T->right = NULL;
  158. }
  159.  
  160. node LeftChildB(node n, btree *T) {
  161. return (n->left);
  162. }
  163.  
  164. node RightChildB(node n, btree *T) {
  165. return (n->right);
  166. }
  167.  
  168. node rekurzivna(node cvor, node trazeni, btree *T) {
  169. if (cvor->left == trazeni || cvor->right == trazeni) {
  170. return cvor;
  171. }
  172. node tmp;
  173. tmp = rekurzivna(cvor->left, trazeni, T);
  174. if (tmp != NULL) return tmp;
  175. tmp = rekurzivna(cvor->right, trazeni, T);
  176. if (tmp != NULL) return tmp;
  177.  
  178. return NULL;
  179. }
  180.  
  181. node ParentB(node n, btree *T) {
  182. return rekurzivna(RootB(T), n, T);
  183. }
  184.  
  185. int LabelB(node n, btree *T) {
  186. return (n->label);
  187. }
  188.  
  189. void ChangeLabelB(int x, node n, btree *T) {
  190. n->label = x;
  191. }
  192.  
  193. void DeleteB(node n, btree *T) {
  194. if (n->left != NULL) {
  195. DeleteB(n->left, T);
  196. }
  197. if (n->right != NULL) {
  198. DeleteB(n->right, T);
  199. }
  200.  
  201. node Parent = ParentB(n, T);
  202. if (Parent->left == n) {
  203. Parent->left = NULL;
  204. }
  205. else {
  206. Parent->right = NULL;
  207. }
  208.  
  209. delete n;
  210. }
  211.  
  212. bool CreateLeftB(int x, node n, btree *T) {
  213. if (n->left == NULL) {
  214. n->left = new element;
  215. n->left->left = NULL;
  216. n->left->right = NULL;
  217. n->left->label = x;
  218. return 1;
  219. }
  220. return 0;
  221. }
  222.  
  223. bool CreateRightB(int x, node n, btree *T) {
  224. if (n->right == NULL) {
  225. n->right = new element;
  226. n->right->left = NULL;
  227. n->right->right = NULL;
  228. n->right->label = x;
  229. return 1;
  230. }
  231. return 0;
  232. }

Report this snippet


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.