Answer to Question #288892 in C++ for tatheer

Question

Implement a C++ program to store Strings in Binary Search tree. Your program should have following functions:

 Insert

 Display

 Search

Answer 1

#include<iostream>
#include<string>

using namespace std;

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

class BST
{
public:
	//Function for insertion new node to the BST
	struct Node* Insert(string value, struct Node *p)
	{
		if(p==NULL)
		{
			p=new Node(value);
		}
		else if(value.compare(p->data)<0)
		{
			p->left=Insert(value,p->left);
		}
		else if(value.compare(p->data)>0)
		{
			p->right=Insert(value,p->right);
		}
		return p;		
	}
	
	//Search function
	struct Node* Search(string value, struct Node *p)
	{
		if(p==NULL||p->data==value)
			return p;
		if(p->data.compare(value)<0)
			return Search(value,p->right);
		return Search(value,p->left);
	}
	
	//Display function
	void Display(struct Node *p)
	{
		if(p==NULL)return;
		cout<<p->data<<" ";
		Display(p->left);
		Display(p->right);
	}
};

int main()
{
	Node *root=new Node("apple");
	BST b;
	b.Insert("pear",root);
	b.Insert("plum",root);
	b.Insert("banana",root);
	b.Insert("orange",root);
	b.Insert("ananas",root);
	b.Insert("watermelon",root);
	b.Display(root);
	cout<<endl;
	string srch="orange";
	cout<<srch;
	if(b.Search(srch,root)!=NULL)
		cout<<" Found\n";
	else
		cout<<" Not found\n";
	
	srch="meal";
	cout<<srch;
	if(b.Search(srch,root)!=NULL)
		cout<<" Found\n";
	else
		cout<<" Not found\n";
	
	
}