Posted By

elvis_popovic on 01/19/15


Tagged

array tree adt c++


Versions (?)

ADT Binary tree - array implementation header


 / Published in: C++
 

An C++ header using templates. Array implementation of binary tree.

  1. #ifndef __POLJE__
  2. #define __POLJE__
  3. #include <iostream>
  4. #define N_ELEMENTS 10000
  5.  
  6. namespace stablo_polje{
  7.  
  8. template<typename labeltype>
  9. struct element{
  10. element(){
  11. used=false;
  12. }
  13. labeltype label;
  14. bool used;
  15. };
  16.  
  17. template<typename labeltype>
  18. struct bt {
  19. element <labeltype>elements[N_ELEMENTS];
  20. };
  21.  
  22. template<typename labeltype>
  23. int ParentB(int n,bt<labeltype>&T)
  24. {
  25. if(n<2||!T.elements[n].used) return -1;
  26. if(!T.elements[n/2].used) return -1;
  27. else return(n/2);
  28. }
  29.  
  30. template<typename labeltype>
  31. int LeftChildB(int n, bt<labeltype>&T)
  32. {
  33. if(n<1||n>=N_ELEMENTS/2||(!T.elements[n].used)) return -1;
  34. if(!T.elements[n*2].used) return -1;
  35. else return n*2;
  36. }
  37. template<typename labeltype>
  38. int RightChildB(int n, bt<labeltype>&T)
  39. {
  40. if(n<1||n>=N_ELEMENTS/2||(!T.elements[n].used)) return -1;
  41. if(!T.elements[n*2+1].used) return -1;
  42. else return n*2+1;
  43. }
  44. template<typename labeltype>
  45. labeltype LabelB(int n, bt<labeltype>&T)
  46. {
  47. if(n<1||n>=N_ELEMENTS) return -1;
  48. if(!T.elements[n].used) return -1;
  49. else return T.elements[n].label;
  50. }
  51. template<typename labeltype>
  52. void ChangeLabelB(labeltype x, int n, bt<labeltype>&T)
  53. {
  54. if(n<1||n>=N_ELEMENTS) return;
  55. if(T.elements[n].used)
  56. T.elements[n].label=x;
  57. }
  58. template<typename labeltype>
  59. int RootB(bt<labeltype>&T)
  60. {
  61. if(!T.elements[1].used) return -1;
  62. else return 1;
  63. }
  64. template<typename labeltype>
  65. bool CreateLeftB(labeltype x, int n, bt<labeltype>&T)
  66. {
  67. if(n<1||n>=N_ELEMENTS) return false;
  68. if(T.elements[n*2].used) return false;
  69. T.elements[n*2].used=true;
  70. T.elements[n*2].label=x;
  71. return true;
  72. }
  73. template<typename labeltype>
  74. bool CreateRightB(labeltype x, int n, bt<labeltype>&T)
  75. {
  76. if(n<1||n>=N_ELEMENTS) return false;
  77. if(T.elements[n*2+1].used) return false;
  78. T.elements[n*2+1].used=true;
  79. T.elements[n*2+1].label=x;
  80. return true;
  81. }
  82. template<typename labeltype>
  83. void InitB(labeltype x, bt<labeltype>&T)
  84. {
  85. int i;
  86. T.elements[1].used=true;
  87. T.elements[1].label=x;
  88. for(i=2; i<N_ELEMENTS; i++)
  89. T.elements[i].used=false;
  90. }
  91. template<typename labeltype>
  92. void DeleteB(int n, bt<labeltype>&T)
  93. {
  94. if(LeftChildB(n,T)>0) DeleteB(LeftChildB(n,T),T);
  95. if(RightChildB(n,T)>0) DeleteB(RightChildB(n,T),T);
  96. T.elements[n].used=false;
  97. }
  98.  
  99.  
  100. };
  101. #endif

Report this snippet  

You need to login to post a comment.