BinaryTreeSearch.cpp

#include<iostream>
using namespace std;

//==================================================================
__interface ATree 
{
public:
#define NULL_(p) (p == NULL ? 0:p->info)
	void virtual insert(int) = 0;
	void virtual delete_nod() = 0;
	void virtual inorder() = 0;
	void virtual preorder() = 0;
	void virtual postorder() = 0;
	bool virtual search(int) = 0;
	void virtual show_tree() = 0;
	void virtual delete_tree() = 0;
};

//==================================================================
class BinaryTree : public ATree
{
	typedef struct nod
	{
		int info;
		nod *left, *right;
	}Tree;
	Tree *root;
	int ok;
public:
	BinaryTree() { root = NULL; }
	void delete_nod();
	void insert(int);
	void inorder();
	void postorder();
	void preorder();
	bool search(int);
	void show_tree();
	void delete_tree();
private:
	void delete_nod(Tree*);
	Tree* search(Tree*, int);
	void insert(Tree *, int);
	void inorder(Tree *);
	void postorder(Tree *);
	void preorder(Tree *);
	void delete_tree(Tree *);
};

void BinaryTree::delete_tree()
{
	delete_tree(root);
}
void BinaryTree::delete_tree(Tree *leaf)
{
	if (leaf != NULL)
	{
		delete_nod(leaf->left);
		delete_nod(leaf->right);

		delete leaf;
	}
	if (root)
		root = NULL;
}
void BinaryTree::show_tree()
{
	Tree * p = root;
	int choose;
	while (p)
	{
		cout << "Root is: " << p->info << endl;
		cout << "Childrens are: " << NULL_(p->left) << " " << NULL_(p->right) << endl;
		cout << " Left or Right (1/2): "; cin >> choose;
		if (choose == 1)
			p = p->left;
		else
			p = p->right;
	}
}
void BinaryTree::delete_nod(Tree* leaf)
{
	ok = 1;
	if (leaf->left != NULL && leaf->right != NULL)
	{
		delete_nod(leaf->right);
		if (ok)
		{
			delete leaf->right;
			leaf->right = NULL;
			ok = 0;
		}
	}
	else if (leaf->left)
	{
		delete_nod(leaf->left);
		if (ok)
		{
			delete leaf->left;
			leaf->left = NULL;
			ok = 0;
		}
	}
	
}
void BinaryTree::delete_nod()
{
	delete_nod(root);
}
BinaryTree::Tree* BinaryTree::search(Tree* leaf, int key)
{
	if (leaf != NULL)
	{
		if (key == leaf->info)
			return leaf;
		if (leaf->left)
			return search(leaf->left,key);
		else
			return search(leaf->right,key);
	}
	else return NULL;
}
bool BinaryTree::search(int key)
{
	Tree * res = search(root, key);
	if (res)
		return true;
	else return false;
}
void BinaryTree::inorder(Tree *leaf)
{
	if (leaf)
	{
		inorder(leaf->left);
		cout << leaf->info << " ";
		inorder(leaf->right);
	}
}
void BinaryTree::postorder(Tree *leaf)
{
	if (leaf)
	{
		postorder(leaf->left);
		postorder(leaf->right);
		cout << leaf->info << " ";
	}
}
void BinaryTree::preorder(Tree *leaf)
{
	if (leaf)
	{
		cout << leaf->info << " ";
		preorder(leaf->left);
		preorder(leaf->right);
	}
}
void BinaryTree::preorder()
{
	Tree *p = root;
	preorder(p);
}
void BinaryTree::postorder()
{
	Tree *p = root;
	postorder(p);
}
void BinaryTree::inorder()
{
	Tree *p = root;
	inorder(p);
}
void BinaryTree::insert(int val)
{
	if (root == NULL)
	{
		root = new Tree;
		root->info = val;
		root->left = NULL;
		root->right = NULL;
	}
	else
	{
		insert(root, val);
	}
}
void BinaryTree::insert(Tree *leaf, int val)
{
	if (leaf->left == NULL && leaf->right == NULL) //insert in left leaf
	{
		Tree *p = new Tree;
		p->info = val;
		p->left = NULL;
		p->right = NULL;
		leaf->left = p;
	}
	else if (leaf->right == NULL) //insert in right leaf
	{

		Tree *p = new Tree;
		p->info = val;
		p->left = NULL;
		p->right = NULL;
		leaf->right = p;
	}
	else //search leaf null for insert
	{
		if (leaf->left && leaf->right)
			insert(leaf->left, val);
		else if (leaf->left)
			insert(leaf->right, val);
		else
			cout << "eroare" << endl;
	}
}

