Binary Search Tree

[usama shahid]

#include <iostream>
#include <iomanip>
using namespace std;
class TNode
{
	int data;
	TNode *left, *right;
public:
	TNode(int Data = 0, TNode *Left = NULL, TNode *Right = NULL) :data(Data), left(Left), right(Right)
	{
	}
	friend class BinarySearchTree;
};
class BinarySearchTree
{
	TNode *root;
	void insert(int & x, TNode *&t)
	{
		if (t == nullptr)
		{
			t = new TNode{ x, nullptr, nullptr };
		}
		else if (x < t->data)
		{
			insert(x, t->left);
		}
		else if (t->data < x)
		{
			insert(x, t->right);
		}
		else
			;
	}
	bool Search(int &x, TNode *&t)
	{
		if (t == nullptr)
			return false;
		else if (x < t->data)
			return Search(x, t->left);
		else if (t->data < x)
			return Search(x, t->right);
		else
			return true;
	}
	void remove(int & x, TNode *&t)
	{
		if (t == nullptr)
			return;
		if (x < t->data)
		{
			remove(x, t->left);
		}
		else if (t->data < x)
		{
			remove(x, t->right);
		}
		else if (t->left != nullptr && t->right != nullptr)
		{
			t->data = findMin(t->right)->data;
			remove(t->data, t->right);
		}
		else
		{
			TNode *oldNode = t;
			t = (t->left != nullptr) ? t->left : t->right;
			delete oldNode;
		}
	}
	void makeEmpty(TNode * & t)
	{
		if (t != nullptr)
		{
			makeEmpty(t->left);
			makeEmpty(t->right);
			delete t;
		}
		t = nullptr;
	}
	TNode * findMin(TNode *t)
	{
		if (t == nullptr)
			return nullptr;
		if (t->left == nullptr)
			return t;
		return findMin(t->left);
	}
	TNode * findMax(TNode *t)
	{
		if (t != nullptr)
		{
			while (t->right != nullptr)
				t = t->right;
		}
		return t;
	}
	void printTree(TNode *&t, int indent = 0)
	{
		if (t != NULL)
		{
			if (t->left) printTree(t->left, indent + 4);
			if (indent)
			{
				std::cout << std::setw(indent) << ' ';
			}
			cout << "     " << t->data << endl;
			if (t->right) printTree(t->right, indent + 4);
		}
	}
public:

	BinarySearchTree() :root(NULL)
	{
	}
	BinarySearchTree(int D)
	{
		root->data = D;
		root->left = NULL;
		root->right = NULL;
	}
	~BinarySearchTree()
	{
		makeEmpty(root);
	}
	void insert(int d)
	{
		insert(d, root);
	}
	bool Search(int d)
	{
		return Search(d, root);
	}
	void remove(int & x)
	{
		remove(x, root);
	}
	void findMin()
	{
		TNode *tmp = findMin(root);
		if (tmp == NULL)
		{
			cout << "Tree Is Empty " << endl;
		}
		else
		{
			cout << "the min value is : " << tmp->data << endl;
		}
	}
	void findMax()
	{
		TNode *tmp = findMax(root);
		if (tmp == NULL)
		{
			cout << "Tree Is Empty " << endl;
		}
		else
		{
			cout << "the mAx value is : " << tmp->data << endl;
		}
	}
	void makeEmpty()
	{
		makeEmpty(root);
	}
	void PrintTree()
	{
		if (root == NULL)
		{
			cout << "tree is empty " << endl;
			return;
		}
		printTree(root);
	}
};
int main()
{
	BinarySearchTree b;
	int ch, tmp, tmp1;
	while (1)
	{
		cout << endl << endl;
		cout << " Binary Search Tree Operations " << endl;
		cout << " ----------------------------- " << endl;
		cout << " 1. Insertion/Creation " << endl;
		cout << " 2. In-Order Traversal " << endl;
		cout << " 3. Find Max " << endl;
		cout << " 4. Find Min " << endl;
		cout << " 5. Removal " << endl;
		cout << " 6. search " << endl;
		cout << " 7. Clear the tree " << endl;
		cout << " 8. Exit " << endl;
		cout << " Enter your choice : ";
		cin >> ch;
		switch (ch)
		{
		case 1: cout << " Enter Number to be inserted : ";
			cin >> tmp;
			b.insert(tmp);
			break;
		case 2: cout << endl;
			cout << " In-Order Traversal " << endl;
			cout << " -------------------" << endl;
			b.PrintTree();
			break;
		case 3: cout << endl;
			cout << " MAX vALUE " << endl;
			cout << " -------------------" << endl;
			b.findMax();
			break;
		case 4: cout << endl;
			cout << " Min Value " << endl;
			cout << " --------------------" << endl;
			b.findMin();
			break;
		case 5: cout << " Enter data to be deleted : ";
			cin >> tmp1;
			b.remove(tmp1);
			break;
		case 6: cout << " Enter data to be searched : ";
			cin >> tmp1;
			cout<<b.Search(tmp1);
			break;
		case 7: cout << "Tree cleared ";
			b.makeEmpty();
		case 8:
			return 0;

		}
	}
	return 0;
}