binary tree example

tree.cpp

#include <iostream>
using namespace std;

/*
 * класс ноды дерева
 */
template <class T>
struct bool_node {
	bool_node<T>* less;
	bool_node<T>* more;
	T* value;

	bool_node () {}
	bool_node (T aValue) : less(NULL), more(NULL), value(new T(aValue)) {}
	virtual ~bool_node () {
		//~ this->remove(); // Деструктор пока не получился. Надо думать. Пока что с утечками.
		delete value;
	}
	
	void remove () {            // Проблемная функция
		if (more) {
			more->remove();
			delete more;
		}
		
		if (less) {
			less->remove();
			delete less;
		}
	}
	
	bool operator < (const bool_node<T>& right) const {
		return *value < *(right.value);
	}
	
	bool operator == (const bool_node<T>& right) const {
		return *value == *(right.value);
	}
};

/*
 * класс самого дерева
 */
template <class T>
class bool_tree {
	private:
		bool_node<T>* top;
		int _depth; ////////////////////////////////////////////
		
	public:
		bool_tree () : top(NULL), _depth(0) {}
	
		virtual ~bool_tree () {
			top->remove();
			delete top;
		}
	
		void insert (T aValue) {
			bool_node<T>* in;
			bool_node<T>* tmp;
			int tmp_depth; /////////////////////////////////////
			
			if (!top) {
				top = new bool_node<T>(aValue);
				++_depth; //////////////////////////////////////
				return;
			}

			tmp_depth = _depth; ////////////////////////////
			in = new bool_node<T>(aValue);
			tmp = top;
			
			while (true) {
				if (*in < *tmp) {
					if (!tmp->less) {
						if (!tmp->more and !--tmp_depth) ++_depth; ///////////////
						tmp->less = in;
						break;
					}
					tmp = tmp->less;
					--tmp_depth; ///////////////////////////////////////////
				} else {
					if (!tmp->more) {
						if (!tmp->less and !--tmp_depth) ++_depth; ////////////////
						tmp->more = in;
						break;
					}
					tmp = tmp->more;
					--tmp_depth; ///////////////////////////////////////////
				}
			}
		}
		
		bool find (T aValue) {
			bool_node<T> in = bool_node<T> (aValue);
			bool_node<T>* tmp = top;
			while (true) {
				if (in == *tmp) {
					return true;
				} else if (in < *tmp) {
					if (!tmp->less) {
						return false;
					}
					tmp = tmp->less;
				} else {
					if (!tmp->more) {
						return false;
					}
					tmp = tmp->more;
				}
			}
		}

		int depth () const {
			return _depth;
		}
};

int main(int argc, char** argv)
{
	bool_tree<int> arr;
	int match = 1;
	int to_add;

	arr.insert(10);
	arr.insert(1);
	arr.insert(0);
	arr.insert(100);
	arr.insert(15);
	arr.insert(12);
	arr.insert(8);

	while (true) {
		cout << "Number to add: "; cin >> to_add;
		if (!to_add) break;
		arr.insert(to_add);
	} 

	cout << "Enter nubers to check they exist in structure." << endl; 
	while (match) {
		cout << "Number: "; cin >> match;
		if (arr.find(match)) {
			cout << "Number exists" << endl;
		} else {
			cout << "Number does not exist" << endl;
		}
	}

	cout << "Structure depth is " << arr.depth() << endl;

	/*
	 * Здесь поиск утечек и причины SIGSEGV при вызове bool_node::remove();
	 */
	//~ bool_node<int>* n = new bool_node<int> (10);

	//~ n->more = new bool_node<int> (11);
	//~ n->more->more = new bool_node<int> (13);
	//~ n->less = new bool_node<int> (9);

	//~ delete n;
	
	return 0;
}