//==================================================================
class BinarySearchTree
{
	struct node
	{
		int key_value;
		node *left;
		node *right;
	};
public:
	BinarySearchTree();
	~BinarySearchTree();

	void insert(int key);
	bool search(int key);
	void destroy_tree();
	void delete_key(int key);
	int findMax();
	bool isEmpty();
	int get_left();
	int get_right();
	void show_tree();
private:
	node* delete_key(node*leaf, int key);
	void destroy_tree(node *leaf);
	void insert(int key, node *leaf);
	node *search(int key, node *leaf);
	node *findMin(node *leaf);
	node * get_left(node*);
	node * get_right(node*);

	node *root;
};

void BinarySearchTree::show_tree()
{
#define NULL_(p) (p == NULL ? 0:p->key_value)
	node * p = root;
	int choose;
	while (p)
	{
		cout << "Root is: " << p->key_value << endl;
		cout << "Childrens are: "<< NULL_(p->left) << " " << NULL_(p->right) << endl;
		cout << " Left or Right (1/2): ";cin >> choose;
		if (choose == 1)
			p = p->left;
		else
			p = p->right;
	}
}
int BinarySearchTree::get_left()
{
	node *p = get_left(root);
	if (p != NULL)
		return p->key_value;
	else return -1;
}
int BinarySearchTree::get_right()
{
	node *p = get_right(root);
	if(p!=NULL)
		return p->key_value;
	else return -1;
}
BinarySearchTree::node* BinarySearchTree::get_left(node *leaf)
{
	if (leaf->left)
		return leaf->left;
	else return NULL;
}
BinarySearchTree::node* BinarySearchTree::get_right(node *leaf)
{
	if (leaf->right)
		return leaf->right;
	else return NULL;
}
bool BinarySearchTree::isEmpty()
{
	if (root == NULL)
		return true;
	else
		return false;
}
BinarySearchTree::node* BinarySearchTree::findMin(node *leaf)
{
	node *p = root;
	while (p->left)
		p = p->left;
	return p;
}
BinarySearchTree::node* BinarySearchTree::delete_key(node *leaf, int key)
{
	if (leaf == NULL)
		return leaf;
	else if (key < leaf->key_value)
		leaf->left = delete_key(leaf->left, key);
	else if (key > leaf->key_value)
		leaf->right = delete_key(leaf->right, key);
	else
	{
		//case 1 no child
		if (leaf->left == NULL && leaf->right == NULL)
		{
			delete leaf;
			leaf = NULL;
		}//case 2 one child
		else if (leaf->left == NULL)
		{
			node * temp = leaf;
			leaf = leaf->right;
			delete temp;
		}
		else if (leaf->right == NULL)
		{
			node * temp = leaf;
			leaf = leaf->left;
			delete temp;
		}
		else // case 3 two child
		{
			node* temp = findMin(leaf->right);
			leaf->key_value = temp->key_value;
			leaf->right = delete_key(root->right, temp->key_value);
		}
	}
	return leaf;
}
void BinarySearchTree::delete_key(int key)
{
	node *p = root;
	delete_key(p, key);
}
int BinarySearchTree::findMax()
{
	if (!isEmpty())
	{
		node *p = root;
		while (p->right)
			p = p->right;
		return p->key_value;
	}
	else return -1;
}
BinarySearchTree::~BinarySearchTree()
{
	destroy_tree();
	root = NULL;
}
BinarySearchTree::BinarySearchTree()
{
	root = NULL;
}
void BinarySearchTree::destroy_tree(node *leaf)
{
	if (leaf != NULL)
	{
		destroy_tree(leaf->left);
		destroy_tree(leaf->right);
		delete(leaf);
	}
}
void BinarySearchTree::insert(int key, node *leaf)
{
	if (key< leaf->key_value)
	{
		if (leaf->left != NULL)
			insert(key, leaf->left); //merge pana in frunzele subarborelui pentru inserare
		else
		{
			leaf->left = new node;
			leaf->left->key_value = key;
			leaf->left->left = NULL;    //Sets the left child of the child node to null
			leaf->left->right = NULL;   //Sets the right child of the child node to null
		}
	}
	else if (key >= leaf->key_value)
	{
		if (leaf->right != NULL)
			insert(key, leaf->right);
		else
		{
			leaf->right = new node;
			leaf->right->key_value = key;
			leaf->right->left = NULL;  //Sets the left child of the child node to null
			leaf->right->right = NULL; //Sets the right child of the child node to null
		}
	}
}
BinarySearchTree::node *BinarySearchTree::search(int key, node *leaf)
{
	if (leaf != NULL)
	{
		if (key == leaf->key_value)
			return leaf;
		if (key<leaf->key_value)
			return search(key, leaf->left);
		else
			return search(key, leaf->right);
	}
	else return NULL;
}
void BinarySearchTree::insert(int key)
{
	if (root != NULL)
		insert(key, root);
	else
	{
		root = new node;
		root->key_value = key;
		root->left = NULL;
		root->right = NULL;
	}
}
bool BinarySearchTree::search(int key)
{
	if (search(key, root))
		return true;
	else return false;
}
void BinarySearchTree::destroy_tree()
{
	destroy_tree(root);
}

