dictionary.cpp

#include<iostream>
#include<string>
#include<exception>
#include<queue>
#define NULL __null
using namespace std;

class node{
public:
	node* create_node(string key, string meaning);
	node* insert_node(node* root, string key, string meaning);
	void print_node(node* root);
	bool search_node(node* root, string key, string meaning);
	void modify_node(node* root, string key, string meaning);
	node* delete_node(node* root, string key, string meaning);
	node* find_maximum(node* root);
	node* find_minimum(node* root);
	void mirror_image(node* root);
	void print_DFS(node* root);
	//virtual ~node();
private:
	string key,meaning;
	node* left,*right;
};

node* node::create_node(string key, string meaning){
	node* temp = new node(); 	 //create new node
	temp->key = key;  	//insert key
	temp->meaning = meaning; //insert meaning
	temp->left = NULL;	 //set left child as null
	temp->right = NULL;	//set right child as null
	return temp;	//return node address to the function insert_node()
}

node* node::insert_node(node* root,string key, string meaning){
	node* temp = create_node(key, meaning); //recieve address of node from create_node()
	if(root == NULL){ //check for root node if it is null thren set root as temp
		root = temp;
	} 
	else{	//search for apropreate position to insert node using recursion
		if(root->key >= key && root->meaning >= meaning){
			root->left = insert_node(root->left,key,meaning);
		}
		else{
			root->right = insert_node(root->right,key,meaning);
		}
	}
	return root; //after insertion return address to the main
}

void node::print_node(node* root){
	if(root!=NULL){
		cout<<root->key<<" "<<root->meaning<<endl;
		print_node(root->left);
		print_node(root->right);
	}
}

// search node
bool node::search_node(node* root ,string key, string meaning){
	if(root==NULL){   // if root is null tree is empty
		return false;
	}
	else{ 
		if(root->key == key && root->meaning == meaning){ //if keyand meaning are equal then return true
			return true;
		}
		else if(root->key >= key && root->meaning >= meaning){// find for key and its meaning in left child
			search_node(root->left,key,meaning);
		}
		else{
			search_node(root->right,key,meaning);// find for key and its meaning in right child
		}
	}
	//return false;//no need of this false statement
}

//modify node with new meaning
void node::modify_node(node* root, string key, string meaning){
	string n_meaning;
	if(root == NULL){ //if tree is empty then return
		return;
	}
	else{//search for key and mwaning which you want to modify
		if(root->key == key && root->meaning == meaning){ // if key are found then ask user for new meaning 
			cout<<"Enter new meaning :" ;cin>>n_meaning;//here we are not asking key because when we set the new key then order of binary tree get distrubed
			meaning = n_meaning;
		}
		else if(root->key >= key && root->meaning >= meaning){//search in left subtree
			modify_node(root->left,key,meaning);
		}
		else{
			modify_node(root->right,key,meaning);//search in right subtree
		}
	}
}

//mirror image
void node::mirror_image(node* root){
	if(root==NULL){
		return;
	}
	mirror_image(root->left);
	mirror_image(root->right);
	node* temp = root->left;//swaping of left child as right and right child as left
	root->left = root->right;
	root->right = temp;
}

//dfs printing
void node::print_DFS(node* root){
	queue<node*>q;//initialize the queue
	if(root){
		q.push(root);//if tree is not empty then push root node
		cout<<root->key<<" "<<root->meaning;
	}
	while(!q.empty()){//iterate till queue is not empty
		const node* const temp = q.front();//insert front node in the queue
		q.pop();//pop raer node
		if(temp->left){//if front node has left child then push it to the queue
			q.push(temp->left);
			cout<<temp->left->key<<" "<<root->left->meaning;
		}
		if(temp->right){//if front node has right child then push it to the queue
			q.push(temp->right);
			cout<<temp->right->key<<" "<<root->right->meaning;
		}
	}
}

//finding minimum
node* node::find_minimum(node* root)
{
    if(root==NULL){
        return NULL ;
    }
    while(root->left!=NULL)//in binary tree leftmost child is minimum 
    {
        root=root->left;//here we iterating it to till end of left subtree
   }
    return root;//finally return root
 }

node* node::find_maximum(node* root){
	if(root == NULL){
		return NULL;
	}
	while(root->right != NULL){//in binary tree rightmost child is maximum 
		root = root->right;//here we iterating it to till end of right subtree
	}
	return root;//finally return root
}


//deletion of node
node* node::delete_node(node* root, string key, string meaning){
	
 if(root==NULL)
    return root;
 else if(key < root->key)
    root->left = delete_node(root->left,key, meaning);
 else if(key > root->key)
    root->right = delete_node(root->right, key, meaning);
 else{
	 //if node has no child means leaf node
    if(root->left==NULL && root->right==NULL) 
    {
        delete root;
        root=NULL;
    }
	 //if node has one child i.e. either left child or right child
    else if(root->left == NULL)//deletion for left child
    {
        struct Node* temp=root;
        root=root->right;
        delete temp;
    }
    else if(root->right == NULL)//deletion for right child
    {
        struct Node* temp=root;
        root=root->left;
        delete temp;
    }
	 //if node has two child
    else{
        struct node* temp = find_minimum(root->right);//find maximum in left subtree 
        root->meaning = temp->meaning;//make copy of that node
        root->right= delete_node(root->right,key, temp->meaning);//delete node
    }
 }
 return root;//return new root node address
}

//you can add may menu in the main or other function
int main(){
	node* root=NULL,b;
	int n;
	string key,meaning;
	cout<<"How many data ?";cin>>n;
	while(n--){
		cout<<"Enter key ?";
		cin>>key;
		cout<<"Enter Meaning ?";
		cin>>meaning;
		root = b.insert_node(root,key,meaning);
	}
	cout<<"Data contains in tree is :\n";
	//b.print_node(root);
	b.mirror_image(root);
	b.print_node(root);
	cout<<"Enter key to search?";cin>>key;
	cout<<"Enter meaning to search ?";cin>>meaning;
	if(b.search_node(root,key,meaning)==true){
		cout<<"Data found in tree.\n";
	}
	else{
		cout<<"Data not found in tree.\n";
	}
}