Posted By

ivpusic on 01/06/11


Tagged

i te binarno Implementacije opcenitog stabla demonstracije izvrsavanja


Versions (?)

Zadatak4StrukturePodataka


 / Published in: C++
 

  1. //Main()
  2.  
  3.  
  4. #include<iostream>
  5. using namespace std;
  6. //#include "pokazivac_three.h"
  7. #include "polje_three.h"
  8. #include "opcenito.h"
  9.  
  10. void opcenitoStablo(){
  11. tree *tree;
  12. int vrijednost;
  13. cout<<"Pocetna vrijednost korijena je 1"<<endl;
  14. tree=InitT(1,tree);
  15. cout<<"Unesite vrijdnost cvora (cvor 2): ";cin>>vrijednost;
  16. CreateT(vrijednost,2,tree);
  17. cout<<"Unesite jos jednu vrijednost cvora (cvor 3): ";cin>>vrijednost;
  18. CreateT(vrijednost,3,tree);
  19.  
  20. cout<<"Vrijednost treceg cvora je: "<<LabelT(2,tree)<<endl<<endl;
  21.  
  22. cout<<"Prvo dijete od cvora 2: "<<FirstChildT(2,tree)<<endl;
  23. cout<<"Roditelj od cvora 3: "<<ParentT(3,tree)<<endl;
  24.  
  25. cout<<"Unesite novu vrijednost treceg cvora: ";cin>>vrijednost;
  26. ChangeLabelT(vrijednost,2,tree);
  27.  
  28. cout<<"Nova vrijednost treceg cvora je: "<<LabelT(2,tree)<<endl<<endl;
  29.  
  30. cout<<"Brisanje cvora 2..."<<endl;
  31. DeleteT(2,tree);
  32. cout<<"Cvor 2 izbrisan..."<<endl;
  33.  
  34. cout<<"Dealokacija stabla..."<<endl<<endl;
  35.  
  36. delete tree;
  37. }//OpcenitoStablo
  38.  
  39. void binarnoStablo(){
  40. cout << "Inicijalizacija stabla" << endl;
  41. bt* stablo = InitB(1, stablo);
  42. cout << "Korijen: " << LabelB(RootB(stablo), stablo)<< endl << endl;
  43.  
  44. cout << "Kreiranje lijevog dijeteta 15 " << endl;
  45. CreateLeftB(15, RootB(stablo), stablo);
  46. cout << "Kreiranje desnog dijeta 3 " << endl << endl;
  47. CreateRightB(3, RootB(stablo), stablo);
  48.  
  49. cout << "Lijevo dijete korijena: " << LabelB(LeftChildB(RootB(stablo), stablo), stablo)<<endl;
  50. cout << "Desno dijete korijena: " << LabelB(RightChildB(RootB(stablo), stablo), stablo)<<endl<<endl;
  51.  
  52. cout << "Kreiranje lijevog djeteta 4 lijevom djetetu korijena (cvor 15)" << endl;
  53. CreateLeftB(4, LeftChildB(RootB(stablo), stablo), stablo);
  54. cout << "Kreiranje desnog djeteta 5 lijevom djetetu korijana (cvor 15)" << endl;
  55. CreateRightB(5, LeftChildB(RootB(stablo), stablo), stablo);
  56.  
  57. cout << "Kreiranje lijevog djeteta 6 desnom djetetu korijana (cvor 3)" << endl;
  58. CreateLeftB(6, RightChildB(RootB(stablo), stablo), stablo);
  59.  
  60. cout << "Kreiranje desnog djeteta 7 desnom djetetu korijana (cvor 3)" << endl;
  61. CreateRightB(7, RightChildB(RootB(stablo), stablo), stablo);
  62. cout<<endl;
  63.  
  64. cout << "Lijevo dijete desnog dijeteta korijena: ";
  65. cout << LabelB(LeftChildB(RightChildB(RootB(stablo), stablo), stablo), stablo) << endl << endl;
  66.  
  67. cout << "Mijenjanje cvora 6 u 16: " << endl << endl;
  68. ChangeLabelB(16, LeftChildB(RightChildB(RootB(stablo), stablo), stablo), stablo);
  69. cout << "Lijevo dijete desnog dijeteta korijena: ";
  70. cout << LabelB(LeftChildB(RightChildB(RootB(stablo), stablo), stablo), stablo) << endl << endl;
  71.  
  72. cvor pom = RightChildB(RightChildB(RootB(stablo), stablo), stablo);
  73. cout << "Roditelj cvora 7 je: " << LabelB(ParentB(pom, stablo), stablo) << endl << endl;
  74.  
  75. cout << "Brisanje cvora 3 i svih njegovih potomaka..." << endl;
  76. DeleteB(RightChildB(RootB(stablo), stablo), stablo);
  77. cout<<endl;
  78.  
  79. }//binarnoStablo
  80.  
  81.  
  82. int main() {
  83. int izbor;
  84. do{
  85. cout<<"0. Izlaz iz programa"<<endl;
  86. cout<<"1. Binarno stablo"<<endl;
  87. cout<<"2. Opcenito stablo"<<endl;
  88.  
  89. cout<<"Vas izbor je: ";
  90.  
  91. cin >> izbor;
  92. cout<<endl;
  93. if(izbor == 1) binarnoStablo();
  94. if(izbor == 2) opcenitoStablo();
  95. }while(izbor != 0);
  96.  
  97. system("pause");
  98. return 0;
  99. }
  100.  
  101.  
  102. //Implementacija opcenitog stabla
  103.  
  104.  
  105. struct Cvor
  106. {
  107. int Label;
  108. int PrvoDijete;
  109. int SljedeciBrat;
  110. };//struct
  111.  
  112. struct tree
  113. {
  114. Cvor element[1000];
  115. int first;
  116. };//struct1
  117.  
  118. tree *InitT(int x,tree *stablo)//inicijalizacija
  119. {
  120. delete [] stablo->element;
  121. stablo=new tree;
  122. stablo->first=0;
  123. stablo->element[x].Label=x;
  124. stablo->first++;
  125. }//InitT
  126.  
  127. int FirstChildT(int x, tree *stablo)
  128. {
  129. if(x<0) return -1;
  130. else
  131. {
  132. if(x>=0 && ((x+1)!=0)) return stablo->element[x].PrvoDijete;
  133. else return -1;
  134. }
  135. }//FirstCildT
  136.  
  137. int NextSiblingT(int x, tree *stablo)
  138. {
  139. if(x<0) return -1;
  140. else
  141. {
  142. if(stablo->element[x].SljedeciBrat!=-1)return stablo->element[x].SljedeciBrat;
  143. else return -1;
  144. }
  145. }//NextSiblingT
  146.  
  147. int ParentT(int x, tree *stablo)
  148. {
  149. if(x>0) return x-1;
  150. else
  151. {
  152. if(x==0) return -1;
  153. else cout<<"Cvor ne postoji"<<endl;
  154. }
  155. }//ParentT
  156.  
  157. int LabelT(int x, tree *stablo)//vratiVrijednost
  158. {
  159. if(x<0) cout<<"Pogreska"<<endl;
  160. else
  161. {
  162. return stablo->element[x].Label;
  163. }
  164. }//LabelT
  165.  
  166. int ChangeLabelT(int x, int y, tree *stablo)
  167. {
  168. if(x<0) return -1;
  169. else stablo->element[y].Label=x;
  170. }//changeLabel
  171.  
  172. int RootT(tree *stablo)
  173. {
  174. return stablo->element[0].Label;
  175. }//RootT
  176.  
  177. int CreateT(int x, int y, tree *stablo)//dodavanje
  178. {
  179. stablo->element[stablo->first].Label=x;
  180. stablo->element[stablo->first].PrvoDijete=y;
  181. stablo->first++;
  182. }//CreateT
  183.  
  184. int DeleteT(int x, tree *stablo)//brisanje
  185. {
  186. if(x<0) return -1;
  187. else
  188. {
  189. if(stablo->element[x].PrvoDijete>0) DeleteT(stablo->element[x].PrvoDijete,stablo);
  190. else
  191. {
  192. stablo->element[x].Label=-1;
  193. stablo->first--;
  194. }
  195. }
  196. }//DeleteT
  197.  
  198. //Implementacija binarnog (polje)
  199.  
  200.  
  201. struct element {
  202. int label;
  203. int koristeno;
  204. };
  205.  
  206. struct bt {
  207. element elements[10000];
  208. };
  209.  
  210. typedef int cvor;
  211.  
  212. bt* InitB(int x, bt* T) {//incijalizacija
  213. if(T) delete T;
  214. T = new bt;
  215. for(int i = 0; i < 10000; i++)
  216. T->elements[i].koristeno = 0;
  217. T->elements[1].label = x;
  218. T->elements[1].koristeno = 1;
  219. return T;
  220. }//initB
  221.  
  222. void CreateLeftB(int x, cvor n, bt* T) {//kreiraj lijevo
  223. if(T->elements[n].koristeno == 0 || T->elements[2*n].koristeno == 1) {
  224. cout << "Greska" << endl << endl;
  225. return;
  226. }
  227. T->elements[2*n].koristeno = 1;
  228. T->elements[2*n].label = x;
  229. }//CreateLeftB
  230.  
  231. void CreateRightB(int x, cvor n, bt* T) {//kreiraj desno
  232. if(T->elements[n].koristeno == 0 || T->elements[2*n+1].koristeno == 1)
  233. {
  234. cout << "Greska" << endl << endl;
  235. return;
  236. }
  237. T->elements[2*n+1].koristeno = 1;
  238. T->elements[2*n+1].label = x;
  239. }//CreateRightB
  240.  
  241. cvor LeftChildB(cvor n, bt* T) {//lijevo dijete
  242. if(T->elements[n].koristeno == 0)
  243. return 0;
  244. if(T->elements[2*n].koristeno == 1)
  245. return 2*n;
  246. else return 0;
  247. }//LeftCildB
  248.  
  249. cvor RightChildB(cvor n, bt* T) {//desno dijete
  250. if(T->elements[n].koristeno == 0) return 0;
  251. if(T->elements[2*n+1].koristeno == 1) return 2*n+1;
  252. else return 0;
  253. }//RightCildB
  254.  
  255. cvor ParentB(cvor n, bt* T) {
  256. if(n == 1) return 0;
  257. if(n%2) n--;
  258. return n/2;
  259. }//ParentB
  260.  
  261. int LabelB(cvor n, bt* T) {
  262. return T->elements[n].label;
  263. }//LabelB
  264.  
  265. void ChangeLabelB(int x, cvor n, bt* T) {//zamjena
  266. if(T->elements[n].koristeno == 0) return;
  267. T->elements[n].label = x;
  268. }//ChangeLabelB
  269.  
  270. cvor RootB(bt* T) {
  271. if(T->elements[1].koristeno == 0) return 0;
  272. return 1;
  273. }//RootB
  274.  
  275. void DeleteB(cvor n, bt* T) {
  276. T->elements[n].koristeno = 0;
  277. if (LeftChildB(n, T)) DeleteB(LeftChildB(n, T), T);
  278. if (RightChildB(n, T)) DeleteB(RightChildB(n, T), T);
  279. }//DeleteB
  280.  
  281.  
  282. //Implementacija binarnog (pokazivac)
  283.  
  284.  
  285. struct element {
  286. int label;
  287. element *left,*right;
  288. };
  289.  
  290. typedef element *cvor;
  291. typedef element bt;
  292.  
  293. bt* InitB(int x, bt* T) {//inicijalizacija
  294. T = new element;
  295. T->label = x;
  296. T->left = NULL;
  297. T->right = NULL;
  298. return T;
  299. }//initB
  300.  
  301. void CreateLeftB(int x, cvor n, bt* T) {//novi lijevi
  302. if(n->left) {
  303. cout << "Greska" << endl << endl;
  304. return;
  305. }
  306. cvor novi = new element;
  307. n->left = novi;
  308. novi->label = x;
  309. novi->left = NULL;
  310. novi->right = NULL;
  311. }//CreateLeftB
  312.  
  313. void CreateRightB(int x, cvor n, bt* T) {//novi desni
  314. if(n->right) {
  315. cout << "Greska" << endl << endl;
  316. return;
  317. }
  318. cvor novi = new element;
  319. n->right = novi;
  320. novi->label = x;
  321. novi->left = NULL;
  322. novi->right = NULL;
  323. }//createRightB
  324.  
  325. cvor ParentB(cvor n, bt* T) {
  326. if (n == T) return NULL;
  327. cvor roditelj = NULL;
  328. if (T->left) {
  329. if (T->left == n) return T;
  330. else roditelj = ParentB(n, T->left);
  331. }
  332. if(T->right) {
  333. if (T->right == n) return T;
  334. else roditelj = ParentB(n, T->right);
  335. }
  336. return roditelj;
  337. }//parentB
  338.  
  339. int LabelB(cvor n, bt* T) {//vrati oznaku
  340. return n->label;
  341. }//labelB
  342.  
  343. void ChangeLabelB(int x, cvor n, bt* T) {
  344. if(!n) return;
  345. n->label = x;
  346. }//changeLabelB
  347.  
  348. cvor LeftChildB(cvor n, bt* T) {//lijevo dijete
  349. if(!n || !n->left) return NULL;
  350. return n->left;
  351. }//leftCildB
  352.  
  353. cvor RightChildB(cvor n, bt* T) {//desno dijete
  354. if(!n || !n->right) return NULL;
  355. return n->right;
  356. }//rightCildB
  357.  
  358. cvor RootB(bt* T) {
  359. if(!T) return NULL;
  360. return T;
  361. }//rootB
  362.  
  363. void DeleteB(cvor n, bt* T) {
  364. static bool jednom = false;
  365. if(!jednom) {
  366. cvor roditelj = ParentB(n, T);
  367. if(roditelj->left == n) roditelj->left = NULL;
  368. else roditelj->right = NULL;
  369. jednom = true;
  370. }
  371.  
  372. if(n->left) DeleteB(n->left, T);
  373. if(n->right) DeleteB(n->right, T);
  374. delete n;
  375. }//deleteB

Report this snippet  

You need to login to post a comment.