Posted By

mogrguric on 01/05/11


Tagged

sp4


Versions (?)

bstablo polje


 / Published in: C++
 

  1. struct elem {
  2. int label;
  3. int used;
  4. };
  5. struct bt {
  6. struct elem elements[20000];
  7. };
  8.  
  9. typedef int node;
  10.  
  11. //funkcija vraca roditelja cvora n, a ako je n korijen, onda vraća null-cvor
  12. node ParentB(node n, bt *tree){
  13. if (n==1){
  14. cout<<"\nZa zadani korijen stabla, ne postoji odgovarajuci roditelj!"<<endl;
  15. return 0;}
  16. if(n%2) n--;
  17. return n/2;
  18. }
  19.  
  20. //funkcija vraca lijevo dijete cvora n. Ako &#269;vor n nema lijevog djeteta, onda vra&#263;a null-cvor
  21. node LeftChildB(node n, bt *tree){
  22. if (tree->elements[n].used==0)
  23. return 0;
  24. if(tree->elements[2*n].used==1)
  25. return 2*n;
  26. else
  27. return 0;
  28. }
  29.  
  30. //funkcija vraca desno dijete cvora n. Ako &#269;vor n nema desnog djeteta, onda vra&#263;a null-cvor
  31. node RightChildB(node n, bt *tree){
  32. if (tree->elements[n].used==0)
  33. return 0;
  34. if(tree->elements[2*n+1].used==1)
  35. return 2*n+1;
  36. else
  37. return 0;
  38. }
  39.  
  40. //funkcija koja vraca oznaku (vrijednost) koju sadrži cvor n
  41. int LabelB(node n, bt *tree){
  42. if (tree->elements[n].used==1){
  43. return tree->elements[n].label; }
  44. else { cout<<"Cvor ne postoji ! "<<endl;
  45. return -1; }
  46. }
  47.  
  48. //mijenja oznaku cvora n u stablu tree na vrijednost x
  49. int ChangeLabelB(int x, node n, bt *tree){
  50. if(tree->elements[n].used==0){
  51. cout<<"Cvor ne postoji u stablu ! "<<endl;
  52. return;}
  53. else {tree->elements[n].label=x; }
  54.  
  55. }
  56.  
  57. //funkcija koja vraca korijen binarnog stabla tree. Ako je stablo prazno,onda vra&#263;a null-cvor
  58. node RootB(bt *tree){
  59. if(tree->elements[1].used) return 1;
  60. else {cout << "Stablo nema korijen, ne postoji!" << endl;
  61. return 0; }
  62. }
  63.  
  64. //Procedura dodaje x kao lijevo dijete cvora n.
  65. //Ako cvor n ve&#263; ima lijevo dijete, onda se javlja poruka pogreske.
  66. void CreateLeftB(int x, node n, bt *tree){
  67. if(tree->elements[n].used==0 || tree->elements[2*n].used==1) {
  68. cout << "Pogreska!" << endl;
  69. return; }
  70.  
  71. tree->elements[2*n].used=1;
  72. tree->elements[2*n].label=x;
  73. }
  74.  
  75. //Procedura dodaje x kao desno dijete cvora n.
  76. //Ako cvor n ve&#263; ima lijevo dijete, onda se javlja poruka pogreske.
  77. void CreateRightB(int x, node n, bt *tree){
  78. if(tree->elements[n].used==0 || tree->elements[2*n+1].used==1) {
  79. cout << "Pogreska!" << endl;
  80. return; }
  81.  
  82. tree->elements[2*n+1].used=1;
  83. tree->elements[2*n+1].label=x;
  84. }
  85.  
  86. //procedura brise cvor n, a s njim i sve njegove potomke iz stabla T
  87. void DeleteB(node n, bt *tree){
  88. if (tree->elements[n].used=1){
  89. cout<<"\nNije dozvoljeno brisati korijen stabla!";
  90. return 0; }
  91. else {
  92. if(LeftChildB(n,tree))
  93. DeleteB(LeftChildB(n,tree),tree);
  94. if(RightChildB(n,tree))
  95. DeleteB(RightChildB(n,tree),tree); }
  96. }
  97.  
  98. //inicijalizira stablo tree s korijenom x
  99. bt* InitB(int x, bt *tree){
  100. if(tree)
  101. delete tree;
  102. tree=new bt;
  103. for(int i=0; i<10000; i++)
  104. tree->elements[i].used=0;
  105. tree->elements[1].label=x;
  106. tree->elements[1].used=1;
  107. return tree;
  108. }
  109. }

Report this snippet  

You need to login to post a comment.