#include<iostream.h>
#include<process.h>
#include<math.h>
#include<conio.h>
class node
{
public:
node *left;
node *right;
int data;
node()
{
left=NULL;
right=NULL;
}
}*root=NULL;
int flag=0;
void add(node
*parent,node *r,int d,int level,int item)
{
if(r!=NULL)
{
add(r,r->left,d+1,level,item);
add(r,r->right,d+1,level,item);
}
else if(d==level && flag!=1)
{
flag=1;
node *newnode = new node;
newnode->data=item;
if(parent->left==NULL)
parent->left=newnode;
else
parent->right=newnode;
}
}
void npreorder()
{
node *ptr=root;
int top=-1;
node **stack = new node*[50];
while(1)
{
if(ptr!=NULL)
{
cout<<" "<<ptr->data;
if(ptr->right!=NULL)
stack[++top]=ptr->right;
ptr=ptr->left;
}
else
{
ptr=stack[top--];
if(top==-2)
return;
}
}
}
void ninorder()
{
node **stack= new node*[50];
int top=0;
node *ptr=root,*process=NULL;
while(top>=0)
{
if(ptr && process!=ptr)
{
stack[++top]=ptr;
ptr=ptr->left;
}
else
{
ptr=stack[top--];
process=ptr;
cout<<" "<<ptr->data;
if(ptr->right)
ptr=ptr->right;
}
}
}
void main()
{
clrscr();
int ch,item;
cout<<"1.ADD\n2.PREORDER\n3.DEPTH\n4.NO
OF ELEMENTS\n5.TRACE";
cout<<"\n6.BFS AND
DFS\n7.EXIt";
while(1)
{
cout<<"\nchoice? ";
cin>>ch;
switch(ch)
{
case 1: cout<<"ITEM
:";
cin>>item;
flag=0;
if(root==NULL)
{
node *newnode =
new node;
newnode->data=item;
root=newnode;
}
else
{
maxdepth=0;
depth(root,0);
int level;
int
elements=count(root);
if(elements==(pow(2,maxdepth+1)-1))
level=maxdepth+1;
else
level=maxdepth;
add(root,root,0,level,item);
}
break;
case 2: ninorder();
//npreorder();
//preorder(root);
break;
case 3: maxdepth=0;
depth(root,0);
cout<<maxdepth;
break;
case 4:
cout<<count(root);
break;
case 5: equal=0;
cout<<"ITEM
TO TRACE : ";
cin>>item;
trace(root,item);
break;
case 6:
cout<<"\nBFS\n";
bfs();
cout<<"\nDFS\n";
dfs();
break;
case 7: exit(0);
}
}
}
No comments:
Post a Comment