Posted By

zeko868 on 01/20/15


Tagged

- dijete sljedei stablobinarnoprvo bratpretraivanjehrpaophoenje


Versions (?)

main.cpp


 / Published in: C++
 

Rješenje programskog problema za 4. zadaću iz kolegija Strukture podataka (FOI:IPS)

  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <iomanip>
  4. #include <ctime>
  5. #include "pdsb_polje.h"
  6. #include "bs_polje.h"
  7. #include "bs_pokazivac.h"
  8. using namespace std;
  9.  
  10. tbinarno stablo=NULL;
  11. tbinarno stablotr=NULL;
  12. tbinarno hrpa=NULL;
  13. int N;
  14. int *brojevi=NULL;
  15. int *sortirano_polje=NULL;
  16.  
  17. void tockaA () {
  18. cout<<"1. Ispuni stablo po primjeru iz laboratorijskih vjezbi"<<endl;
  19. cout<<"2. Ispuni stablo prethodno izgeneriranim brojevima"<<endl;
  20. cout<<"3. Generiraj niz pseudoslucajnih brojeva te sa njima ispuni stablo"<<endl;
  21. cout<<"4. Rucni unos brojeva u stablo"<<endl;
  22. cout<<"5. Brisanje odredjenog elementa stabla"<<endl;
  23. cout<<"6. Brisanje svih elemenata stabla"<<endl;
  24. cout<<"7. Promjena oznake odredjenog elementa stabla"<<endl;
  25. cout<<"8. Ispis roditelja odredjenog elementa stabla"<<endl;
  26. cout<<"Vas izbor: ";
  27. short izbor;
  28. cin>>izbor;
  29. switch (izbor) {
  30. case 1:
  31. short izbor2;
  32. cout<<"\t1. Primjer koristen kod objasnjenja ophodjenja"<<endl;
  33. cout<<"\t2. Primjer koristen kod prikaza stabla PDSB"<<endl;
  34. cout<<"\tVas izbor: ";
  35. cin>>izbor2;
  36. switch (izbor2) {
  37. case 1:
  38. InitT(1,stablo1);
  39. CreateT(2,1,stablo1);
  40. CreateT(3,1,stablo1);
  41. CreateT(4,1,stablo1);
  42. CreateT(5,3,stablo1);
  43. CreateT(6,3,stablo1);
  44. CreateT(7,4,stablo1);
  45. CreateT(8,5,stablo1);
  46. CreateT(9,5,stablo1);
  47. CreateT(10,6,stablo1);
  48. break;
  49. case 2:
  50. InitT(9,stablo1);
  51. CreateT(4,9,stablo1);
  52. CreateT(10,9,stablo1);
  53. CreateT(2,4,stablo1);
  54. CreateT(1,10,stablo1);
  55. CreateT(0,2,stablo1);
  56. CreateT(6,2,stablo1);
  57. CreateT(3,2,stablo1);
  58. }
  59. break;
  60. case 3:
  61. cout<<"Unesite kolicinu brojeva koju zelite izgenerirati i staviti u stablo: ";
  62. cin>>N;
  63. brojevi=new int [N];
  64. for (int i=0;i<N;i++)
  65. brojevi[i]=rand()%10000;
  66. case 2:
  67. if (brojevi==NULL)
  68. cout<<"Polje brojeva do sada jos nije generirano!"<<endl;
  69.  
  70. else
  71. for (int i=0;i<N;i++) {
  72. if (RootT(stablo1)==-1) {
  73. cout<<"Alociranje korijena stabla s vrijednoscu "<<brojevi[0]<<endl;
  74. InitT(brojevi[0],stablo1);
  75. }
  76. else {
  77. int roditelj=brojevi[rand()%i];
  78. cout<<"Dodavanje cvora sa vrijednoscu "<<brojevi[i]<<" roditelju "<<roditelj<<endl;
  79. CreateT(brojevi[i],roditelj,stablo1);
  80. }
  81. }
  82. break;
  83. case 4:
  84. char jos;
  85. do {
  86. short vrijednost;
  87. if (RootT(stablo1)==-1) {
  88. cout<<"Korijen nije alociran! Unesite vrijednost korijena: ";
  89. cin>>vrijednost;
  90. InitT(vrijednost,stablo1);
  91. }
  92. else {
  93. cout<<"Unesite vrijednost roditelja kojem zelite dodati dijete: ";
  94. short roditelj;
  95. cin>>roditelj;
  96. cout<<"Unesite vrijednost toga djeteta: ";
  97. cin>>vrijednost;
  98. CreateT(vrijednost,roditelj,stablo1);
  99. }
  100. cout<<"Da li zelite unijeti jos koji element? (d/n): ";
  101. cin.ignore();
  102. cin.get(jos);
  103. } while (jos=='d');
  104. break;
  105. case 5:
  106. cout<<"Unesite vrijednost cvora kojeg zelite izbrisati zajedno sa svom njegovom djecom: ";
  107. int vrij;
  108. cin>>vrij;
  109. DeleteT(vrij,stablo1);
  110. break;
  111. case 6:
  112. DeleteT(RootT(stablo1),stablo1);
  113. cout<<"Stablo uspjesno dealocirano!"<<endl;
  114. break;
  115. case 7:
  116. cout<<"Unesite vrijednost cvora kojem zelite promijeniti oznaku: ";
  117. int cvor;
  118. cin>>cvor;
  119. cout<<"Unesite novu oznaku cvora (maksimalno 3 znaka!): ";
  120. char oznaka[4];
  121. cin.ignore();
  122. cin.getline(oznaka,4);
  123. ChangeLabelT(oznaka,cvor,stablo1);
  124. break;
  125. case 8:
  126. cout<<"Unesite vrijednost cvora od kojeg Vas zanima roditelj: ";
  127. int vrijednost;
  128. cin>>vrijednost;
  129. if (ParentT(vrijednost,stablo1)==-1)
  130. if (vrijednost==RootT(stablo1))
  131. cout<<"Korijen stabla nema svoga roditelja!"<<endl;
  132. else
  133. cout<<"Element sa navedenom vrijednoscu se ne nalazi u stablu!"<<endl;
  134. else
  135. cout<<"Roditelj elementa sa navedenom vrijednoscu je cvor sa vrijednoscu "<<ParentT(vrijednost,stablo1)<<", odnosno sa oznakom "<<LabelT(ParentT(vrijednost,stablo1),stablo1)<<endl;
  136. }
  137. }
  138. void ophodjenje (int cvor,tstablo &stablo,short izbor) {
  139. switch (izbor) {
  140. case 1:
  141. cout<<LabelT(cvor,stablo)<<" ";
  142. if (FirstChildT(cvor,stablo)!=-1)
  143. ophodjenje (FirstChildT(cvor,stablo),stablo,izbor);
  144. if (NextSiblingT(cvor,stablo)!=-1)
  145. ophodjenje (NextSiblingT(cvor,stablo),stablo,izbor);
  146. break;
  147. case 2:
  148. if (FirstChildT(cvor,stablo)!=-1)
  149. ophodjenje(FirstChildT(cvor,stablo),stablo,izbor);
  150. cout<<LabelT(cvor,stablo)<<" ";
  151. if (FirstChildT(cvor,stablo)!=-1){
  152. cvor=FirstChildT(cvor,stablo);
  153. while (NextSiblingT(cvor,stablo)!=-1){
  154. cvor=NextSiblingT(cvor,stablo);
  155. ophodjenje(cvor,stablo,izbor);
  156. }
  157. }
  158. break;
  159. case 3:
  160. if(FirstChildT(cvor,stablo)!=-1)
  161. ophodjenje(FirstChildT(cvor,stablo),stablo,izbor);
  162. int pomocni=cvor;
  163. if(FirstChildT(pomocni,stablo)!=-1){
  164. pomocni=FirstChildT(pomocni,stablo);
  165. while(NextSiblingT(pomocni,stablo)!=-1){
  166. pomocni=NextSiblingT(pomocni,stablo);
  167. ophodjenje(pomocni,stablo,izbor);
  168. }
  169. }
  170. cout<<LabelT(cvor,stablo)<<" ";
  171. };
  172. }
  173. void tockaB () {
  174. if (RootT(stablo1)==-1) {
  175. cout<<"Binarno stablo nije alocirano! Unesite prvo elemente.."<<endl;
  176. return;
  177. }
  178. cout<<"Ispis clanova stabla ophodjenjem: "<<endl;
  179. cout<<"\t1. -preorder"<<endl;
  180. cout<<"\t2. -inorder"<<endl;
  181. cout<<"\t3. -postorder"<<endl;
  182. cout<<"\tVas izbor: ";
  183. short izbor;
  184. cin>>izbor;
  185. cout<<setw(5)<<"Cont"<<setw(5)<<"Lab"<<setw(5)<<"Chil"<<setw(5)<<"Sibl"<<endl;
  186. cout<<setw(5)<<"----"<<setw(5)<<"---"<<setw(5)<<"----"<<setw(5)<<"----"<<endl;
  187. int prazan=-1;
  188. for (int i=0;i<10000;i++)
  189. if (memcmp(&prazan,&stablo1.element[i].oznaka,sizeof(int))!=0)
  190. cout<<setw(5)<<i<<setw(5)<<LabelT(i,stablo1)<<setw(5)<<FirstChildT(i,stablo1)<<setw(5)<<NextSiblingT(i,stablo1)<<endl;
  191. ophodjenje (RootT(stablo1),stablo1,izbor);
  192. cout<<endl;
  193. }
  194. void tockaCD () {
  195. cout<<"1. Ispuni binarno stablo po primjeru iz laboratorijskih vjezbi"<<endl;
  196. cout<<"2. Ispuni binarno stablo prethodno izgeneriranim brojevima"<<endl;
  197. cout<<"3. Generiraj niz pseudoslucajnih brojeva te sa njima ispuni binarno stablo"<<endl;
  198. cout<<"4. Rucni unos brojeva u binarno stablo"<<endl;
  199. cout<<"5. Brisanje odredjenog elementa binarnog stabla"<<endl;
  200. cout<<"6. Brisanje svih elemenata binarnog stabla"<<endl;
  201. cout<<"7. Promjena oznake odredjenog elementa binarnog stabla"<<endl;
  202. cout<<"Vas izbor: ";
  203. short izbor;
  204. cin>>izbor;
  205. switch (izbor) {
  206. case 1:
  207. InitB(1,stablo);
  208. CreateLeftB(2,RootB(stablo),stablo);
  209. CreateRightB(3,RootB(stablo),stablo);
  210. CreateRightB(4,LeftChildB(RootB(stablo),stablo),stablo);
  211. CreateLeftB(5,RightChildB(RootB(stablo),stablo),stablo);
  212. CreateLeftB(6,RightChildB(LeftChildB(RootB(stablo),stablo),stablo),stablo);
  213. CreateRightB(7,RightChildB(LeftChildB(RootB(stablo),stablo),stablo),stablo);
  214. CreateRightB(8,LeftChildB(RightChildB(RootB(stablo),stablo),stablo),stablo);
  215. cout<<"Binarno stablo je kreirano!"<<endl;
  216. break;
  217. case 3:
  218. cout<<"Unesite kolicinu brojeva koju zelite izgenerirati i staviti u stablo: ";
  219. cin>>N;
  220. brojevi=new int [N];
  221. for (int i=0;i<N;i++)
  222. brojevi[i]=rand()%10000;
  223. case 2:
  224. if (brojevi==NULL)
  225. cout<<"Polje brojeva do sada jos nije generirano!"<<endl;
  226. else
  227. for (int i=0;i<N;i++)
  228. if (stablo==NULL) {
  229. cout<<"Alociranje korijena stabla s vrijednoscu "<<brojevi[0]<<endl;
  230. InitB(brojevi[0],stablo);
  231. }
  232. else {
  233. tcvor cvor=RootB(stablo);
  234. bool end=false;
  235. do {
  236. if (rand()%2==0)
  237. if (ExistsLeftChild(cvor,stablo)==true)
  238. cvor=LeftChildB(cvor,stablo);
  239. else {
  240. CreateLeftB(brojevi[i],cvor,stablo);
  241. end=true;
  242. }
  243. else
  244. if (ExistsRightChild(cvor,stablo)==true)
  245. cvor=RightChildB(cvor,stablo);
  246. else {
  247. CreateRightB(brojevi[i],cvor,stablo);
  248. end=true;
  249. }
  250. } while (end==false);
  251. cout<<"Dodavanje cvora sa vrijednoscu "<<brojevi[i]<<" roditelju sa oznakom "<<LabelB(cvor,stablo)<<endl;
  252. }
  253. break;
  254. case 4:
  255. char jos;
  256. do {
  257. short vrijednost;
  258. if (stablo==NULL) {
  259. cout<<"Korijen nije alociran! Unesite vrijednost korijena: ";
  260. cin>>vrijednost;
  261. InitB(vrijednost,stablo);
  262. }
  263. else {
  264. tcvor cvor=RootB(stablo);
  265. bool dodan=false;
  266. do {
  267. cout<<"Zelite li dodati element lijevo ("<<(ExistsLeftChild(cvor,stablo)==false?-1:LabelB(LeftChildB(cvor,stablo),stablo))<<") ili desno ("<<(ExistsRightChild(cvor,stablo)==false?-1:LabelB(RightChildB(cvor,stablo),stablo))<<") (l/d): ";
  268. char ld;
  269. cin.ignore();
  270. cin.get(ld);
  271. if (ld=='l')
  272. if (ExistsLeftChild(cvor,stablo)==true)
  273. cvor=LeftChildB(cvor,stablo);
  274. else {
  275. cout<<"Unesite vrijednost djeteta: ";
  276. cin>>vrijednost;
  277. CreateLeftB(vrijednost,cvor,stablo);
  278. dodan=true;
  279. }
  280. else if (ld=='d')
  281. if (ExistsRightChild(cvor,stablo)==true)
  282. cvor=RightChildB(cvor,stablo);
  283. else {
  284. cout<<"Unesite vrijednost djeteta: ";
  285. cin>>vrijednost;
  286. CreateRightB(vrijednost,cvor,stablo);
  287. dodan=true;
  288. }
  289. } while (dodan==false);
  290. }
  291. cout<<"Da li zelite unijeti jos koji element? (d/n): ";
  292. cin.ignore();
  293. cin.get(jos);
  294. } while (jos=='d');
  295. break;
  296. case 5:
  297. if (stablo==NULL)
  298. cout<<"Korijen nije alociran! Nema se sto izbrisati..";
  299. else {
  300. tcvor cvor=RootB(stablo);
  301. bool izbrisan=false;
  302. do {
  303. cout<<"Zelite li pomaknuti kursor na element lijevo ("<<(ExistsLeftChild(cvor,stablo)==false?-1:LabelB(LeftChildB(cvor,stablo),stablo))<<"), desno ("<<(ExistsRightChild(cvor,stablo)==false?-1:LabelB(RightChildB(cvor,stablo),stablo))<<"), natrag na roditelja ("<<(ParentB(cvor,stablo)<=0?-1:LabelB(ParentB(cvor,stablo),stablo))<<") ili izbrisati trenutni ("<<LabelB(cvor,stablo)<<") (l/d/r/b): ";
  304. char ldrb;
  305. cin.ignore();
  306. cin.get(ldrb);
  307. if (ldrb=='l')
  308. if (ExistsLeftChild(cvor,stablo)==true)
  309. cvor=LeftChildB(cvor,stablo);
  310. else
  311. cerr<<"Lijevo dijete ne postoji, te bi pomak ovim putem uzrokovao iskakanje kursora iz stabla!"<<endl;
  312. else if (ldrb=='d')
  313. if (ExistsRightChild(cvor,stablo)==true)
  314. cvor=RightChildB(cvor,stablo);
  315. else
  316. cerr<<"Desno dijete ne postoji, te bi pomak ovim putem uzrokovao iskakanje kursora iz stabla!"<<endl;
  317. else if (ldrb=='r') {
  318. if (ParentB(cvor,stablo)<=0)
  319. cerr<<"Korijen nema svoga roditelja! Pozicija kursora ostaje nepromijenjena.."<<endl;
  320. else
  321. cvor=ParentB(cvor,stablo);
  322. }
  323. else if (ldrb=='b') {
  324. bool dealociraj=false;
  325. if (cvor==RootB(stablo))
  326. dealociraj=true;
  327. DeleteB(cvor,stablo);
  328. if (dealociraj==true)
  329. stablo=NULL;
  330. izbrisan=true;
  331. }
  332. } while (izbrisan==false);
  333. }
  334. break;
  335. case 6:
  336. if (stablo==NULL)
  337. cout<<"Korijen stabla niti nije alociran, pa se ni nema sto izbrisati!"<<endl;
  338. else {
  339. DeleteB(RootB(stablo),stablo);
  340. stablo=NULL;
  341. }
  342. break;
  343. case 7:
  344. if (stablo==NULL)
  345. cout<<"Korijen nije alociran! Nema elementa kojem bi se promijenila oznaka (vrijednost)..";
  346. else {
  347. tcvor cvor=RootB(stablo);
  348. bool promijenjeno=false;
  349. do {
  350. cout<<"Zelite li pomaknuti kursor na element lijevo ("<<(ExistsLeftChild(cvor,stablo)==false?-1:LabelB(LeftChildB(cvor,stablo),stablo))<<"), desno ("<<(ExistsRightChild(cvor,stablo)==false?-1:LabelB(RightChildB(cvor,stablo),stablo))<<"), natrag na roditelja ("<<(ParentB(cvor,stablo)<=0?-1:LabelB(ParentB(cvor,stablo),stablo))<<") ili promijeniti oznaku trenutnome ("<<LabelB(cvor,stablo)<<") (l/d/r/p): ";
  351. char ldrp;
  352. cin.ignore();
  353. cin.get(ldrp);
  354. if (ldrp=='l')
  355. if (ExistsLeftChild(cvor,stablo)==true)
  356. cvor=LeftChildB(cvor,stablo);
  357. else
  358. cerr<<"Lijevo dijete ne postoji, te bi pomak ovim putem uzrokovao iskakanje kursora iz stabla!"<<endl;
  359. else if (ldrp=='d')
  360. if (ExistsRightChild(cvor,stablo)==true)
  361. cvor=RightChildB(cvor,stablo);
  362. else
  363. cerr<<"Desno dijete ne postoji, te bi pomak ovim putem uzrokovao iskakanje kursora iz stabla!"<<endl;
  364. else if (ldrp=='p') {
  365. cout<<"Unesite novu oznaku (vrijednost) trenutnog elementa: ";
  366. int vrijednost;
  367. cin>>vrijednost;
  368. ChangeLabelB(vrijednost,cvor,stablo);
  369. promijenjeno=true;
  370. }
  371. else if (ldrp=='r') {
  372. if (ParentB(cvor,stablo)<=0)
  373. cerr<<"Korijen nema svoga roditelja! Pozicija kursora ostaje nepromijenjena.."<<endl;
  374. else
  375. cvor=ParentB(cvor,stablo);
  376. }
  377. } while (promijenjeno==false);
  378. }
  379. break;
  380. }
  381. }
  382. /////////////////////////// funkcija parentB kod pokaziva�a ne radi!
  383. void ispuni_bst (int vrijednost,tbinarno &bst) {
  384. if (bst==NULL) {
  385. InitB(vrijednost,bst);
  386. }
  387. else {
  388. tcvor cvor=RootB(bst);
  389. bool stani=false;
  390. while (stani==false) {
  391. if (vrijednost<LabelB(cvor,bst))
  392. if (ExistsLeftChild(cvor,bst)==true)
  393. cvor=LeftChildB(cvor,bst);
  394. else {
  395. CreateLeftB(vrijednost,cvor,bst);
  396. stani=true;
  397. cout<<"Element sa vrijednoscu "<<vrijednost<<" je uspjesno dodan!"<<endl;
  398. }
  399. else if (vrijednost>LabelB(cvor,bst))
  400. if (ExistsRightChild(cvor,bst)==true)
  401. cvor=RightChildB(cvor,bst);
  402. else {
  403. CreateRightB(vrijednost,cvor,bst);
  404. stani=true;
  405. cout<<"Element sa vrijednoscu "<<vrijednost<<" je uspjesno dodan!"<<endl;
  406. }
  407. else {
  408. cout<<"Element nije dodan jer vec postoji!"<<endl;
  409. stani=true;
  410. }
  411. }
  412. }
  413. }
  414. void tockaE () {
  415. cout<<"1. Ispuni binarno stablo pretrazivanja po primjeru iz laboratorijskih vjezbi"<<endl;
  416. cout<<"2. Ispuni binarno stablo pretrazivanja prethodno izgeneriranim brojevima"<<endl;
  417. cout<<"3. Generiraj niz pseudoslucajnih brojeva te sa njima ispuni binarno stablo pretrazivanja"<<endl;
  418. cout<<"4. Rucni unos brojeva u binarno stablo pretrazivanja"<<endl;
  419. cout<<"5. Pretrazivanje vrijednosti unutar binarnog stabla pretrazivanja"<<endl;
  420. cout<<"Vas izbor: ";
  421. short izbor;
  422. cin>>izbor;
  423. switch (izbor) {
  424. case 1:
  425. ispuni_bst(6,stablotr);
  426. ispuni_bst(3,stablotr);
  427. ispuni_bst(7,stablotr);
  428. ispuni_bst(9,stablotr);
  429. ispuni_bst(4,stablotr);
  430. ispuni_bst(2,stablotr);
  431. ispuni_bst(8,stablotr);
  432. ispuni_bst(1,stablotr);
  433. break;
  434. case 3:
  435. cout<<"Unesite kolicinu brojeva koju zelite izgenerirati i staviti u stablo: ";
  436. cin>>N;
  437. brojevi=new int [N];
  438. for (int i=0;i<N;i++)
  439. brojevi[i]=rand()%10000;
  440. case 2:
  441. if (brojevi==NULL)
  442. cout<<"Polje brojeva do sada jos nije generirano!"<<endl;
  443. else
  444. for (int i=0;i<N;i++)
  445. ispuni_bst(brojevi[i],stablotr);
  446. break;
  447. case 4:
  448. char jos;
  449. short vrijednost;
  450. if (stablotr==NULL) {
  451. cout<<"Korijen nije alociran! Unesite vrijednost korijena: ";
  452. cin>>vrijednost;
  453. }
  454. cout<<"Da li zelite unijeti jos koji element? (d/n): ";
  455. cin.ignore();
  456. cin.get(jos);
  457. while (jos=='d') {
  458. cout<<"Unesite vrijednost elementa kojeg zelite dodati: ";
  459. cin>>vrijednost;
  460. ispuni_bst(vrijednost,stablotr);
  461. cout<<"Da li zelite unijeti jos koji element? (d/n): ";
  462. cin.ignore();
  463. cin.get(jos);
  464. }
  465. break;
  466. case 5:
  467. cout<<"Unesite vrijednost elementa kojeg zelite pronaci: ";
  468. cin>>vrijednost;
  469. tcvor cvor=RootB(stablotr);
  470. while (true) {
  471. if (vrijednost<LabelB(cvor,stablotr))
  472. if (ExistsLeftChild(cvor,stablotr)==true)
  473. cvor=LeftChildB(cvor,stablotr);
  474. else {
  475. cout<<"Element se NE nalazi u binarnom stablu pretrazivanja!"<<endl;
  476. return;
  477. }
  478. else if (vrijednost>LabelB(cvor,stablotr))
  479. if (ExistsRightChild(cvor,stablotr)==true)
  480. cvor=RightChildB(cvor,stablotr);
  481. else {
  482. cout<<"Element se NE nalazi u binarnom stablu pretrazivanja!"<<endl;
  483. return;
  484. }
  485. else {
  486. cout<<"Element se nalazi u binarnom stablu pretrazivanja!"<<endl;
  487. return;
  488. }
  489. }
  490. }
  491. }
  492. void ispis (tbinarno &stablo) {
  493. if (stablo==NULL)
  494. cout<<"Korijen nije alociran! Nema elementa kojem bi se promijenila oznaka (vrijednost)..";
  495. else {
  496. tcvor cvor=RootB(stablo);
  497. bool promijenjeno=false;
  498. do {
  499. cout<<"Zelite li pomaknuti kursor na element lijevo ("<<(ExistsLeftChild(cvor,stablo)==false?-1:LabelB(LeftChildB(cvor,stablo),stablo))<<"), desno ("<<(ExistsRightChild(cvor,stablo)==false?-1:LabelB(RightChildB(cvor,stablo),stablo))<<"), natrag na roditelja ("<<(ParentB(cvor,stablo)<=0?-1:LabelB(ParentB(cvor,stablo),stablo))<<") ili zavrsiti rad ("<<LabelB(cvor,stablo)<<") (l/d/r/q): ";
  500. char ldrp;
  501. cin.ignore();
  502. cin.get(ldrp);
  503. if (ldrp=='l')
  504. if (ExistsLeftChild(cvor,stablo)==true)
  505. cvor=LeftChildB(cvor,stablo);
  506. else
  507. cerr<<"Lijevo dijete ne postoji, te bi pomak ovim putem uzrokovao iskakanje kursora iz stabla!"<<endl;
  508. else if (ldrp=='d')
  509. if (ExistsRightChild(cvor,stablo)==true)
  510. cvor=RightChildB(cvor,stablo);
  511. else
  512. cerr<<"Desno dijete ne postoji, te bi pomak ovim putem uzrokovao iskakanje kursora iz stabla!"<<endl;
  513. else if (ldrp=='q')
  514. return;
  515. else if (ldrp=='r') {
  516. if (ParentB(cvor,stablo)<=0)
  517. cerr<<"Korijen nema svoga roditelja! Pozicija kursora ostaje nepromijenjena.."<<endl;
  518. else
  519. cvor=ParentB(cvor,stablo);
  520. }
  521. } while (promijenjeno==false);
  522. }
  523. }
  524. char directions[1000];
  525. int M=0;
  526. void ispuni_hrpu (int vrijednost,tbinarno &hrpa) {
  527. if (hrpa==NULL) {
  528. M++;
  529. InitB(vrijednost,hrpa);
  530. }
  531. else {
  532. M++;
  533. int i=M;
  534. int j=0;
  535. while (i/2!=0) {
  536. if (i%2==0)
  537. directions[j++]='l';
  538. else
  539. directions[j++]='d';
  540. i=i/2;
  541. }
  542. rcvor cvor=RootB(hrpa);
  543. for (int k=j-1;k>=0;k--)
  544. if (directions[k]=='l')
  545. if (ExistsLeftChild(cvor,hrpa)==true)
  546. cvor=LeftChildB(cvor,hrpa);
  547. else {
  548. CreateLeftB(vrijednost,cvor,hrpa);
  549. cvor=LeftChildB(cvor,hrpa);
  550. }
  551. else
  552. if (ExistsRightChild(cvor,hrpa)==true)
  553. cvor=RightChildB(cvor,hrpa);
  554. else {
  555. CreateRightB(vrijednost,cvor,hrpa);
  556. cvor=RightChildB(cvor,hrpa);
  557. }
  558. while (cvor!=RootB(hrpa) && LabelB(ParentB(cvor,hrpa),hrpa)>LabelB(cvor,hrpa)) {
  559. int pom=LabelB(cvor,hrpa);
  560. ChangeLabelB(LabelB(ParentB(cvor,hrpa),hrpa),cvor,hrpa);
  561. ChangeLabelB(pom,ParentB(cvor,hrpa),hrpa);
  562. cvor=ParentB(cvor,hrpa);
  563. }
  564. }
  565. }
  566. int P;
  567. void brisi_i_seli () {
  568. if (M==0)
  569. return;
  570. else {
  571. int i=M;
  572. int j=0;
  573. while (i/2!=0) {
  574. if (i%2==0)
  575. directions[j++]='l';
  576. else
  577. directions[j++]='d';
  578. i=i/2;
  579. }
  580. tcvor cvor=RootB(hrpa);
  581. tcvor cvor2=RootB(hrpa);
  582. for (int k=j-1;k>=0;k--) {
  583. if (directions[k]=='l')
  584. cvor=LeftChildB(cvor,hrpa);
  585. else
  586. cvor=RightChildB(cvor,hrpa);
  587. if (ExistsLeftChild(cvor2,hrpa)==false && ExistsRightChild(cvor2,hrpa)==false)
  588. continue;
  589. else if (ExistsLeftChild(cvor2,hrpa)==false) {
  590. if (LabelB(cvor2,hrpa)>LabelB(RightChildB(cvor2,hrpa),hrpa)) {
  591. int pom=LabelB(RightChildB(cvor2,hrpa),hrpa);
  592. ChangeLabelB(LabelB(cvor2,hrpa),RightChildB(cvor2,hrpa),hrpa);
  593. ChangeLabelB(pom,cvor2,hrpa);
  594. cvor2=RightChildB(cvor2,hrpa);
  595. }
  596. }
  597. else if (ExistsRightChild(cvor2,hrpa)==false) {
  598. if (LabelB(cvor2,hrpa)>LabelB(LeftChildB(cvor2,hrpa),hrpa)) {
  599. int pom=LabelB(LeftChildB(cvor2,hrpa),hrpa);
  600. ChangeLabelB(LabelB(cvor2,hrpa),LeftChildB(cvor2,hrpa),hrpa);
  601. ChangeLabelB(pom,cvor2,hrpa);
  602. cvor2=LeftChildB(cvor2,hrpa);
  603. }
  604. }
  605. else
  606. if (LabelB(LeftChildB(cvor2,hrpa),hrpa)<LabelB(cvor2,hrpa) || LabelB(RightChildB(cvor2,hrpa),hrpa)<LabelB(cvor2,hrpa))
  607. if (LabelB(LeftChildB(cvor2,hrpa),hrpa)<=LabelB(RightChildB(cvor2,hrpa),hrpa)) {
  608. int pom=LabelB(LeftChildB(cvor2,hrpa),hrpa);
  609. ChangeLabelB(LabelB(cvor2,hrpa),LeftChildB(cvor2,hrpa),hrpa);
  610. ChangeLabelB(pom,cvor2,hrpa);
  611. cvor2=LeftChildB(cvor2,hrpa);
  612. }
  613. else {
  614. int pom=LabelB(RightChildB(cvor2,hrpa),hrpa);
  615. ChangeLabelB(LabelB(cvor2,hrpa),RightChildB(cvor2,hrpa),hrpa);
  616. ChangeLabelB(pom,cvor2,hrpa);
  617. cvor2=RightChildB(cvor2,hrpa);
  618. }
  619. else
  620. continue;
  621. }
  622. sortirano_polje[P-M]=LabelB(RootB(hrpa),hrpa);
  623. ChangeLabelB(LabelB(cvor,hrpa),RootB(hrpa),hrpa);
  624. DeleteB(cvor,hrpa);
  625. M--;
  626. brisi_i_seli();
  627. }
  628. }
  629. void tockaF () {
  630. cout<<"1. Ispuni stablo hrpu po primjeru iz laboratorijskih vjezbi"<<endl;
  631. cout<<"2. Ispuni stablo hrpu prethodno izgeneriranim brojevima"<<endl;
  632. cout<<"3. Generiraj niz pseudoslucajnih brojeva te sa njima ispuni stablo hrpu"<<endl;
  633. cout<<"4. Rucni unos brojeva u stablo hrpu"<<endl;
  634. cout<<"5. Heap-sort nad stablom hrpe (za sad samo radi sa binarnim stablom implementiranim pomocu polja)"<<endl;
  635. cout<<"Vas izbor: ";
  636. short izbor;
  637. cin>>izbor;
  638. switch(izbor) {
  639. case 1:
  640. ispuni_hrpu(6,hrpa);
  641. ispuni_hrpu(2,hrpa);
  642. ispuni_hrpu(7,hrpa);
  643. ispuni_hrpu(5,hrpa);
  644. ispuni_hrpu(8,hrpa);
  645. ispuni_hrpu(2,hrpa);
  646. ispuni_hrpu(8,hrpa);
  647. ispuni_hrpu(9,hrpa);
  648. ispuni_hrpu(1,hrpa);
  649. break;
  650. case 3:
  651. cout<<"Unesite kolicinu brojeva koju zelite izgenerirati i staviti u stablo: ";
  652. cin>>N;
  653. brojevi=new int [N];
  654. for (int i=0;i<N;i++)
  655. brojevi[i]=rand()%10000;
  656. case 2:
  657. if (brojevi==NULL)
  658. cout<<"Polje brojeva do sada jos nije generirano!"<<endl;
  659. else
  660. for (int i=0;i<N;i++)
  661. ispuni_hrpu(brojevi[i],hrpa);
  662. break;
  663. case 4:
  664. int vrijednost;
  665. if (hrpa==NULL) {
  666. cout<<"Korijen hrpe nije alociran! Unesite vrijednost korijena: ";
  667. cin>>vrijednost;
  668. ispuni_hrpu(vrijednost,hrpa);
  669. }
  670. char jos;
  671. cout<<"Da li zelite dodati jos koji element u hrpu? (d/n): ";
  672. cin.ignore();
  673. cin.get(jos);
  674. while (jos=='d') {
  675. cout<<"Unesite vrijednost elementa kojeg zelite dodati: ";
  676. cin>>vrijednost;
  677. ispuni_hrpu(vrijednost,hrpa);
  678. cout<<"Da li zelite dodati jos koji element u hrpu? (d/n): ";
  679. cin.ignore();
  680. cin.get(jos);
  681. }
  682. break;
  683. case 5:
  684. if (hrpa==NULL)
  685. cout<<"Nema elemenata unutar hrpe, pa se nema ni sto sortirati!"<<endl;
  686. else {
  687. sortirano_polje=new int [M];
  688. P=M;
  689. brisi_i_seli();
  690. cout<<"Polje sortirano nakon heap-sorta: ";
  691. for (int i=0;i<P;i++)
  692. cout<<sortirano_polje[i]<<" ";
  693. cout<<endl;
  694. delete [] sortirano_polje;
  695. }
  696. }
  697. }
  698.  
  699. int main () {
  700. srand(time(0));
  701. rand();
  702. memset(&stablo1,-1,sizeof(tstablo));
  703. short izbor;
  704. do {
  705. system("cls");
  706. cout<<"1. Rad sa stablom 'prvo dijete - sljedeci brat'"<<endl;
  707. cout<<"2. Ophodjenje opcenitog stabla"<<endl;
  708. cout<<"3. Rad sa binarnim stablom"<<endl;
  709. cout<<"4. Rad sa binarnim stablom pretrazivanja"<<endl;
  710. cout<<"5. Rad sa hrpom"<<endl;
  711. cout<<"9. Izlaz iz programa"<<endl;
  712. cout<<"Vas izbor: ";
  713. cin>>izbor;
  714. switch (izbor) {
  715. case 1:
  716. tockaA();
  717. break;
  718. case 2:
  719. tockaB();
  720. break;
  721. case 3:
  722. tockaCD();
  723. break;
  724. case 4:
  725. tockaE();
  726. break;
  727. case 5:
  728. tockaF();
  729. break;
  730. case 9:
  731. cout<<"Kraj programa.."<<endl;
  732. break;
  733. default:
  734. cout<<"Neispravan unos!"<<endl;
  735. }
  736. system("pause");
  737. } while (izbor!=9);
  738. return 0;
  739. }

Report this snippet  

You need to login to post a comment.