Posted By

zoturk on 01/06/11


Tagged


Versions (?)

Zadatak 4 -SP


 / Published in: C++
 

  1. // bstablo_polje.h
  2.  
  3.  
  4. typedef int labeltype;
  5.  
  6. struct element
  7. {
  8. labeltype label;
  9. int used;
  10. };
  11.  
  12. struct bt
  13. {
  14. element elements[10000];
  15. };
  16.  
  17. typedef bt *btree;
  18. typedef int node;
  19.  
  20. node ParentB( int n, btree T)
  21. {
  22. if (n==1)
  23. {
  24. return 0;
  25. }//if
  26.  
  27. return n/2;
  28.  
  29. };
  30.  
  31. node LeftChildB(int n, btree T)
  32. {
  33. if(T->elements[n*2].used==0)
  34. {
  35. return -1;
  36. }//if
  37.  
  38.  
  39. else return n*2;
  40.  
  41. };
  42.  
  43. node RightChildB(int n,btree T)
  44. {
  45. if(T->elements[(n*2)+1].used==0) return -1;
  46.  
  47. else return n*2+1;
  48. };
  49.  
  50. node LabelB(int n, btree T)
  51. {
  52. if(T->elements[1].used == 0 || n<0) return 0;
  53. return T->elements[n].label;
  54. };
  55.  
  56. node ChangeLabelB(int x,int n,btree T)
  57. {
  58. T->elements[n].used=1;
  59. T->elements[n].label=x;
  60.  
  61. };
  62.  
  63. node RootB(btree T)
  64. {
  65.  
  66. return 1;
  67.  
  68. };
  69.  
  70. void CreateLeftB(int x,int n, btree T)
  71. {
  72. if(n*2>10000) return;
  73.  
  74. if(T->elements[n*2].used==1) return;
  75.  
  76. else
  77. {
  78. T->elements[n*2].label=x;
  79. T->elements[n*2].used=1;
  80. }//else
  81. };
  82.  
  83. void CreateRightB(int x, int n, btree T)
  84. {
  85. if(n*2+1>10000) return;
  86.  
  87. if(T->elements[n*2+1].used==1) return;
  88.  
  89. else
  90. {
  91. T->elements[n*2+1].label=x;
  92. T->elements[n*2+1].used=1;
  93. }//else
  94. };
  95.  
  96.  
  97. void DeleteB( int n, btree T)
  98. {
  99. T->elements[n].used=0;
  100.  
  101. if(LeftChildB(n,T)!=-1)
  102. {
  103. DeleteB(LeftChildB(n,T),T);
  104. }//if
  105.  
  106. if(RightChildB(n,T)!=-1)
  107. {
  108. DeleteB(RightChildB(n,T),T);
  109. }//if
  110. };
  111.  
  112. btree InitB(int n, btree T)
  113. {
  114. if(T) delete T;
  115.  
  116. T = new bt;
  117. T->elements[1].label = n;
  118. T->elements[1].used=1;
  119. T->elements[0].used=1;
  120. for(int i=2;i<10000;i++)
  121. T->elements[i].used=0;
  122.  
  123. return T;
  124. };
  125.  
  126.  
  127.  
  128. ///////////////////////////
  129. // bstablo_pokazivac.h
  130.  
  131. typedef int labeltype;
  132.  
  133. struct element
  134. {
  135. labeltype label;
  136. element *left, *right;
  137. };
  138.  
  139. typedef element *node;
  140. typedef element *btree;
  141.  
  142. node ParentB(node n, btree T)
  143. {
  144. if(n == T) return NULL;
  145.  
  146. node P = NULL;
  147.  
  148. if(T->left!=NULL)
  149. {
  150. if(T->left == n) return T;
  151.  
  152. else P = ParentB(n,T->left);
  153. }//if
  154.  
  155. if(T->right!=NULL)
  156. {
  157. if(T->right == n) return T;
  158. else P = ParentB(n,T->right);
  159. }//if
  160.  
  161. return P;
  162. };
  163.  
  164. node LeftChildB(node n, btree T)
  165. {
  166. if(n!=NULL || n -> left != NULL)
  167. return n -> left;
  168. else NULL;
  169.  
  170. };
  171.  
  172.  
  173. node RightChildB(node n, btree T)
  174. {
  175. if(n!=NULL || n -> right != NULL)
  176. return n -> right;
  177. else NULL;
  178.  
  179. };
  180.  
  181. labeltype LabelB(node n, btree T)
  182. {
  183. return n->label;
  184. };
  185.  
  186.  
  187. void ChangeLabelB(int x, node n, btree T)
  188. {
  189. if(n==NULL)return;
  190.  
  191. n->label = x;
  192.  
  193. };
  194.  
  195. node RootB(btree T)
  196. {
  197. if(T!=NULL) return T;
  198.  
  199. else return NULL;
  200. };
  201.  
  202. void CreateLeftB(int x, node n, btree T)
  203. {
  204. if(n->left!=NULL) return;
  205.  
  206. node novi = new element;
  207. n->left= novi;
  208. novi->label = x;
  209. novi->left=NULL;
  210. novi->right=NULL;
  211.  
  212. };
  213.  
  214. void CreateRightB(int x, node n, btree T)
  215. {
  216. if(n->right!=NULL) return;
  217.  
  218. node novi = new element;
  219. n->right = novi;
  220. novi->label = x;
  221. novi->left=NULL;
  222. novi->right=NULL;
  223.  
  224. };
  225.  
  226.  
  227. void DeleteB(node n, btree T)
  228. {
  229. if(n->left!=NULL) DeleteB(n->left,T);
  230.  
  231. if(n->right!=NULL) DeleteB(n->right,T);
  232.  
  233. delete n;
  234. };
  235.  
  236. btree InitB(int n, btree T)
  237. {
  238. if(T) delete T;
  239. T = new element;
  240.  
  241. T->label= n;
  242. T->right =NULL;
  243. T->left = NULL;
  244.  
  245. return T;
  246. };
  247.  
  248.  
  249.  
  250. ///////////////////////////
  251. // Main.cpp
  252.  
  253.  
  254. #include<iostream>
  255. using namespace std;
  256. #include "bstablo_polje.h"
  257. //#include "bstablo_pokazivac.h"
  258.  
  259. int main()
  260. {
  261. btree T;
  262. int izbor,unos;
  263. bool upis=false,upis2=false;
  264. do{
  265. cout<<"---------------------------------"<<endl
  266. <<"0. Iniciranje binarnog stabla <InitB>"<<endl
  267. <<"1. Dodavanje desnog i ljevog djeteta korjenu stabla <CreateLeftB, \n CreateRightB>"<<endl
  268. <<"2. Izmjena ljevog i desnog djeteta <ChangeLabelB>"<<endl
  269. <<"3. Dodavanje desnog djeteta ljevom i desnom djetetu cvora <CreateLeftB,\n CreateRightB>"<<endl
  270. <<"4. Prikaz roditelja cvora <ParentB, LabelB>"<<endl
  271. <<"5. Brisanje cvora <DeleteB>"<<endl
  272. <<"9. Kraj"<<endl
  273. <<"---------------------------------"<<endl;
  274.  
  275. cin>>izbor;
  276.  
  277. switch(izbor)
  278. {
  279. case 0:
  280. cout<<"Korjen = ";
  281. cin>>unos;
  282. T=InitB(unos,T);
  283. cout<<"\t\t\t"<<LabelB(RootB(T),T)<<endl;
  284. break;
  285.  
  286. case 1:
  287. upis=true;
  288. cout<<"n_right= ";
  289. cin>>unos;
  290. CreateRightB(unos,RootB(T),T);
  291. cout<<"n_left= ";
  292. cin>>unos;
  293. CreateLeftB(unos,RootB(T),T);
  294.  
  295. cout<<"\t\t\t"<<LabelB(RootB(T),T)<<endl
  296. <<"\t\t "<<LabelB(LeftChildB(RootB(T),T),T)<<"\t "<<LabelB(RightChildB(RootB(T),T),T)<<endl;
  297. cout<<endl;
  298. break;
  299.  
  300. case 2:
  301. if (upis==false){
  302. cout<<"Prvo koirstite migucnost 1...."<<endl;
  303. break;
  304. }
  305. cout<<"n_right= ";
  306. cin>>unos;
  307. ChangeLabelB(unos,RightChildB(RootB(T),T),T);
  308. cout<<"n_left= ";
  309. cin>>unos;
  310. ChangeLabelB(unos,LeftChildB(RootB(T),T),T);
  311.  
  312. cout<<"\t\t\t"<<LabelB(RootB(T),T)<<endl;
  313. cout<<"\t\t "<<LabelB(LeftChildB(RootB(T),T),T)<<"\t "<<LabelB(RightChildB(RootB(T),T),T)<<endl;
  314.  
  315. cout<<endl;
  316. break;
  317.  
  318. case 3:
  319. if (upis==false){
  320. cout<<"Prvo koirstite migucnost 1...."<<endl;
  321. break;
  322. }
  323.  
  324. cout<<"n_right= ";
  325. cin>>unos;
  326. CreateRightB(unos,LeftChildB(RootB(T),T),T);
  327.  
  328. cout<<"\t\t\t"<<LabelB(RootB(T),T)<<endl;
  329. cout<<"\t\t "<<LabelB(LeftChildB(RootB(T),T),T)<<"\t "<<LabelB(RightChildB(RootB(T),T),T)<<endl;
  330. cout<<"\t\t "<<LabelB(RightChildB(LeftChildB(RootB(T),T),T),T)<<endl;
  331. cout<<endl;
  332.  
  333. cout<<"n_right= ";
  334. cin>>unos;
  335. CreateRightB(unos,RightChildB(RootB(T),T),T);
  336.  
  337. cout<<"\t\t\t"<<LabelB(RootB(T),T)<<endl;
  338. cout<<"\t\t "<<LabelB(LeftChildB(RootB(T),T),T)<<"\t "<<LabelB(RightChildB(RootB(T),T),T)<<endl;
  339. cout<<"\t\t "<<LabelB(RightChildB(LeftChildB(RootB(T),T),T),T)<<"\t "<<LabelB(RightChildB(RightChildB(RootB(T),T),T),T)<<endl;
  340. cout<<endl;
  341. upis2=true;
  342. break;
  343.  
  344. case 4:
  345. cout<<"Roditelj broja "<<LabelB(LeftChildB(RootB(T),T),T)<<" je: "<<LabelB(ParentB(LeftChildB(RootB(T),T),T),T)<<endl;
  346. if(upis2==true){
  347. cout<<"Roditelj broja "<<LabelB(RightChildB(RightChildB(RootB(T),T),T),T)<<" je: "<<LabelB(ParentB(RightChildB(RightChildB(RootB(T),T),T),T),T)<<endl;
  348. }
  349. break;
  350.  
  351. case 5:
  352. DeleteB(LeftChildB(RootB(T),T),T);
  353.  
  354. cout<<"\t\t\t"<<LabelB(RootB(T),T)<<endl;
  355. cout<<"\t\t "<<"\t "<<LabelB(RightChildB(RootB(T),T),T)<<endl;
  356. cout<<"\t\t "<<"\t "<<LabelB(RightChildB(RightChildB(RootB(T),T),T),T)<<endl;
  357.  
  358. cout<<endl;
  359. break;
  360.  
  361.  
  362. }//switch
  363. }while(izbor!=9);
  364.  
  365.  
  366. system("pause");
  367. return 0;
  368. };

Report this snippet  

You need to login to post a comment.