Strukture stabla


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

implementacija opcenitog stabla
tree.h


Copy this code and paste it in your HTML
  1. #include <cstring>
  2. #include <iostream>
  3. using namespace std;
  4. struct elem{
  5. string label;
  6. int firstchild;
  7. int nextsibling;
  8. bool flag;
  9. };
  10. struct tr{
  11. struct elem elements[10000];
  12. int first;
  13. };
  14. typedef struct tr tree;
  15. typedef int node;
  16.  
  17. void InitT(int korijen, tree *stablo){
  18. stablo->first=korijen;
  19. stablo->elements[korijen].firstchild=-1;
  20. stablo->elements[korijen].nextsibling=-1;
  21. }
  22.  
  23. int ParentT(int cvor, tree *stablo){
  24. if(stablo->first==cvor){
  25. return -1;
  26. cout<<"Cvor je korijen\n";
  27. }
  28. for (int i=0;i<10000;i++){
  29. if(stablo->elements[i].firstchild==cvor)
  30. return i;
  31. else if(stablo->elements[i].nextsibling==cvor){
  32. ParentT(i,stablo);
  33. }
  34. }
  35. return -1;
  36. cout<<"Cvor ne postoji...\n";
  37. }
  38. int FirstChildT(int cvor, tree *stablo){
  39. if(stablo->elements[cvor].firstchild==-1) {
  40. cout<<"Zadani cvor je list...\n";
  41. return -1;
  42. }
  43. else
  44. return stablo->elements[cvor].firstchild;
  45. }
  46. int NextSiblingT(int cvor, tree *stablo){
  47. if(stablo->elements[cvor].nextsibling==-1){
  48. cout<<"Cvor je najdesnije dijete...\n";
  49. return -1;
  50. }
  51. else
  52. return stablo->elements[cvor].nextsibling;
  53. }
  54.  
  55. void LabelT(int cvor, tree *stablo){
  56. if(stablo->elements[cvor].flag==false)
  57. {
  58. cout<<"Taj cvor ne postoji...\n";
  59. return;
  60. }
  61. else
  62. cout<<"Label na cvoru "<<cvor<<" je: "<<stablo->elements[cvor].label<<endl;
  63. }
  64. int RootT(tree *stablo){
  65. return stablo->first;
  66. }
  67.  
  68. void CreateT(int dijete, int cvor, tree *stablo){
  69. if(stablo->elements[cvor].firstchild==-1){
  70. stablo->elements[cvor].firstchild=dijete;
  71. stablo->elements[dijete].firstchild=-1;
  72. stablo->elements[dijete].nextsibling=-1;
  73. stablo->elements[dijete].flag=true;
  74. cout<<"\nKoju vrijednost zelite unijeti za LABEL: ";
  75. getline(cin,stablo->elements[dijete].label);
  76. }
  77. else{
  78. int Brat;
  79. bool imaBrata=true;
  80. //" "brute force" rekurzija"
  81. Brat=stablo->elements[cvor].firstchild;
  82. do{
  83. //ako ne postoji sljedeci brat onda ga dodaj tj izbij iz do while
  84. if(stablo->elements[Brat].nextsibling==-1)
  85. imaBrata=false;
  86. else{
  87. //ako ima brata onda preskoci na njega u testiranju
  88. Brat=stablo->elements[Brat].nextsibling;
  89. }//else
  90. }while(imaBrata);
  91. //dodaj brata
  92. stablo->elements[Brat].nextsibling=dijete;
  93. stablo->elements[dijete].firstchild=-1;
  94. stablo->elements[dijete].nextsibling=-1;
  95. stablo->elements[dijete].flag=true;
  96. cout<<"\nKoju vrijednost zelite unijeti za LABEL: ";
  97. getline(cin,stablo->elements[dijete].label);
  98. }//else
  99. }//CreateT
  100.  
  101. void ChangeLabelT(string x, int cvor, tree *stablo){
  102. stablo->elements[cvor].label=x;
  103. }
  104.  
  105. void brisi(int cvor, tree *stablo){
  106.  
  107. if(stablo->elements[cvor].nextsibling==-1&&stablo->elements[ParentT(cvor,stablo)].firstchild==cvor){//ako ima samo 1 dijete
  108. stablo->elements[ParentT(cvor,stablo)].firstchild=-1;
  109. stablo->elements[cvor].flag=false;
  110. }
  111. else if(stablo->elements[cvor].nextsibling!=-1&&stablo->elements[ParentT(cvor,stablo)].firstchild==cvor){//ako ima vise djece a brisemo prvo
  112. stablo->elements[ParentT(cvor,stablo)].firstchild=stablo->elements[cvor].nextsibling;
  113. stablo->elements[cvor].flag=false;
  114. }
  115. else{//brisanje u sred djece
  116. int brat=stablo->elements[ParentT(cvor,stablo)].firstchild;
  117. while(stablo->elements[brat].nextsibling!=cvor){
  118. brat=stablo->elements[brat].nextsibling;
  119. }
  120. stablo->elements[brat].nextsibling=stablo->elements[cvor].firstchild;
  121. stablo->elements[cvor].flag=false;
  122. }
  123. }
  124. void DeleteT(int cvor,tree *stablo){
  125. if(stablo->elements[cvor].firstchild!=-1){
  126. while(stablo->elements[cvor].firstchild!=-1){
  127. brisi(stablo->elements[cvor].firstchild,stablo);
  128. }
  129. brisi(cvor,stablo);
  130. }
  131. else
  132. brisi(cvor,stablo);
  133. }

Report this snippet


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.