trees.cpp

/******************************
  	   trees.cpp
    Auther:Syed Zain Ul hasan
  *****************************/

#include <iostream>
#include<stdlib.h>

using namespace std;


class Node
{
public:

	int data;

	Node *left;
	Node *right;

	Node(int d)
	{

		data = d;
		left = NULL;
		right = NULL;
	}
};


class BST
{
private:
	Node *root;

	void insert(int d, Node *aNode);
	Node *search(int d, Node *aNode);

	void inOrder(Node *aNode);
	void preOrder(Node *aNode);
	void postOrder(Node *aNode);


public:

	BST();

	void insert(int d);
	Node *search(int d);

	void inOrder();
	void preOrder();
	void postOrder();


};

//////////////////////////////////////////////////////////////

BST ::BST()
{

	root = NULL;
}
/////////////////////////////////////////////////////////

void BST ::insert(int d, Node *aNode)
{
	if(d < aNode->data)
	{

		if(aNode->left != NULL)
		{

			insert(d, aNode->left);
		}
		else
		{

			aNode->left = new Node(d);
			aNode->left->left = NULL;
			aNode->left->right = NULL;
		}



	}

	else if(d > aNode->data)
	{

		if(aNode->right != NULL)
		{
			insert(d, aNode->right);

		}

		else
		{
			aNode->right = new Node(d);

			aNode->right->right = NULL;
			aNode->right->left = NULL;
		}

	}

	else
	{
		aNode->right = new Node(d);

		aNode->right->right = NULL;
		aNode->right->left = NULL;


	}

}
/////////////////////////////////////////////////

void BST ::insert(int d)
{

	if(root != NULL)
	{

		insert(d, root);
	}

	else
	{

		root = new Node(d);

		root->left = NULL;
		root->right = NULL;
	}

}
/////////////////////////////////

Node* BST ::search(int d, Node *aNode)
{

	if(d == aNode->data)
	{
		return aNode;
	}

	if(d < aNode->data)
	{

		return search(d, aNode->left);
	}

	if(d > aNode->data)
	{

		return search(d, aNode->right);

	}
	else
	{
		return NULL;
	}
}
/////////////////////////////////

Node* BST ::search(int d)
{

	return search(d, root);

}
/////////////////////////////////

void BST::inOrder(Node *aNode)
{

	if(aNode != NULL)
	{

		inOrder(aNode->left);
		cout << aNode->data << " ";
		inOrder(aNode->right);
	}
}
////////////////////////////////

void BST::preOrder(Node *aNode)
{


	if(aNode != NULL)
	{

		cout << aNode->data << " ";
		inOrder(aNode->left);
		inOrder(aNode->right);
	}
}

///////////////////////////////////
void BST::postOrder(Node *aNode)
{



	if(aNode != NULL)
	{

		inOrder(aNode->left);
		inOrder(aNode->right);
		cout << aNode->data << " ";
	}
}
/////////////////////////////////

void BST::inOrder()
{

	inOrder(root);
}
/////////////////////////
void BST::preOrder()
{

	preOrder(root);
}
/////////////////////////

void BST::postOrder()
{

	postOrder(root);
}


/////////////////////////////////
int main(int argc, char** argv)
{
	BST *b = new BST;
	b->insert(5);
	b->insert(7);
	b->insert(4);
	b->insert(9);

	b->insert(10);
	Node *fount = b->search(10);
	cout << "Found: " << fount->data << endl;

	cout << "Pre Order: ";
	b->preOrder();
	cout << endl;
	cout << "In Order: ";
	b->inOrder();
	cout << endl;
	cout << "Post order: ";
	b->postOrder();
	cout << endl;



	system("pause");

	return 0;
}