Posted By

javert on 01/19/15


Tagged

sp


Versions (?)

btree_array.h


 / Published in: C++
 

Implementacija ATP stablo, polje

  1. struct element {
  2. int v;
  3. bool u;
  4. };
  5.  
  6. struct tree {
  7. element values[10000];
  8. };
  9.  
  10. typedef tree* binTree;
  11. typedef int node;
  12.  
  13. binTree initB(int x, binTree T) {
  14. T = new tree;
  15.  
  16. T->values[0].u=0;
  17. for(int i=2; i<10000; i++) {
  18. T->values[i].u=0;
  19. T->values[i].v=0;
  20. }
  21.  
  22. T->values[1].v = x;
  23. T->values[1].u = 1;
  24.  
  25. return T;
  26. }
  27.  
  28. node rootB(binTree T) {
  29. return 1;
  30. }
  31.  
  32. node parentB(node n, binTree T) {
  33. if(n==rootB(T))
  34. return 0;
  35. else return n/2;
  36. }
  37.  
  38. node leftChildB(node n, binTree T) {
  39. if(T->values[n*2].u==0)
  40. return 0;
  41. else return n*2;
  42. }
  43.  
  44. node rightChildB(node n, binTree T) {
  45. if(T->values[n*2+1].u==0)
  46. return 0;
  47. else return n*2+1;
  48. }
  49.  
  50. int labelB(node n, binTree T) {
  51. int label=T->values[n].v;
  52. return label;
  53. }
  54.  
  55. void changeLabelB(int x, node n, binTree T) {
  56. if(n>=0 && n<10000)
  57. T->values[n].v = x;
  58. }
  59.  
  60. void createLeftB(int x, node n, binTree T) {
  61. if(n<0 || n>10000) return;
  62.  
  63. if(T->values[n*2].u)
  64. return;
  65.  
  66. T->values[n*2].v = x;
  67. T->values[n*2].u = 1;
  68. }
  69.  
  70. void createRightB(int x, node n, binTree T) {
  71. if(n<0 || n>10000) return;
  72.  
  73. if(T->values[n*2+1].u)
  74. return;
  75.  
  76. T->values[n*2+1].v = x;
  77. T->values[n*2+1].u = 1;
  78. }
  79.  
  80. bool existsLeftChildB(node n, binTree T) {
  81. node temp = leftChildB(n,T);
  82. if(T->values[temp].u) return true;
  83. else return false;
  84. }
  85.  
  86. bool existsRightChildB(node n, binTree T) {
  87. node temp = rightChildB(n,T);
  88. if(T->values[temp].u) return true;
  89. else return false;
  90. }
  91.  
  92. void deleteB(node n, binTree T) {
  93. if(n==1)return;
  94. if(n>=10000)return;
  95.  
  96. if(T->values[n*2].u)
  97. deleteB(n*2, T);
  98. if(T->values[n*2+1].u)
  99. deleteB(n*2+1, T);
  100.  
  101. T->values[n].u = 0;
  102. }

Report this snippet  

You need to login to post a comment.