//==================================================================


class AVL
{
	struct node
	{
		int element;
		node *left;
		node *right;
		int height;
	};
	typedef struct node *nodeptr;
	nodeptr root;//,flag;public:
public:
	AVL() { root = NULL; }
	int findmax();
	int findmin();
	void insert(int);
	void del(int);
	void find(int);
	void inorder();
	void preorder();
	void postorder();
	int bsheight();
	int nonodes(nodeptr);
	void Interface();
private:
	void insert(int, nodeptr &);
	void del(int, nodeptr &);
	int deletemin(nodeptr &);
	void find(int, nodeptr &);
	nodeptr findmin(nodeptr);
	nodeptr findmax(nodeptr);
	void makeempty(nodeptr &);
	void copy(nodeptr &, nodeptr &);
	nodeptr nodecopy(nodeptr &);
	void preorder(nodeptr);
	void inorder(nodeptr);
	void postorder(nodeptr);
	int bsheight(nodeptr);
	nodeptr srl(nodeptr &);
	nodeptr drl(nodeptr &);
	nodeptr srr(nodeptr &);
	nodeptr drr(nodeptr &);
	int max(int, int);

};

//===================================================
//--------------public method------------------------
//===================================================

// Inserting a node
void AVL::insert(int val)
{
	insert(val, root);
}
// Finding the Smallest
int AVL::findmin()
{
	nodeptr p = root, min;
	if (root != NULL)
	{
		min = findmin(p);
		return min->element;
	}
	return -1;
}
// Finding the Largest node
int AVL::findmax()
{
	nodeptr p = root, max;
	if (root != NULL)
	{
		max = findmax(p);
		return max->element;
	}
	return -1;
}
// Finding an element
void AVL::find(int val)
{
	find(val, root);
}
// Deleting a node
void AVL::del(int val)
{
	del(val, root);
}
//Preorder Printig
void AVL::preorder()
{
	preorder(root);
}
// Inorder Printing
void AVL::inorder()
{
	inorder(root);
}
// PostOrder Printing
void AVL::postorder()
{
	postorder(root);
}
// Height
int AVL::bsheight()
{
	int height = bsheight(root);
	return height;
}
//===================================================
//--------------private method ----------------------
//===================================================
// Inserting a node
void AVL::insert(int x, nodeptr &p)
{
	if (p == NULL)
	{
		p = new node;
		p->element = x;
		p->left = NULL;
		p->right = NULL;
		p->height = 0;
		if (p == NULL)
		{
			cout << "Out of Space\n" << endl;
		}
	}
	else
	{
		if (x<p->element)
		{
			insert(x, p->left);
			if ((bsheight(p->left) - bsheight(p->right)) == 2)
			{
				if (x < p->left->element)
				{
					p = srl(p);
				}
				else
				{
					p = drl(p);
				}
			}
		}
		else if (x>p->element)
		{
			insert(x, p->right);
			if ((bsheight(p->right) - bsheight(p->left)) == 2)
			{
				if (x > p->right->element)
				{
					p = srr(p);
				}
				else
				{
					p = drr(p);
				}
			}
		}
		else
		{
			cout << "Element Exists\n" << endl;
		}
	}
	int m, n, d;
	m = bsheight(p->left);
	n = bsheight(p->right);
	d = max(m, n);
	p->height = d + 1;
}
// Finding the Smallest
AVL::nodeptr AVL::findmin(nodeptr p)
{
	if (p == NULL)
	{
		cout << "The tree is empty\n" << endl;
		return p;
	}
	else
	{
		while (p->left != NULL)
		{
			p = p->left;
			//return p;
		}
		return p;
	}
}
// Finding the Largest node
AVL::nodeptr AVL::findmax(nodeptr p)
{
	if (p == NULL)
	{
		cout << "The tree is empty\n" << endl;
		return p;
	}
	else
	{
		while (p->right != NULL)
		{
			p = p->right;
			//return p;
		}
		return p;
	}
}
// Finding an element
void AVL::find(int x, nodeptr &p)
{
	if (p == NULL)
	{
		cout << "Sorry! element not found\n" << endl;
	}
	else
	{
		if (x < p->element)
		{
			find(x, p->left);
		}
		else
		{
			if (x>p->element)
			{
				find(x, p->right);
			}
			else
			{
				cout << "Element found!\n" << endl;
			}
		}
	}
}
// Copy a tree
void AVL::copy(nodeptr &p, nodeptr &p1)
{
	makeempty(p1);
	p1 = nodecopy(p);
}
// Make a tree empty
void AVL::makeempty(nodeptr &p)
{
	nodeptr d;
	if (p != NULL)
	{
		makeempty(p->left);
		makeempty(p->right);
		d = p;
		free(d);
		p = NULL;
	}
}
// Copy the nodes
AVL::nodeptr AVL::nodecopy(nodeptr &p)
{
	nodeptr temp;
	if (p == NULL)
	{
		return p;
	}
	else
	{
		temp = new node;
		temp->element = p->element;
		temp->left = nodecopy(p->left);
		temp->right = nodecopy(p->right);
		return temp;
	}
}
// Deleting a node
void AVL::del(int x, nodeptr &p)
{
	nodeptr d;
	if (p == NULL)
	{
		cout << "Sorry! element not found\n" << endl;
	}
	else if (x < p->element)
	{
		del(x, p->left);
	}
	else if (x > p->element)
	{
		del(x, p->right);
	}
	else if ((p->left == NULL) && (p->right == NULL))
	{
		d = p;
		delete(d);
		p = NULL;
		cout << "Element deleted successfully\n" << endl;
	}
	else if (p->left == NULL)
	{
		d = p;
		free(d);
		p = p->right;
		cout << "Element deleted successfully\n" << endl;
	}
	else if (p->right == NULL)
	{
		d = p;
		p = p->left;
		free(d);
		cout << "Element deleted successfully\n" << endl;
	}
	else
	{
		p->element = deletemin(p->right);
	}
}
//Preorder Printig
int AVL::deletemin(nodeptr &p)
{
	int c;
	cout << "inside deltemin\n" << endl;
	if (p->left == NULL)
	{
		c = p->element;
		p = p->right;
		return c;
	}
	else
	{
		c = deletemin(p->left);
		return c;
	}
}
void AVL::preorder(nodeptr p)
{
	if (p != NULL)
	{
		cout << p->element << "\t";
		preorder(p->left);
		preorder(p->right);
	}
}
// Inorder Printing
void AVL::inorder(nodeptr p)
{
	if (p != NULL)
	{
		inorder(p->left);
		cout << p->element << "\t";
		inorder(p->right);
	}
}
// PostOrder Printing
void AVL::postorder(nodeptr p)
{
	if (p != NULL)
	{
		postorder(p->left);
		postorder(p->right);
		cout << p->element << "\t";
	}
}
// For insert value ( echivalation tree )
AVL::nodeptr AVL::srl(nodeptr &p1)
{
	nodeptr p2;
	p2 = p1->left;
	p1->left = p2->right;
	p2->right = p1;
	p1->height = max(bsheight(p1->left), bsheight(p1->right)) + 1;
	p2->height = max(bsheight(p2->left), p1->height) + 1;
	return p2;
}
AVL::nodeptr AVL::srr(nodeptr &p1)
{
	nodeptr p2;
	p2 = p1->right;
	p1->right = p2->left;
	p2->left = p1;
	p1->height = max(bsheight(p1->left), bsheight(p1->right)) + 1;
	p2->height = max(p1->height, bsheight(p2->right)) + 1;
	return p2;
}
AVL::nodeptr AVL::drl(nodeptr &p1)
{
	p1->left = srr(p1->left);
	return srl(p1);
}
AVL::nodeptr AVL::drr(nodeptr &p1)
{
	p1->right = srl(p1->right);
	return srr(p1);
}
int AVL::max(int value1, int value2)
{
	return ((value1 > value2) ? value1 : value2);
}
int AVL::bsheight(nodeptr p)
{
	int t;
	if (p == NULL)
	{
		return -1;
	}
	else
	{
		t = p->height;
		return t;
	}
}
//Number of nods in tree
int AVL::nonodes(nodeptr p)
{
	int count = 0;
	if (p != NULL)
	{
		nonodes(p->left);
		nonodes(p->right);
		count++;
	}
	return count;
}
//Interface for use default AVL
void AVL::Interface()
{
	//clrscr();
	int a, choice, findele, delele, min, max;
	char ch = 'y';
	AVL tree;

	//system("clear");
	cout << "\n\t\t\t\tWELCOME TO AVL TREE" << endl;
	cout << "\t\t\t\t:::::::::::::::::::\n" << endl;

	do
	{
		cout << "\t\t:::::::::::::::::::::::::::::::::::::::::::::::::::" << endl;
		cout << "\t\t:::: Enter 1 to insert a new node               :::" << endl;
		cout << "\t\t:::: Enter 2 to find the minimum value          :::" << endl;
		cout << "\t\t:::: Enter 3 to find the max value              :::" << endl;
		cout << "\t\t:::: Enter 4 to search a value                  :::" << endl;
		cout << "\t\t:::: Enter 5 to delete a value                  :::" << endl;
		cout << "\t\t:::: Enter 6 to display Preorder                :::" << endl;
		cout << "\t\t:::: Enter 7 to display Inorder                 :::" << endl;
		cout << "\t\t:::: Enter 8 to display Postorder               :::" << endl;
		cout << "\t\t:::: Enter 9 to display the height of the tree  :::" << endl;
		cout << "\t\t:::: Enter 0 to exit                            :::" << endl;
		cout << "\t\t:::::::::::::::::::::::::::::::::::::::::::::::::::\n" << endl;

		cout << "\nEnter the choice: ";
		cin >> choice;

		switch (choice)
		{
		case 1:
			cout << "\n\t\tADDING NEW NODE" << endl;
			cout << "\t\t:::::::::::::\n" << endl;
			cout << "Enter a new value: ";
			cin >> a;
			tree.insert(a);
			cout << "\nThe new value have been added to your tree successfully\n" << endl;
			break;
		case 2:
			min = tree.findmin();
			cout << "\nThe minimum element in the tree is: " << min << endl;
			break;
		case 3:
			max = tree.findmax();
			cout << "\nThe maximum element in the tree is: " << max << endl;
			break;
		case 4:
			cout << "\nEnter node to search: ";
			cin >> findele;
			tree.find(findele);
			break;
		case 5:
			cout << "\nEnter node to delete: ";
			cin >> delele;
			tree.del(delele);
			tree.inorder();
			cout << endl;
			break;
		case 6:
			cout << "\n\t\tPRE-ORDER TRAVERSAL" << endl;
			tree.preorder();
			cout << endl;
			break;
		case 7:
			cout << "\n\t\tIN-ORDER TRAVERSAL" << endl;
			tree.inorder();
			cout << endl;
			break;
		case 8:
			cout << "\n\t\tPOST ORDER TRAVERSAL" << endl;
			tree.postorder();
			cout << endl;
			break;
		case 9:
			cout << "\n\t\tHEIGHT\n" << endl;
			cout << "The height of the tree is: " << tree.bsheight() << endl;

			break;
		case 0:
			cout << "\n\tThank your for using AVL tree program\n" << endl;
			break;
		default:
			cout << "Sorry! wrong input\n" << endl;
			break;
		}
		system("pause");
		system("cls");
	} while (choice != 0);
}



int main(void)
{
	
	BinaryTree a;
	a.insert(1);
	a.insert(2);
	a.insert(3);
	a.insert(4);
	a.insert(5);
	a.insert(6);
	a.delete_nod();
	a.delete_nod();
	a.inorder();
	//a.show_tree();


	system("pause");
	return 0;
}