Advanced Search

ADT Binary tree - array implementation header

/ Published in: C++
Save to your folder(s)
An C++ header using templates.
Array implementation of binary tree.

Expand | Embed | Plain Text

Copy this code and paste it in your HTML 
  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


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.