Posted By

vangogh94 on 01/21/15


Tagged

Strukture polje stablo podatak


Versions (?)

stablo_polje.h


 / Published in: C++
 

Biblioteka sa funkcijama za rad sa stablom preko polja, ophođenje stabla

  1. #include <iostream>
  2. using namespace std;
  3.  
  4. struct dataStrukt {
  5. int data;
  6. short prviSin, sl;
  7. dataStrukt(): data(-1), prviSin(-1), sl(-1){}
  8. };
  9. //n=indeks, x=vrijednost, T=stablo,
  10.  
  11. //prviSin i sl = indeksi
  12. struct stabloStrukt {
  13. dataStrukt cvor [10000];
  14. int korijen;
  15. };
  16.  
  17. short kursor=1;
  18.  
  19. void InitT (int unos, stabloStrukt *&stablo){
  20. stablo=new stabloStrukt;
  21. stablo->cvor[0].data=unos;
  22. stablo->korijen=0;
  23. }
  24.  
  25. dataStrukt RootT(stabloStrukt *stablo){
  26. return stablo->cvor[stablo->korijen];
  27. }
  28.  
  29. int LabelT(short indeks, stabloStrukt *stablo){
  30. if(indeks>=0&&indeks<10000)
  31. return stablo->cvor[indeks].data;
  32. }
  33.  
  34. dataStrukt *NextSiblingT(short indeks, stabloStrukt *stablo){
  35. if(indeks>=0&&indeks<10000)
  36. if(stablo->cvor[indeks].sl!=-1)
  37. return &stablo->cvor[stablo->cvor[indeks].sl];
  38. return NULL;
  39. }
  40.  
  41. dataStrukt *FirstChildT(short indeks, stabloStrukt *stablo){
  42. if(indeks>=0&&indeks<10000)
  43. if(stablo->cvor[indeks].prviSin!=-1)
  44. return &stablo->cvor[indeks];
  45. return NULL;
  46. }
  47.  
  48. dataStrukt *ParentT(short indeks, stabloStrukt *stablo){
  49. if(indeks==stablo->korijen)
  50. return NULL;
  51. for(short i=0; i<10000; i++){
  52. if(stablo->cvor[i].prviSin==indeks)
  53. return &stablo->cvor[i];
  54. if(stablo->cvor[i].sl==indeks){
  55. //ako je naš element zapravo desni sl od nekoga onda tražimo oca od tog lijevog i tako radimo dok ne na�emo oca od prvog brata
  56. indeks=i;
  57. i=-1;
  58. }
  59. }
  60. }
  61.  
  62. bool CreateT(int unos, short indeks, stabloStrukt *stablo){
  63. if(stablo->cvor[indeks].data==-1){
  64. return false;
  65. }
  66. if(stablo->cvor[indeks].prviSin==-1){//ako cvor nema djece dodajemo ga direkt
  67. stablo->cvor[indeks].prviSin=kursor;
  68. }
  69. else{//ako ima onda ga dodajemo na najdesnije prviSin
  70. int pom=stablo->cvor[indeks].prviSin;
  71. while(stablo->cvor[pom].sl!=-1)//dok ima sljedecih
  72. pom=stablo->cvor[pom].sl;//idemo na sljedece
  73. stablo->cvor[pom].sl=kursor;//pom je sada indeks najdesnijeg brata
  74. }
  75. stablo->cvor[kursor++].data=unos;//dodajem zadanu vrijednost novom cvoru
  76. return true;
  77.  
  78. }
  79.  
  80.  
  81. bool ChangeLabelT(int unos, short indeks, stabloStrukt *stablo){
  82. if(stablo->cvor[indeks].data==-1)
  83. return false;
  84. stablo->cvor[indeks].data=unos;
  85. return true;
  86. }
  87.  
  88. void DeleteT(short indeks, stabloStrukt *stablo){
  89. int sin, sl;
  90. if((sin=stablo->cvor[indeks].prviSin)!=-1){//spuštamo se na najnižu razinu po�evši od zadanog �vora (indeksa)
  91. stablo->cvor[indeks].prviSin=-1;
  92. DeleteT(sin, stablo);
  93. }
  94. if((sl=stablo->cvor[indeks].sl)!=-1){//kada smo na hijerarhiji onda idemo do najdesnijeg buraza
  95. stablo->cvor[indeks].sl=-1;
  96. DeleteT(sl, stablo);
  97. }
  98. //"brišemo" cvor
  99. dataStrukt *otac=ParentT(indeks,stablo);
  100. stablo->cvor[indeks].prviSin=-1;
  101. stablo->cvor[indeks].sl=-1;
  102. stablo->cvor[indeks].data=-1;
  103. kursor--;
  104. }
  105.  
  106. void PreorderT(int n, stabloStrukt *S){
  107. cout<<LabelT(n,S)<<" ";
  108. if(S->cvor[n].prviSin!=-1)
  109. PreorderT(S->cvor[n].prviSin,S);
  110. if(S->cvor[n].sl!=-1)
  111. PreorderT(S->cvor[n].sl,S);
  112. }
  113.  
  114. void InorderT(int n, stabloStrukt *S){
  115. if(S->cvor[n].prviSin!=-1)
  116. InorderT(S->cvor[n].prviSin,S);
  117. cout<<LabelT(n,S)<<" ";
  118. if(S->cvor[n].prviSin!=-1){
  119. n=S->cvor[n].prviSin;
  120. while(S->cvor[n].sl!=-1){
  121. n=S->cvor[n].sl;
  122. InorderT(n,S);
  123. }
  124. }
  125. }
  126. void PostorderT(int n, stabloStrukt *S){
  127. if(S->cvor[n].prviSin!=-1)
  128. PostorderT(S->cvor[n].prviSin,S);
  129. int pom=n;
  130. if(S->cvor[pom].prviSin!=-1){
  131. pom=S->cvor[n].prviSin;
  132. while(S->cvor[pom].sl!=-1){
  133. pom=S->cvor[pom].sl;
  134. PostorderT(pom,S);
  135. }
  136. }
  137. cout<<LabelT(n,S)<<" ";
  138. }

Report this snippet  

You need to login to post a comment.