Answer to Question #288891 in C++ for tatheer

Question

Create a Binary Search Tree of user defined values. Keep asking user values until he/she enters any negative number. Now display the elements of the tree in In-order, Post-order and Pre-order form. Your program should also contain a search function which should find a particular number entered by user. Search function should be recursive.

Answer 1

#include<iostream>
#include<vector>

using namespace std;


struct Node
{
	int data;
	struct Node *right;
	struct Node *left;
	Node(int _data) :data(_data), left(NULL), right(NULL) {}
};


class BST
{
public:
	struct Node* BSTInsert(int value, Node* p)
	{
		if (p == NULL)
		{
			p = new Node(value);
		}
		else if (value<p->data)
		{
			p->left = BSTInsert(value, p->left);
		}
		else if (value>p->data)
		{
			p->right = BSTInsert(value, p->right);
		}
		return p;
	}


	void Preorder(struct Node *p)
	{
		if (p != NULL)
		{
			cout << p->data << " ";
			Preorder(p->left);
			Preorder(p->right);
		}
	}


	void Postorder(struct Node *p)
	{
		if (p != NULL)
		{			
			Postorder(p->left);
			Postorder(p->right);
			cout << p->data << " ";
		}
	}


	void Inorder(struct Node *p)
	{
		if (p != NULL)
		{
			Postorder(p->left);
			cout << p->data << " ";
			Postorder(p->right);
		}
	}


	struct Node* Search(int value, struct Node* p)
	{
		if (p == NULL || p->data == value)
			return p;
		if (p->data < value)
			return Search(value, p->right);
		return Search(value, p->left);
	}
};




int main()
{
	BST bs;
	int num;
	Node *root = new Node(1);
	do
	{
		cout << "Please, enter a value (-value - exit program):\n";
		cin >> num;
		if (num < 0)break;
		bs.BSTInsert(num, root);
	} while (true);
	cout << "\nInorder:";
	bs.Inorder(root);
	cout << "\nPostorder";
	bs.Postorder(root);
	cout << "\nPreorder";
	bs.Preorder(root);
	int fnum;
	cout << "\nPlease, enter a value to find:\n";
	cin >> fnum;
	if (bs.Search(fnum, root) != NULL)
		cout << "Found";
	else
		cout << "Not Found";


}