/**********************************************************
Name : Jabir Daud Pathan
Name : Jabir Daud Pathan
Program : Create binary tree and Perform following
operations
1.
Find height of
the tree
2.
Print leaf nodes
3.
Find mirror
image
4.
Print original and
mirror image using level-wise printing
5.
Searching
6.
Insert element
7.
Delete element
8.
Counting total
no. of nodes
9.
Copy
10. Compare
11. Minsearch
12. Maxsearch
************************************************************/
/*------------<< Header File
>>------------*/
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
struct
node
{
int data;
node *left,*right;
};
/*----------<< Declaration of class tree
>>----------*/
class
tree
{
private:
node*root,*temp;
public :
tree() // Default constructor
{
root=NULL;
}
node*create(); // [ Functions
node*insert(node*,int); //
declaraton ]
node*delet(node*,int);
node*copy(node*);
void print(node*);
void mirror(node*);
void search(node*,int);
int leafnodes(node*,int);
int height(node*);
int minsearch(node*);
int maxsearch(node*);
int count(node*);
int compare(node*,node*);
};
/*------------<< Declaration of class queue
>>------------*/
class
queue
{
private:
node *data[20];
int front,rear;
public :
queue()
{
front=rear=-1;
}
void init()
{
front=rear=-1;
}
int empty()
{
if(rear==-1)
return 1;
return 0;
}
void enqueue(node*p)
{
if(empty())
front=rear=0;
else
rear=rear+1;
data[rear]=p;
}
node *dequeue()
{
node*p=data[front];
if(front==rear)
front=rear=-1;
else
front=front+1;
return(p);
}
};
/*----------<< Function defination for create
>>------------*/
node*tree::create()
{
node *root;
int x,n,i;
root=NULL;
cout<<"\nEnter the no of nodes
: ";
cin >> n;
cout<<"\nEnter the root node :
" ;
cin>>x;
root=insert(root,x);
for(i=1;i<n;i++)
{
cout<<"\nEnter the data :
" ;
cin>>x;
root=insert(root,x);
}
return root;
}
/*-------<< Function defination for insert node into tree
>>---------*/
node*tree::insert(node*root,int
x)
{
if(root==NULL)
{
root=new node;
root->data=x;
root->left=NULL;
root->right=NULL;
return root;
}
if(x>root->data)
{
root->right=insert(root->right,x);
return root;
}
root->left=insert(root->left,x);
return root;
}
/*------<< Function defination for delete any node from
tree >>-------*/
node*tree::delet(node*root,int
x)
{
node*temp;
if(root==NULL)
{
cout<<"\n\tElement is not
found";
return root;
}
if(x<root->data)
{
root->left=delet(root->left,x);
return root;
}
if(x>root->data)
{
root->right=delet(root->right,x);
return root;
}
if(root->left==NULL &&
root->right==NULL)
{
temp=root;
delete temp;
return NULL;
}
if(root->left==NULL)
{
temp=root;
root=root->right;
delete temp;
return root;
}
if(root->right==NULL)
{
temp=root;
root=root->left;
delete temp;
return root;
}
temp->data=minsearch(root->right);
root->data=temp->data;
root->right=delet(root->right,temp->data);
return root;
}
/*-------<< Function defination for display tree level
wise >>--------*/
void
tree::print(node*root)
{
queue q1,q2;
node*p1,*p2;
if(root==NULL)
cout<<"Tree is not created
";
q1.enqueue(root);
cout<<"
"<<root->data;
while(!q1.empty())
{
q2.init();
while(!q1.empty())
{
p1=q1.dequeue();
if(p1->left!=NULL)
{
q2.enqueue(p1->left);
cout<<"
"<<p1->left->data;
}
if(p1->right!=NULL)
{
q2.enqueue(p1->right);
cout<<"
"<<p1->right->data;
}
}
q1=q2;
}
}
/*------<< Function defination to find mirror image of
tree >>-------*/
void
tree::mirror(node*root)
{
node*temp,*temp1;
temp=root;
if(temp==NULL)
cout<<"Tree is not
created";
else
{
if(temp->left)
mirror(temp->left);
if(temp->right)
mirror(temp->right);
temp1=temp->left;
temp->left=temp->right;
temp->right=temp1;
}
}
/*--------<< Function defination for display leaf nodes
>>----------*/
int
tree::leafnodes(node*root,int cnt)
{
node *temp;
temp=root;
if(temp->left==NULL &&
temp->right==NULL)
{
cout<<" "<<temp->data;
cnt++;
}
else
{
if(temp->left!=NULL)
{
cnt=leafnodes(temp->left,cnt);
}
if(temp->right!=NULL)
{
cnt=leafnodes(temp->right,cnt);
}
}
return cnt;
}
int
max(int value1, int value2)
{
return ( (value1 > value2) ? value1 :
value2);
}
/*--------<< Function defination for height of tree
>>---------*/
int
tree::height(node*root)
{
node*temp;
temp=root;
if(temp==NULL)
{
return 0;
}
else
if(temp->left==NULL&&temp->right==NULL)
{
return 1;
}
else
return
(max(height(temp->left),height(temp->right))+1);
}
/*--------<< Function defination for search any node into
tree >>---------*/
void
tree::search(node*root,int j)
{
node*temp;
temp=root;
while(temp!=NULL)
{
if(temp->data==j)
{
cout<<"\nelement"<<"
"<<j<<" is present in tree";
break;
}
else if(temp->data<j)
{
temp=temp->right;
}
else if(temp->data>j)
{
temp=temp->left;
}
}
if(temp->data!=j)
{
cout<<"\nElement"<<"
"<<j<<" is not present in tree";
}
}
/*-------<< Function defination to find minimum value of
node in tree >>---------*/
int
tree::minsearch(node*root)
{
while(root->left!=NULL)
{
root=root->left;
}
return root->data;
}
/*-------<< Function defination to find maximum value of
node in tree >>---------*/
int
tree::maxsearch(node*root)
{
while(root->right!=NULL)
{
root=root->right;
}
return root->data;
}
/*--------<< Function defination to counting total no of
nodes >>----------*/
int
cnt=0;
int
tree::count(node*root)
{
if(root==NULL)
{
return 0;
}
else
{
cnt++;
count(root->left);
count(root->right);
}
return cnt;
}
/*--------<< Function defination for copy tree
>>----------*/
node*tree::copy(node*root)
{
node*temp;
temp=NULL;
if(root!=NULL)
{
temp=new node;
temp->data=root->data;
temp->left=copy(root->left);
temp->right=copy(root->right);
}
return temp;
}
/*-------<< Function defination for compare two trees
>>----------*/
int
tree::compare(node* root1,node* root2)
{
int j=0;
if(root1==NULL&&root2==NULL)
{
j=1;
}
else if(root1!=NULL&&root2!=NULL)
{
if(root1->data==root2->data)
{
if(compare(root1->left,root2->left))
{
j=compare(root1->right,root2->right);
}
}
}
return j;
}
/*-------------<< Main Function Starts >>------------*/
void
main()
{
clrscr();
tree t;
node*root,*temp;
int ch,ht=0,j,cnt=0;
char ans;
do
{
clrscr();
cout<<"\n\n\t\t\t-------<<
MENU >>-------";
cout<<"\n\t\t\t1.Create binary
Tree";
cout<<"\n\t\t\t2.Print
original";
cout<<"\n\t\t\t3.Height of the
tree";
cout<<"\n\t\t\t4.Print leaf
nodes";
cout<<"\n\t\t\t5.Print mirror
image";
cout<<"\n\t\t\t6.Searching";
cout<<"\n\t\t\t7.insert element";
cout<<"\n\t\t\t8.delete
element";
cout<<"\n\t\t\t9.counting total
no. of nodes";
cout<<"\n\t\t\t10.copy";
cout<<"\n\t\t\t11.compare";
cout<<"\n\t\t\t12.minsearch";
cout<<"\n\t\t\t13.maxsearch";
cout<<"\n\t\t\t14.Exit";
cout<<"\n\t\t\t---------------------------";
cout <<"\n\t\t\tEnter Your Choice
: ";
cin>>ch;
switch(ch)
{
case 1:
root=t.create();
break;
case 2:
cout<<"\nlevel_wise tree is
: ";
t.print(root);
break;
case 3:
ht=t.height(root);
cout<<"\nHeight of the Tree
: " <<ht;
break;
case 4:
if(root==NULL)
{
cout<<"\nTree is not
created";
}
else
{
cout<<"\nLeaf nodes are :
";
cnt=t.leafnodes(root,cnt);
cout<<"\n\nTotal no of
Leaf nodes are : "<<cnt;
}
break;
case 5:
cout<<"\nOriginal Tree is :
" ;
t.print(root);
t.mirror(root);
cout<<"\n\nMirror Image of
Tree : " ;
t.print(root);
break;
case 6:
cout<<"\nEnter the element to
be search :";
cin>>j;
t.search(root,j);
break;
case 7:
cout<<"\nEnter the element to
be insert :";
cin>>j;
t.insert(root,j);
cout<<"\nAfter inserting
element level_wise tree is : ";
t.print(root);
break;
case 8:
cout<<"\nEnter the element to
be deleted :";
cin>>j;
t.delet(root,j);
cout<<"\nAfter deleting
element level_wise tree is : ";
t.print(root);
break;
case 9:
cnt=t.count(root);
cout<<"\nTotal no of nodes in
tree is : "<<cnt;
break;
case 10:
root=t.create();
cout<<"\nOriginal tree is
[T1] : ";
t.print(root);
temp=t.copy(root);
cout<<"\n\nAfter copy tree is
[T2] : ";
t.print(temp);
break;
case 11:
node*root1,*root2;
cout<<"\nEnter 1st tree data
:\n";
root1=t.create();
cout<<"\n\nEnter 2nd tree
data :\n";
root2=t.create();
cout<<"\nTree [T1] is :
";
t.print(root1);
cout<<"\n\nTree [T2] is :
";
t.print(root2);
j=t.compare(root1,root2);
if(j==1)
cout<<"\n\nTree's
(T1&T2) are Equal";
else
cout<<"\n\nTree's
(T1&T2) are not Equal";
break;
case 12:
j=t.minsearch(root);
cout<<"\nSmallest element in
tree is : "<<j;
break;
case 13:
j=t.maxsearch(root);
cout<<"\nGreatest element in
tree is : "<<j;
break;
case 14:
exit(0);
break;
}
cout<<"\n\n\n\tDo you want to continue(y/n):
";
ans=getche();
}while(ans=='y'||ans=='Y');
getch();
}
/*-------------<< End Of Main Function >>---------------*/
/*-----------------<< OUTPUT
SCREEN >>-------------------*/
-------<< MENU
>>-------
1.Create binary Tree
2.Print original
3.Height of the tree
4.Print leaf nodes
5.Print mirror image
6.Searching
7.insert element
8.delete element
9.counting total no. of
nodes
10.copy
11.compare
12.minsearch
13.maxsearch
14.Exit
---------------------------
Enter Your Choice : 1
Enter
the no of nodes : 7
Enter
the root node : 20
Enter
the data : 10
Enter
the data : 12
Enter
the data : 5
Enter
the data : 11
Enter
the data : 30
Enter
the data : 25
Do you want to continue(y/n):y
-------<< MENU
>>-------
1.Create binary Tree
2.Print original
3.Height of the tree
4.Print leaf nodes
5.Print mirror image
6.Searching
7.insert element
8.delete element
9.counting total no. of nodes
10.copy
11.compare
12.minsearch
13.maxsearch
14.Exit
---------------------------
Enter Your Choice : 2
level_wise
tree is : 20 10 30 5 12 25 11
Do you want to continue(y/n):y
-------<< MENU
>>-------
1.Create binary Tree
2.Print original
3.Height of the tree
4.Print leaf nodes
5.Print mirror image
6.Searching
7.insert element
8.delete element
9.counting total no. of
nodes
10.copy
11.compare
12.minsearch
13.maxsearch
14.Exit
---------------------------
Enter Your Choice : 3
Height
of the Tree : 4
Do you want to continue(y/n):y
-------<< MENU
>>-------
1.Create binary Tree
2.Print original
3.Height of the tree
4.Print leaf nodes
5.Print mirror image
6.Searching
7.insert element
8.delete element
9.counting total no. of
nodes
10.copy
11.compare
12.minsearch
13.maxsearch
14.Exit
---------------------------
Enter Your Choice : 4
Leaf
nodes are : 5 11 25
Total
no of Leaf nodes are : 3
Do you want to continue(y/n):y
-------<< MENU
>>-------
1.Create binary Tree
2.Print original
3.Height of the tree
4.Print leaf nodes
5.Print mirror image
6.Searching
7.insert element
8.delete element
9.counting total no. of
nodes
10.copy
11.compare
12.minsearch
13.maxsearch
14.Exit
---------------------------
Enter Your Choice : 5
Original
Tree is : 20 10 30 5 12 25 11
Mirror
Image of Tree : 20 30 10 25 12 5 11
Do you want to continue(y/n):y
-------<< MENU
>>-------
1.Create binary Tree
2.Print original
3.Height of the tree
4.Print leaf nodes
5.Print mirror image
6.Searching
7.insert element
8.delete element
9.counting total no. of
nodes
10.copy
11.compare
12.minsearch
13.maxsearch
14.Exit
---------------------------
Enter Your Choice : 6
Enter
the element to be search :12
element
12 is present in tree
Do you want to continue(y/n):y
-------<< MENU
>>-------
1.Create binary Tree
2.Print original
3.Height of the tree
4.Print leaf nodes
5.Print mirror image
6.Searching
7.insert element
8.delete element
9.counting total no. of
nodes
10.copy
11.compare
12.minsearch
13.maxsearch
14.Exit
---------------------------
Enter Your Choice : 7
Enter
the element to be insert :70
After
inserting element level_wise tree is :
20 10 30 5 12 25 70 11
Do you want to continue(y/n):y
-------<< MENU
>>-------
1.Create binary Tree
2.Print original
3.Height of the tree
4.Print leaf nodes
5.Print mirror image
6.Searching
7.insert element
8.delete element
9.counting total no. of
nodes
10.copy
11.compare
12.minsearch
13.maxsearch
14.Exit
---------------------------
Enter Your Choice : 8
Enter
the element to be deleted :12
After
deleting element level_wise tree is : 20
10 30 5 11 25 70
Do you want to continue(y/n):y
-------<< MENU
>>-------
1.Create binary Tree
2.Print original
3.Height of the tree
4.Print leaf nodes
5.Print mirror image
6.Searching
7.insert element
8.delete element
9.counting total no. of
nodes
10.copy
11.compare
12.minsearch
13.maxsearch
14.Exit
---------------------------
Enter Your Choice : 9
Total
no of nodes in tree is : 7
Do you want to continue(y/n):y
-------<< MENU
>>-------
1.Create binary Tree
2.Print original
3.Height of the tree
4.Print leaf nodes
5.Print mirror image
6.Searching
7.insert element
8.delete element
9.counting total no. of
nodes
10.copy
11.compare
12.minsearch
13.maxsearch
14.Exit
---------------------------
Enter Your Choice : 10
Enter
the no of nodes : 7
Enter
the root node : 20
Enter
the data : 10
Enter
the data : 30
Enter
the data : 11
Enter
the data : 5
Enter
the data : 25
Enter
the data : 70
Original
tree is [T1] : 20 10 30 5 11 25 70
After
copy tree is [T2] : 20 10 30 5 11 25 70
Do you want to continue(y/n):y
-------<< MENU
>>-------
1.Create binary Tree
2.Print original
3.Height of the tree
4.Print leaf nodes
5.Print mirror image
6.Searching
7.insert element
8.delete element
9.counting total no. of
nodes
10.copy
11.compare
12.minsearch
13.maxsearch
14.Exit
---------------------------
Enter Your Choice : 11
Enter
1st tree data :
Enter
the no of nodes : 7
Enter
the root node : 20
Enter
the data : 10
Enter
the data : 12
Enter
the data : 5
Enter
the data : 11
Enter
the data : 30
Enter
the data : 25
Enter
2nd tree data :
Enter
the no of nodes : 7
Enter
the root node : 20
Enter
the data : 30
Enter
the data : 25
Enter
the data : 10
Enter
the data : 12
Enter
the data : 11
Enter
the data : 5
Tree
[T1] is : 20 10 30 5 12 25 11
Tree
[T2] is : 20 10 30 5 12 25 11
Tree's
(T1&T2) are Equal
Do you want to continue(y/n):y
-------<< MENU
>>-------
1.Create binary Tree
2.Print original
3.Height of the tree
4.Print leaf nodes
5.Print mirror image
6.Searching
7.insert element
8.delete element
9.counting total no. of
nodes
10.copy
11.compare
12.minsearch
13.maxsearch
14.Exit
---------------------------
Enter Your Choice : 12
Smallest
element in tree is : 5
Do you want to continue(y/n):y
-------<< MENU
>>-------
1.Create binary Tree
2.Print original
3.Height of the tree
4.Print leaf nodes
5.Print mirror image
6.Searching
7.insert element
8.delete element
9.counting total no. of
nodes
10.copy
11.compare
12.minsearch
13.maxsearch
14.Exit
---------------------------
Enter Your Choice : 13
Greatest
element in tree is : 70
Do you want to continue(y/n):y
-------<< MENU
>>-------
1.Create binary Tree
2.Print original
3.Height of the tree
4.Print leaf nodes
5.Print mirror image
6.Searching
7.insert element
8.delete element
9.counting total no. of
nodes
10.copy
11.compare
12.minsearch
13.maxsearch
14.Exit
---------------------------
Enter Your Choice : 14
/************************************************************/
No comments:
Post a Comment