Шаблонный класс Бинарное дерево полная реализация с различными методами!
/*
Athor Igor Dombrovsky
Realization binary tree
*/
#include <iostream>
#include <time.h>
#include <stdlib.h>
using namespace std;
#define TEXT_COLOR_CMD_WINDOWS system("color 0A");
#define STOP_CMD_WINDOWS system("pause");
template<class T>
class Tree
{
public:
Tree();
~Tree();
void addElement(T data);
void showMinMax(Tree * root);
void showMaxMin(Tree * root);
int searchElement(Tree * root, T element);
T getMax();
T getMin();
void clearTree();
void deleteElement(Tree * root, T element);
void deleteBranchLeft(Tree * root);
void deleteBranchRight(Tree * root);
public:
Tree * root;
private:
Tree * right;
Tree * left;
Tree * max;
Tree * min;
T data;
void searchPlace(Tree * root, Tree * temp, T data);
};
template<class T>
Tree<T>::Tree() : root(NULL), right(NULL), left(NULL), min(NULL), max(NULL) // CONSTRUCTOR
{
//DEFAULT
}
template<class T>
Tree<T>::~Tree() // DESTRUCTOR
{
root = NULL;
right = NULL;
left = NULL;
min = NULL;
max = NULL;
}
template<class T>
void Tree<T>::addElement(T data) // AD ELEMENT AT TREE
{
Tree * temp = new Tree;
temp->data = data;
temp->left = NULL;
temp->right = NULL;
if (root == NULL)
{
root = temp;
min = temp;
max = temp;
}
else
{
if (min->data > temp->data) // MAX ELEMENT
min = temp;
if (max->data < temp->data) // MIN ELEMENT
max = temp;
searchPlace(root, temp, data); // SEARCH PLACE IN TREE
}
}
template<class T>
void Tree<T>::searchPlace(Tree<T> * root, Tree<T> * temp, T data) // PRIVATE RECURSION SEARCH PLACE IN TREE
{
Tree * tmp = root;
if (tmp->data < data && tmp->right == NULL) tmp->right = temp;
else if (tmp->data > data && tmp->left == NULL) tmp->left = temp;
else
{
if (tmp->data < data) searchPlace(tmp->right, temp, data); // RECURSION CALL
if (tmp->data > data) searchPlace(tmp->left, temp, data); // RECURSION CALL
}
}
template<class T>
void Tree<T>::showMinMax(Tree * root) // SHOW MIN MAX
{
if (root != NULL && this->root != NULL)
{
showMinMax(root->left);
cout << "==>> Address = " << root << " Data = " << root->data << "\n";
showMinMax(root->right);
}
}
template<class T>
void Tree<T>::showMaxMin(Tree * root) // SHOW MAX MIN
{
if (root != NULL && this->root != NULL)
{
showMaxMin(root->right);
cout << "==>> Address = " << root << " Data = " << root->data << "\n";
showMaxMin(root->left);
}
}
template<class T>
int Tree<T>::searchElement(Tree<T>* root, T element) // SEARCH ELEMENT IN TREE RETURN ONE OR ZERO
{
if (this->root != NULL)
{
if (root->data > element)
{
if (root->data == element) return 1;
if (root->left != NULL) searchElement(root->left, element);
else return 0;
}
else
{
if (root->data == element) return 1;
if (root->right != NULL) searchElement(root->right, element);
else return 0;
}
}
}
template<class T>
T Tree<T>::getMax() // GET MAX ELEMENT
{
return this->max->data;
}
template<class T>
T Tree<T>::getMin() // GET MIN ELEMENT
{
return this->min->data;
}
template<class T>
void Tree<T>::clearTree() // CLEAR TREE
{
if (this->root != NULL)
{
deleteBranchLeft(this->root);
deleteBranchRight(this->root);
if (this->root->right == NULL && this->root->left == NULL)
{
delete this->root;
this->root = NULL;
}
}
}
template<class T>
void Tree<T>::deleteElement(Tree * root, T element) // DELETE ELEMENT
{
Tree * parent;
if (this->root != NULL)
{
if (root->data > element)
{
if (root->data == element) // WORKS WITH LEFT IN TREE
{
}
if (root->left != NULL)
{
parent = root;
deleteElement(root->left, element);
}
}
else
{
if (root->data == element) // WORKS WITH LEFT IN TREE
{
}
if (root->right != NULL)
{
parent = root;
deleteElement(root->right, element);
}
}
}
}
template<class T>
void Tree<T>::deleteBranchLeft(Tree * root) // DELETE BRANCH LEFT
{
if (root->left != NULL && this->root != NULL)
{
deleteBranchLeft(root->left);
delete root->left;
root->left = NULL;
}
}
template<class T>
void Tree<T>::deleteBranchRight(Tree * root) // DELETE BRANCH RIGHT
{
if (root->right != NULL && this->root != NULL)
{
deleteBranchRight(root->right);
delete root->right;
root->right = NULL;
}
}
int main() { // MAIN
TEXT_COLOR_CMD_WINDOWS
Tree<int> t; // TREE
//--------------------------------------------------------------
t.addElement(5);
t.addElement(10);
t.addElement(8);
t.addElement(6);
t.addElement(4);
t.addElement(3);
t.addElement(7);
t.addElement(9);
t.addElement(1);
t.addElement(2);
//--------------------------------------------------------------
cout << "//****************************************" << endl;
cout << "// SHOW MIN MAX" << endl;
cout << "//****************************************" << endl;
t.showMinMax(t.root);
cout << endl;
//--------------------------------------------------------------
cout << "//****************************************" << endl;
cout << "// SHOW MAX MIN" << endl;
cout << "//****************************************" << endl;
t.showMaxMin(t.root);
cout << endl;
//--------------------------------------------------------------
cout << "//****************************************" << endl;
int found = 0, key = 25;
found = t.searchElement(t.root, key);
cout << "Key search = " << key << endl;
cout << "Found = " << found << endl;
cout << endl;
//--------------------------------------------------------------
cout << "//****************************************" << endl;
cout << "// SHOW Max element " << endl;
cout << "//****************************************" << endl;
cout << t.getMax() << endl;
cout << endl;
//--------------------------------------------------------------
cout << "//****************************************" << endl;
cout << "// SHOW Min element " << endl;
cout << "//****************************************" << endl;
cout << t.getMin() << endl;
cout << endl;
//--------------------------------------------------------------
cout << "//****************************************" << endl;
cout << "// DELETE BRANCH LEFT " << endl;
cout << "//****************************************" << endl;
t.deleteBranchLeft(t.root);
t.showMaxMin(t.root);
cout << endl;
t.showMinMax(t.root);
cout << endl;
//--------------------------------------------------------------
cout << "//****************************************" << endl;
cout << "// DELETE BRANCH RIGHT " << endl;
cout << "//****************************************" << endl;
t.deleteBranchRight(t.root);
t.showMaxMin(t.root);
cout << endl;
t.showMinMax(t.root);
cout << endl;
//--------------------------------------------------------------
cout << "//****************************************" << endl;
cout << "// clear Tree " << endl;
cout << "//****************************************" << endl;
t.clearTree();
t.showMaxMin(t.root);
cout << endl;
t.showMinMax(t.root);
cout << endl;
//--------------------------------------------------------------
cout << "//****************************************" << endl;
cout << "// END PROGRAM " << endl;
cout << "//****************************************" << endl;
STOP_CMD_WINDOWS
return 0;
}
