Binary Search Tree

// BST.cpp : Defines the entry point for the console application.
//

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

using namespace std;

class Node{
public:
int data;
Node *right;
Node *left;
public:
Node(){
data=0;
left=NULL;
right=NULL;
}

Node(int d){
data=d;
right=NULL;
left=NULL;
cout<<"\nNode created containing the value "<<d<<endl;
}

int getData(){
return data;
}

void setdata(int d){
data=d;
}

Node *getRight(){
if(right==NULL){
return 0;
}
else
return right;
}

void setRight(Node *r){
right=r;
}

Node *getLeft(){
if(left==NULL){
return 0;
}
else
return left;
}

void setLeft(Node *l){
left=l;
}
};

class Tree{
private:
Node *root;
Node *current;
int flag;
public:
Tree(int d){
flag=0;
Node *newNode= new Node();
newNode->data=d;
newNode->right=NULL;
newNode->left=NULL;
root=newNode;
current=root;
}

Node *getCurrent(){
return current;
}

Node *getRoot(){
return root;
}

void insert(Node *current, int d){
if(d==current->data){
cout<<"\nRepeated values are not allowed: ";
}
if(d<current->data){
if(current->left==NULL){
Node *newNode = new Node;
newNode->data = d;
newNode->right=NULL;
newNode->left=NULL;
cout<<"\nThe data is entered in memory at location(newNode) : "<<newNode;
current->left=newNode;
cout<<"\nThe current pointer is pointing at : "<<current<<endl;
}
else{
cout<<"\nGoing left to memory location: "<<current->left<<endl;
insert(current->left,d);
}
}
if(d>current->data){
if(current->right==NULL){
Node *newNode = new Node;
newNode->data = d;
newNode->right=NULL;
newNode->left=NULL;
cout<<"\nThe data is entered in memory at location(newNode) : "<<newNode;
current->right=newNode;
cout<<"\nThe current pointer is pointing at : "<<current<<endl;
}
else {
cout<<"\nGoing right to memory location: "<<current->right<<endl;
insert(current->right,d);
}
}
}

Node *search(Node *current, int d){
if(d==current->data){
return current;
}
else if(d<current->data){
if(current->left==NULL){
return NULL;
}
else search(current->left, d);
}
else if(d>current->data){
if(current->right==NULL){
return NULL;
}
else search(current->right,d);
}
}

bool isLeaf(Node *current){
if(current->left==current->right==NULL)
return true;
else
return false;
}

Node *findMin(Node *current){
if(current->left==NULL){
cout<<"\nReturning the minimum value : "<<current->data;
return current;
}
else findMin(current->left);
}

void deleteNode(Node *current, int d){
if(d<current->data){
 if(current->left!=NULL){
if(d==current->left->data){
if((current->left->left==NULL) && (current->left->right==NULL)){
cout<<"\nDeleting Node containing "<<current->left->data<<endl;
delete (current->left);
current->left=NULL;
}
else if(current->left->left==NULL && current->left->right!=NULL){
Node *temp=new Node;
temp=current->left;
current->left=current->left->right;
cout<<"\nDeleting Node containing "<<temp->data<<endl;
delete temp;
}
else if(current->left->right==NULL && current->left->left!=NULL){
Node *temp=new Node;
temp=current->left;
current->left=current->left->left;
cout<<"\nDeleting Node containing "<<temp->data<<endl;
delete temp;
}
else if(current->left->left!=NULL && current->left->right!=NULL){

Node *temp=new Node;
temp=findMin(current->left->right);
cout<<"\nReplacing "<<current->left->data<< " with "<<temp->data;
current->left->data=temp->data;
cout<<"\nDeleting Node containing "<<temp->data<<endl;
delete temp;
}
}
else {
cout<<"\nMoving to left Node ";
deleteNode(current->left, d);
}
}
}
if(d>current->data){
 if(current->right!=NULL){
if(d==current->right->data){
if((current->right->left==NULL) && (current->right->right==NULL)){
cout<<"\nDeleting Node containing "<<current->right->data<<endl;
delete (current->right);
current->right=NULL;
}
else if(current->right->left==NULL && current->right->right!=NULL){
Node *temp=new Node;
temp=current->right;
current->right=current->right->right;
cout<<"\nDeleting Node containing "<<temp->data<<endl;
delete temp;
}
else if(current->right->right==NULL && current->right->left!=NULL){
Node *temp=new Node;
temp=current->right;
current->right=current->right->left;
cout<<"\nDeleting Node containing "<<temp->data<<endl;
delete temp;
}
else if(current->left->left!=NULL && current->left->right!=NULL){

Node *temp=new Node;
temp=findMin(current->right->right);
cout<<"\nReplacing "<<current->right->data<< " with "<<temp->data;
current->right->data=temp->data;
cout<<"\nDeleting Node containing "<<temp->data<<endl;
delete temp;
}
}
else {
cout<<"\nMoving to right Node ";
deleteNode(current->right, d);
}
 }
}
if(d==current->data){
if(current->right==NULL){
Node *temp=new Node;
temp=current;
current=current->left;
cout<<"\nDeleting Node containing "<<temp->data<<endl;
delete temp;
}
else if(current->left==NULL){
Node *temp=new Node;
temp=current;
current=current->right;
cout<<"\nDeleting Node containing "<<temp->data<<endl;
delete temp;
}
else if(current->right!=NULL && current->left!=NULL){
Node *temp=new Node;
temp=findMin(current->right);
current->data=temp->data;
cout<<"\nDeleting Node containing "<<temp->data<<endl;
delete temp;
}
}
}

void inOrder(Node *current){

if(current!=NULL){

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

void preOrder(Node *current){

if(current!=NULL){

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

void postOrder(Node *current){

if(current!=NULL){

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


int _tmain(int argc, _TCHAR* argv[])
{
int d=0;
cout<<"\nSelect the root of your tree :";
cin>>d;
Tree t(d);
int option;

cout<<"Enter your option: \n1) Insert data: \n2) Inorder Traversal: \n3) Search: \n4) Preoder Traversal: \n5) Postorder Traversal:  \n6) Find Minimum: \n7) Delete Node: \n8) Press 0 to exit: ";
cin>>option;

while(option!=0){
switch(option){
case 1:
cout<< "\nEnter the data you want to insert: ";
cin>> d;
t.insert(t.getRoot(), d);
cout<<"\nThe root is "<< t.getRoot();
cout<<"\nThe current pointer is "<< t.getCurrent()<<endl;
break;

case 2:
t.inOrder(t.getRoot());
cout<<endl;
break;

case 3:{
cout<<"\nEnter the number you want to search :" ;
cin>>d;
Node *temp=new Node;
temp=t.search(t.getRoot(),d);
if(temp){
cout<<"\nThe number "<< temp->data<< " exists in the tree ";
}
else cout<<"\nThe number "<< d<<" does not exist in the tree ";
break;
}

case 4:
t.preOrder(t.getRoot());
break;

case 5:
t.postOrder(t.getRoot());
break;



case 6:{
Node *temp=new Node;
temp=t.findMin(t.getRoot());
cout<<temp->data<<endl;
break;
  }

case 7:{
cout<<"\nEnter the number you want to delete: ";
cin>>d;
t.deleteNode(t.getRoot(), d);
break;
  }
default:
cout<<"\nEnter a correct option: ";
}
cout<<"\nEnter your option: \n1) Insert data: \n2) Inorder Traversal: \n3) Search: \n4) Preoder Traversal: \n5) Postorder Traversal:  \n6) Find Minimum: \n7) Delete Node: \n8) Press 0 to exit: ";
cin>>option;
}
return 0;
}