Last active
October 24, 2018 16:53
-
-
Save pasha-pivo/97f90badf96b3e8124e290e8ae82e57f to your computer and use it in GitHub Desktop.
binary tree example
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment