A Dictionary stores keywords & its meanings. Provide facility for adding new keywords, deleting keywords, updating values of any entry, assign a given tree into another tree (=). Provide facility to display whole data sorted in ascending/ Descending order. Also find how many maximum comparisons may require for finding any keyword. Use Binary Search Tree for implementation.

	/*
	* Dictionary.cpp
	*
	* Created on: Jan 20, 2019
	* Author: iamrohitsuthar
	*/
	#include<iostream>
	#include<string.h>
	const int MAX=30;
	using namespace std;
	class Node {
	string keyword;
	string mean;
	Node* left;
	Node* right;
	public:
	Node() {
	keyword="";
	mean="";
	left=NULL;
	right=NULL;
	}
	Node(string k,string m) {
	keyword=k;
	mean=m;
	left=NULL;
	right=NULL;
	}
	friend class Dictionary;
	};
	class stack {
	Node* item[MAX];
	int top;
	public:
	stack() {
	top=-1;
	}
	void push(Node* node) {
	if(isFull()) {
	cout<<"Stack is full"<<endl;
	}
	else {
	top++;
	item[top]=node;
	}
	}
	Node* topData() {
	return item[top];
	}
	Node* pop() { // @suppress("No return")
	if(isEmpty()) {
	cout<<"Stack is empty"<<endl;
	}
	else
	return item[top--];
	}
	int size() {
	return top+1;
	}
	int isEmpty() {
	if(top==-1)
	return 1;
	return 0;
	}
	int isFull() {
	if(top==MAX)
	return 1;
	return 0;
	}
	friend class Tree;
	};
	class Dictionary {
	Node* root;
	int counter=0;
	public:
	Dictionary() {
	root=NULL;
	}
	Node* getRoot() {
	return root;
	}
	void createTree(string keyword,string mean) {
	Node* p,*q;
	Node* temp=new Node(keyword,mean);
	if(root==NULL) {
	root=temp;
	}
	else {
	p=q=root;
	while(q!=NULL && q->keyword!=temp->keyword) {
	p=q;
	if(temp->keyword < p->keyword) {
	q=p->left;
	}
	else {
	q=p->right;
	}
	}
	if(temp->keyword < p->keyword )
	p->left=temp;
	else if(temp->keyword > p->keyword)
	p->right=temp;
	else
	cout<<"duplicate"<<endl;
	}
	}
	void inorder(Node* node) {
	if(node!=NULL) {
	inorder(node->left);
	cout<<node->keyword<<" : "<<node->mean<<endl;
	inorder(node->right);
	}
	}
	void desc(Node* node) {
	if(node!=NULL) {
	desc(node->right);
	cout<<node->keyword<<" : "<<node->mean<<endl;
	desc(node->left);
	}
	int search(Node* node,string data) {
	int c=0;
	while(node != NULL){
	c++;
	if(node->keyword == data) {
	cout<<"Maximum comparisons are: "<<c<<endl;
	return 1;
	}
	if(data < node->keyword) {
	node=node->left;
	}
	if(data > node->keyword) {
	node=node->right;
	}
	}
	return -1;
	}
	int height(Node* node) {
	if(node == NULL)
	return 0;
	else {
	int lh=height(node->left);
	int rh=height(node->right);
	if(lh > rh)
	return (lh+1);
	else
	return (rh+1);
	}
	}
	int printGivenLevel(Node* root, int level)
	{
	int temp=0,temp1=0;
	if (root == NULL)
	return 0;
	if (level == 1) {
	counter++;
	return 1;
	}
	else if (level > 1)
	{
	temp=printGivenLevel(root->left, level-1);
	temp1=printGivenLevel(root->right, level-1);
	}
	return temp+temp1;
	}
	float printLevelOrder(Node* root)
	{
	counter=0;
	int h = height(root);
	int i;
	float temp=0;
	for (i = 1; i <= h; i++) {
	int temp1 = printGivenLevel(root, i);
	temp+=i*temp1;
	}
	return temp;
	}
	float findAverage(Node* node) {
	float temp=printLevelOrder(node);
	return float(temp/counter);
	}
	void update(Node* node,string keyword) {
	string meaning;
	Node* temp=NULL;
	temp=findNode(node,keyword);
	if(temp != NULL) {
	cout<<"keyword found"<<endl;
	cout<<"Old Meaning is: "<<temp->mean<<endl;
	cout<<"Enter new Meaning: ";
	cin>>meaning;
	temp->mean=meaning;
	cout<<"keyword updated..."<<endl;
	}
	else
	cout<<"keyword not found"<<endl;
	}
	Node* findNode(Node* node,string keyword) { // @suppress("No return")
	if(node != NULL) {
	if(node->keyword==keyword) {
	return node;
	}
	if(node->keyword > keyword)
	return findNode(node->left,keyword);
	return findNode(node->right,keyword);
	}else {
	return NULL;
	}
	}
	void operator=(Dictionary &d) {
	Node* node=d.getRoot();
	if(node==NULL) return;
	stack s1;
	Node* temp=node;
	s1.push(temp);
	while(!s1.isEmpty() && s1.topData() != NULL) {
	temp=s1.pop();
	createTree(temp->keyword,temp->mean);
	if(temp->right)
	s1.push(temp->right);
	if(temp->left)
	s1.push(temp->left);
	}
	cout<<"Tree copied"<<endl;
	}
	//delete
	Node* getParent(Node* child) {
	Node* p,*q;
	Node* parent;
	if(root->keyword==child->keyword) {
	parent=NULL;
	}
	else {
	p=q=root;
	while(q!=NULL && q->keyword!=child->keyword) {
	p=q;
	if(child->keyword < p->keyword) {
	q=p->left;
	}
	else {
	q=p->right;
	}
	}
	if(child->keyword < p->keyword )
	parent=p;
	else if(child->keyword > p->keyword)
	parent=p;
	}
	return parent;
	}
	void deleteBst(Node* child) {
	//smallest from right subtree
	Node* parent=getParent(child);
	Node* child_succ;
	//for deleting single node
	if(parent == NULL && (child->left == NULL || child->right == NULL)) {
	if(child->left == NULL && child->right == NULL) {
	delete child;
	root=NULL;
	}
	else {
	if(child->left == NULL) {
	parent=child;
	child=child->right;
	root=child;
	delete parent;
	}
	else {
	parent=child;
	child=child->left;
	root=child;
	delete parent;
	}
	}
	return;
	}
	if(child->left != NULL && child->right != NULL) {
	parent=child;
	child_succ=child->right;
	while(child_succ->left != NULL) {
	parent=child_succ;
	child_succ = child_succ->left;
	}
	child->keyword =child_succ->keyword;
	child->mean=child_succ->mean;
	child=child_succ;
	}
	if(child->left == NULL && child->right ==NULL) {
	if(parent->right == child)
	parent->right=NULL;
	else
	parent->left=NULL;
	delete child;
	}
	if(child->left ==NULL && child->right != NULL) {
	if(parent->left==child)
	parent->left=child->right;
	else
	parent->right=child->right;
	delete child;
	}
	if(child->left!=NULL && child->right ==NULL) {
	if(parent->left ==child)
	parent->left=child->left;
	else
	parent->right=child->left;
	delete child;
	}
	}
	};
	int main() {
	int choice,c,s,n;
	Node* temp=NULL;
	Dictionary d,d1;
	string val,k,m,key;
	char ch;
	do {
	cout<<"1. Insert keyword \n";
	cout<<"2. Update meaning \n";
	cout<<"3. Delete Keyword \n";
	cout<<"4. Search \n";
	cout<<"5. copy \n";
	cout<<"6. Display tree (Ascending) \n";
	cout<<"7. Display tree (Descending) \n";
	cout<<"8. Average comparisions for searching any keyword \n";
	cout<<"Enter your choice: ";
	cin>>choice;
	switch(choice) {
	case 1: cout<<"Enter keyword: ";
	cin>>k;
	cout<<"Enter meaning: ";
	cin>>m;
	d.createTree(k,m);
	break;
	case 2: cout<<"Enter keyword to update its meaning: ";
	cin>>val;
	d.update(d.getRoot(),val);
	break;
	case 3: cout<<"Enter keyword you want to delete: ";
	cin>>key;
	temp=d.findNode(d.getRoot(),key);
	if(temp != NULL) {
	d.deleteBst(temp);
	cout<<"keyword Deleted"<<endl;
	}
	else
	cout<<"Keyword not found"<<endl;
	break;
	case 4: cout<<"Enter keyword do you want to search? : ";
	cin>>val;
	if(d.search(d.getRoot(),val) == -1)
	cout<<"Keyword not found"<<endl;
	else
	cout<<"Keyword Found"<<endl;
	break;
	case 5: d1=d;
	cout<<"Data in ascending order is: ";
	d.inorder(d.getRoot());
	break;
	case 6: d.inorder(d.getRoot());
	break;
	case 7: d.desc(d.getRoot());
	break;
	case 8: cout<<"cost is: "<<d.findAverage(d.getRoot())<<endl;
	break;
	default:cout<<"Invalid input"<<endl;
	break;
	}
	cout<<"Do you want to continue (Y/N): ";
	cin>>ch;
	}while(ch=='Y' || ch=='y');
	return 0;
	}

view raw BinarySearchTree.cpp hosted with ❤ by GitHub