Binary Search Tree with non-recursive traversals

# include < conio.h > 
# include < process.h > 
# include < iostream.h > 
# include < alloc.h > 
struct node 
{ 
int ele; 
node *left; 
node *right; 
}; 
typedef struct node *nodeptr; 
class stack 
{ 
private: 
struct snode 
{ 
nodeptr ele; 
snode *next; 
}; 
snode *top; 
public: 
stack() 
{ 
top=NULL; 
} 
void push(nodeptr p) 
{ 
snode *temp; 
temp = new snode; 
temp->ele = p; 
temp->next = top; 
top=temp; 
} 
void pop() 
{ 
if (top != NULL) 
{ 
nodeptr t; 
snode *temp; 
temp = top; 
top=temp->next; 
delete temp; 
} 
} 
nodeptr topele() 
{ 
if (top !=NULL) 
return top->ele; 
else 
return NULL; 
} 
int isempty() 
{ 
return ((top == NULL) ? 1 : 0); 
} 
}; 
class bstree 
{ 
public: 
void insert(int,nodeptr &); 
void del(int,nodeptr &); 
int deletemin(nodeptr &); 
void find(int,nodeptr &); 
nodeptr findmin(nodeptr); 
nodeptr findmax(nodeptr); 
void copy(nodeptr &,nodeptr &); 
void makeempty(nodeptr &); 
nodeptr nodecopy(nodeptr &); 
void preorder(nodeptr); 
void inorder(nodeptr); 
void postorder(nodeptr); 
void preordernr(nodeptr); 
void inordernr(nodeptr); 
void postordernr(nodeptr); 
void leftchild(int,nodeptr &); 
void rightchild(int,nodeptr &); 
}; 
void bstree::insert(int x,nodeptr &p) 
{ 
if (p==NULL) 
{ 
p = new node; 
p->ele=x; 
p->left=NULL; 
p->right=NULL; 
} 
else 
{ 
if (x < p->ele) 
insert(x,p->left); 
else if (x>p->ele) 
insert(x,p->right); 
else 
cout<<"Element already Exits !"; 
} 
} 
void bstree:: del(int x,nodeptr &p) 
{ 
nodeptr d; 
if (p==NULL) 
cout<<"Element not found "; 
else if (x < p->ele) 
del(x,p->left); 
else if (x > p->ele) 
del(x,p->right); 
else if ((p->left == NULL) && (p->right ==NULL)) 
{ 
d=p; 
free(d); 
p=NULL; 
} 
else if (p->left == NULL) 
{ 
d=p; 
free(d); 
p=p->right; 
} 
else if (p->right ==NULL) 
{ 
d=p; 
p=p->left; 
free(d); 
}
else 
p->ele=deletemin(p->right); 
} 
int bstree::deletemin(nodeptr &p) 
{ 
int c; 
if (p->left == NULL) 
{ 
c=p->ele; 
p=p->right; 
return c; 
} 
else 
c=deletemin(p->left); 
return c; 
} 
void bstree::copy(nodeptr &p,nodeptr &p1) 
{ 
makeempty(p1); 
p1=nodecopy(p); 
} 
void bstree::makeempty(nodeptr &p) 
{ 
nodeptr d; 
if (p!=NULL) 
{ 
makeempty(p->left); 
makeempty(p->right); 
d=p; 
free(d); 
p=NULL; 
} 
} 
nodeptr bstree::nodecopy(nodeptr &p) 
{ 
nodeptr temp; 
if (p == NULL) 
return p; 
else 
{ 
temp = new node; 
temp->ele=p->ele; 
temp->left = nodecopy(p->left); 
temp->right = nodecopy(p->right); 
return temp; 
} 
} 
nodeptr bstree::findmin(nodeptr p) 
{ 
if (p==NULL) 
{ 
cout<<"Tree is empty !"; 
return p; 
} 
else 
{ 
while (p->left !=NULL) 
p=p->left; 
return p; 
} 
} 
nodeptr bstree::findmax(nodeptr p) 
{ 
if (p==NULL) 
{ 
cout<<"Tree is empty !"; 
return p; 
} 
else 
{ 
while (p->right !=NULL) 
p=p->right; 
return p; 
} 
} 
void bstree::find(int x,nodeptr &p) 
{
if (p==NULL) 
cout<<"Element not found !"; 
else 
{ 
if (x < p->ele) 
find(x,p->left); 
else if ( x> p->ele) 
find(x,p->right); 
else 
cout<<"Element Found !"; 
} 
} 
void bstree::preorder(nodeptr p) 
{ 
if (p!=NULL) 
{ 
cout<< p->ele<<"-->"; 
preorder(p->left); 
preorder(p->right); 
} 
} 
void bstree::inorder(nodeptr p) 
{ 
if (p!=NULL) 
{ 
inorder(p->left); 
cout<< p->ele<<"-->"; 
inorder(p->right);
} 
} 
void bstree::postorder(nodeptr p) 
{ 
if (p!=NULL) 
{ 
postorder(p->left); 
postorder(p->right); 
cout<< p->ele<<"-->"; 
}

} 
void bstree::preordernr(nodeptr p) 
{ 
stack s; 
while (1) 
{ 
if (p != NULL) 
{ 
cout<< p->ele<<"-->"; 
s.push(p); 
p=p->left; 
} 
else if (s.isempty()) 
{ 
cout<<"Stack is empty"; 
return; 
} 
else 
{ 
nodeptr t; 
t=s.topele(); 
p=t->right; 
s.pop(); 
} 
} 
} 
void bstree::inordernr(nodeptr p) 
{ 
stack s; 
while (1) 
{ 
if (p != NULL) 
{ 
s.push(p); 
p=p->left; 
} 
else 
{ 
if (s.isempty()) 
{ 
cout<<"Stack is empty"; 
return; 
} 
else 
{ 
p=s.topele();
cout<< p->ele<<"-->"; 
} 
s.pop(); 
p=p->right; 
} 
} 
} 
void bstree::postordernr(nodeptr p) 
{ 
stack s; 
while (1) 
{ 
if (p != NULL) 
{ 
s.push(p); 
p=p->left; 
} 
else 
{ 
if (s.isempty()) 
{ 
cout<<"Stack is empty"; 
return; 
} 
else 
if (s.topele()->right == NULL) 
{ 
p=s.topele(); 
s.pop(); 
cout<< p->ele<<"-->"; 
if (p==s.topele()->right) 
{ 
cout<< s.topele()->ele<<"-->"; 
s.pop(); 
} 
} 
if (!s.isempty()) 
p=s.topele()->right; 
else 
p=NULL; 
} 
} 
} 
void bstree::leftchild(int q,nodeptr &p) 
{ 
if (p==NULL) 
cout<<"The node does not exists "; 
else 
if (q < p->ele ) 
leftchild(q,p->left); 
else 
if (q > p->ele) 
leftchild(q,p->right); 
else 
if (q == p->ele) 
{ 
if (p->left != NULL) 
cout<<"Left child of "<< q<<"is "<< p->left->ele; 
else 
cout<<"No Left child !"; 
} 
} 
void bstree::rightchild(int q,nodeptr &p) 
{ 
if (p==NULL) 
cout<<"The node does not exists "; 
else 
if (q < p->ele ) 
rightchild(q,p->left); 
else 
if (q > p->ele) 
rightchild(q,p->right); 
else 
if (q == p->ele) 
{ 
if (p->right != NULL) 
cout<<"Right child of "<< q<<"is "<< p->right->ele; 
else 
cout<<"No Right Child !"; 
} 
} 
int main() 
{ 
int ch,x,leftele,rightele; 
bstree bst; 
char c='y'; 
nodeptr root,root1,min,max; 
root=NULL; 
root1=NULL; 
do 
{ 
// system("clear");
clrscr(); 
cout<<"Binary Search Tree "; 
cout<<"-------------------------"; 
cout<<"1.Insertion 
2.Deletion 
3.NodeCopy"; 
cout<<"4.Find 
5.Findmax 
6.Findmin"; 
cout<<"7.Preorder 
8.Inorder 
9.Postorder"; 
cout<<"10.Leftchild 
11.Rightchild 
0.Exit"; 
cout<<"Enter your choice :"; 
cin>>ch; 
switch(ch) 
{ 
case 1: 
cout<<"1.Insertion"; 
cout<<"Enter the new element to get inserted :"; 
cin>>x; 
bst.insert(x,root); 
cout<<"Inorder traversal is :"; 
bst.inorder(root); 
break; 
case 2: 
cout<<"2.Deletion"; 
cout<<"Enter the element to get deleted :"; 
cin>>x; 
bst.del(x,root); 
bst.inorder(root); 
break; 
case 3: 
cout<<"3.Nodecopy"; 
bst.copy(root,root1); 
cout<<"The new tree is :"; 
bst.inorder(root1); 
break; 
case 4: 
cout<<"4.Find"; 
cout<<"Enter the element to be searched :"; 
cin>>x; 
bst.find(x,root); 
break; 
case 5: 
cout<<"5.Findmax"; 
if (root == NULL) 
cout<<"Tree is empty"; 
else 
{ 
max=bst.findmax(root); 
cout<<"Largest element is : "<< max->ele<< endl; 
} 
break; 
case 6: 
cout<<"6.Findmin"; 
if (root == NULL) 
cout<<"Tree is empty"; 
else 
{ 
min=bst.findmin(root); 
cout<<"Smallest element is : "<< min->ele<< endl; 
} 
break; 
case 7: 
cout<<"7.Preorder"; 
if (root==NULL) 
cout<<"Tree is empty"; 
else 
{ 
cout<<"Preorder traversal (Non-Recursive) is :"; 
bst.preordernr(root); 
cout<<"Preorder traversal (Recursive) is :"; 
bst.preorder(root); 
} 
break; 
case 8: 
cout<<"8.Inorder"; 
if (root==NULL) 
cout<<"Tree is empty"; 
else 
{ 
cout<<"Inorder traversal (Non-Recursive) is :"; 
bst.inordernr(root); 
cout<<"Inorder traversal (Recursive) is :"; 
bst.inorder(root); 
} 
break; 
case 9: 
cout<<"9.Postorder"; 
if (root==NULL) 
cout<<"Tree is empty"; 
else 
{ 
cout<<"Postorder traversal (Non-Recursive) is :"; 
bst.postordernr(root); 
cout<<"Postorder traversal (Recursive) is :"; 
bst.postorder(root); 
} 
break; 
case 10: 
cout<<"10.Finding the left Child "; 
if (root==NULL) 
cout<<"Tree is empty"; 
else 
{ 
cout<<"Enter the node for which the left child is to be found :"; 
cin>>leftele; 
bst.leftchild(leftele,root); 
} 
break; 
case 11: 
cout<<"11.Finding the Right Child "; 
if (root==NULL) 
cout<<"Tree is empty"; 
else 
{ 
cout<<"Enter the node for which the Right child is to be found :"; 
cin>>rightele; 
bst.rightchild(rightele,root); 
} 
break; 
case 0: 
exit(0); 
} 
cout<<"Continue (y/n) ?"; 
cin>>c; 
}
while (c=='y' || c == 'Y'); 
return 0; 
}