Algorithm of Tree Traversals | Node Insertion , Deletion

PreOrder Travel | PostOrder Travel | InOrder Travel

Insert a node on a Tree , Traversing node (preorder,postopder,inorder) ,  Delete a node of a tree can be done as shown.

Source-Code :-

#include <iostream>
using namespace std;
struct node
{
int data;
node *left;
node *right;
}*btree;

class tree
{
public:
tree(){btree=NULL;}
void ins(int n);
node* ins1(node *temp,node *newnode);
void preorder(node *tree=btree);
void inorder(node *tree=btree);
void postorder(node *tree=btree);
void remove(int n);
};

node* tree::ins1(node *temp,node *newnode)
{
if(temp==NULL)
{
temp=newnode;
}
else if(temp->data<newnode->data)
{
ins1(temp->right,newnode);
if(temp->right==NULL) temp->right=newnode;
}
else
{
ins1(temp->left,newnode);
if(temp->left==NULL) temp->left=newnode;
}
return temp;
}

void tree::ins(int n)
{
node *temp=btree,*newnode;
newnode=new node;
newnode->left=NULL;
newnode->right=NULL;
newnode->data=n;
btree=ins1(temp,newnode);
}
void tree::preorder(node *tree)
{
if(tree==NULL) cout<<"Tree is empty";
else
{
cout<<tree->data<<'\t';
if(tree->left!=NULL) preorder(tree->left);
if(tree->right!=NULL) preorder(tree->right);
}
}
void tree::inorder(node *tree)
{
if(tree==NULL) cout<<"Tree is empty";
else
{
if(tree->left!=NULL) inorder(tree->left);
cout<<tree->data<<'\t';
if(tree->right!=NULL) inorder(tree->right);
}
}
void tree::postorder(node *tree)
{
if(tree==NULL) cout<<"Tree is empty";
else
{
if(tree->left!=NULL) postorder(tree->left);
if(tree->right!=NULL) postorder(tree->right);
cout<<tree->data<<'\t';
}
}
void tree::remove(int n)
{
node *temp=btree,*parent=btree,*marker;
if(temp==NULL) cout<<"The tree is empty"<<endl;
else
{
while(temp!=NULL && temp->data!=n)
{
parent=temp;
if(temp->data<n)
{
temp=temp->right;
}
else
{
temp=temp->left;
}
}
}
marker=temp;
if(temp==NULL) cout<<"No node present";
else if(temp==btree)
{
if(temp->right==NULL && temp->left==NULL)
{
btree=NULL;
}
else if(temp->left==NULL)
{
btree=temp->right;
}
else if(temp->right==NULL)
{
btree=temp->left;
}
else
{
node *temp1;
temp1=temp->right;
while(temp1->left!=NULL)
{
temp=temp1;
temp1=temp1->left;
}
if(temp1!=temp->right)
{
temp->left=temp1->right;
temp1->right=btree->right;
}
temp1->left=btree->left;
btree=temp1;
}
}
else
{
if(temp->right==NULL && temp->left==NULL)
{
if(parent->right==temp) parent->right=NULL;
else parent->left=NULL;
}
else if(temp->left==NULL)
{
if(parent->right==temp) parent->right=temp->right;
else parent->left=temp->right;
}
else if(temp->right==NULL)
{
if(parent->right==temp) parent->right=temp->left;
else parent->left=temp->left;
}
else
{
node *temp1;
parent=temp;
temp1=temp->right;
while(temp1->left!=NULL)
{
parent=temp1;
temp1=temp1->left;
}
if(temp1!=temp->right)
{
temp->left=temp1->right;
temp1->right=parent->right;
}
temp1->left=parent->left;
parent=temp1;
}
}
delete marker;
}

int main()
{
int ch,ch1;
tree t1;
int n;
do
{
cout<<"\n-----------------Menu---------------------"<<endl;
cout<<"1.Insert a node"<<endl;
cout<<"2.Traversing"<<endl;
cout<<"3.Delete a node"<<endl;
cout<<"4.Exit"<<endl;
cout<<"Enter your choice:";
cin>>ch;
switch(ch)
{
case 1:

cout<<"Enter the number to be inserted in tree:";
cin>>n;
t1.ins(n);
break;
case 2:

cout<<"\n^^^^^^^^^^^^^^Sub Menu^^^^^^^^^^^^^^"<<endl;
cout<<"1.Preorder Traversing"<<endl;
cout<<"2.Inorder Traversing"<<endl;
cout<<"3.Postorder Traversing"<<endl;
cout<<"4.Exit"<<endl;
cout<<"Enter your choice:";
cin>>ch1;
switch(ch1)
{
case 1:

cout<<"The numbers in preorder traversing are"<<endl;
t1.preorder();
break;
case 2:

cout<<"The numbers in inorder traversing are"<<endl;
t1.inorder();
break;
case 3:

cout<<"The numbers in postorder traversing are"<<endl;
t1.postorder();
break;
default:
break;
}
break;
case 3:
cout<<"Enter the number to be deleted in tree:";
cin>>n;
t1.remove(n);
break;
case 5:
break;
default:
cout<<"Out of menu";
break;
}
}while(ch!=4);
return 0;
}