fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3.  
  4. //примитивный итератор для симметричного обхода двоичного дерева поиска
  5. template<typename N, typename T>
  6. struct itraverse {
  7. private:
  8. 	N* p;
  9. public:
  10. 	itraverse(void):p(NULL){}
  11. 	itraverse(N* _p):p(_p){}
  12. public:
  13. 	bool operator != (N* _p) const { return (p != _p); }
  14. 	bool operator == (N* _p) const { return (p == _p); }
  15.  
  16. 	T& operator *(void) const { return p->val; }
  17. 	T& operator *(void) { return p->val; }
  18.  
  19. 	itraverse& operator ++ (void){
  20. 		N* t;
  21. 		if(p != NULL){
  22. 			if(p->right == NULL){
  23. 				t = p->parent;
  24. 				while((t != NULL) && (p == t->right)){
  25. 					p = t;
  26. 					t = t->parent;
  27. 				}
  28. 			} else {
  29. 				t = p->right;
  30. 				while(t->left != NULL)
  31. 					t = t->left;
  32. 			}
  33. 			p = t;
  34. 		}
  35. 		return *this;
  36. 	}
  37.  
  38. 	itraverse operator ++ (int){
  39. 		itraverse t(*this);
  40. 		++*this;
  41. 		return t;
  42. 	}
  43. };
  44.  
  45.  
  46. //двоичное дерево поиска
  47. template<typename T>
  48. class bstree {
  49. 	struct node {
  50. 		T     val;
  51. 		node* left;
  52. 		node* right;
  53. 		node* parent;
  54. 	};
  55. private:
  56. 	node*  tr;
  57. 	size_t n;
  58. public:
  59. 	typedef itraverse<node, T> traverse;
  60.  
  61. 	bstree(void):tr(NULL), n(0){}
  62. 	bstree(const bstree&);
  63. 	~bstree(){
  64. 		this->clear();
  65. 	}
  66.  
  67. public:
  68.  
  69. 	//вставка
  70. 	bool insert(const T& val){
  71. 		node* p, *t, **r = &tr;
  72.  
  73. 		p = t = tr;
  74. 		while(p != NULL){
  75. 			t = p;
  76. 			if(val < p->val){
  77. 				r = &p->left;
  78. 				p =  p->left;
  79. 			} else { 
  80. 				if(val == p->val)
  81. 					return false;
  82. 				r = &p->right;
  83. 				p = p->right;
  84. 			}
  85. 		}
  86.  
  87. 		p = new (std::nothrow) node();
  88. 		if(p != NULL){
  89. 			p->left   = p->right = NULL;
  90. 			p->parent = t;
  91. 			p->val    = val;
  92. 			*r = p;
  93. 			++n;
  94. 		}
  95. 		return (p != NULL);
  96. 	}
  97.  
  98. 	//удаление
  99. 	void remove(const T& val){
  100. 		node* t1, *t2, *p = tr;
  101.  
  102. 		while(p != NULL){
  103. 			if(val < p->val)
  104. 				p = p->left;
  105. 			else {
  106. 				if(val == p->val)
  107. 					break;
  108. 				p = p->right;
  109. 			}
  110. 		}
  111.  
  112. 		if(p == NULL)
  113. 			return;
  114.  
  115. 		if((p->left == NULL) || (p->right == NULL))
  116. 			t1 = p;
  117. 		else {
  118. 			t1 = p->right; 
  119. 			while(t1->left != NULL)
  120. 				t1 = t1->left;
  121. 		}
  122.  
  123. 		t2 = (t1->left == NULL) ?  t1->right : t1->left;
  124. 		if(t2 != NULL)
  125. 			t2->parent = t1->parent;
  126.  
  127. 		if(t1->parent == NULL)
  128. 			tr = t2;
  129. 		else if(t1 == t1->parent->left)
  130. 			t1->parent->left  = t2;
  131. 		else
  132. 			t1->parent->right = t2;
  133.  
  134. 		if(t1 != p)
  135. 			p->val = t1->val;
  136.  
  137. 		delete t1;
  138. 		--n;
  139. 	}
  140.  
  141. 	//начало для прохода
  142. 	node* begin(void){
  143. 		node* p = tr;
  144. 		if(p != NULL){
  145. 			while(p->left != NULL)
  146. 				p = p->left;
  147. 		}
  148. 		return p;
  149. 	}
  150.  
  151. 	//кол-во элементов
  152. 	size_t size(void) const {
  153. 		return n;
  154. 	}
  155.  
  156. 	//удаление всего дерева
  157. 	void clear(void){
  158. 		_clear(tr);
  159. 		tr = NULL;
  160. 		n  = 0;
  161. 	}
  162.  
  163. private:
  164.  
  165. 	void _clear(node* p){
  166. 		if(p != NULL){
  167. 			if(p->left != NULL)
  168. 				_clear(p->left);
  169. 			if(p->right != NULL)
  170. 				_clear(p->right);
  171. 			delete p;
  172. 		}
  173. 	}
  174. };
  175.  
  176.  
  177. int main(void){
  178. 	bstree<std::string> tr;
  179.  
  180. 	tr.insert("for");
  181. 	tr.insert("case");
  182. 	tr.insert("while");
  183. 	tr.insert("class");
  184. 	tr.insert("protected");
  185. 	tr.insert("virtual");
  186. 	tr.insert("public");
  187. 	tr.insert("private");
  188. 	tr.insert("do");
  189. 	tr.insert("template");
  190. 	tr.insert("const");
  191. 	tr.insert("if");
  192. 	tr.insert("int");
  193.  
  194. 	bstree<std::string>::traverse p = tr.begin();
  195. 	while(p != NULL){
  196. 		std::cout << *p << std::endl;
  197. 		++p;
  198. 	}
  199. 	tr.clear();
  200. 	return 0;
  201. }
  202.  
  203.  
  204.  
Success #stdin #stdout 0s 3464KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
case
class
const
do
for
if
int
private
protected
public
template
virtual
while
https://ideone.com/Q0EEtx
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!