BST Program

Write a BST Program that insert,inorder traversal, count external node,count internal node of tree as well as display external node, internal node and also  display height of tree:-

#include<conio.h>
#include<iostream.h>
#include<process.h>
struct node
{
node *left;
node *right;
int info;
};
node *root=NULL;
int count_e, count_i;
void insert()
{
node *temp,*save,*ptr;
int x;
temp=new node;
temp->left=NULL;
temp->right=NULL;
cout<<"enter value for node:"  ;
cin>>x;
temp->info=x;
if(root==NULL)
root=temp;
else
{
save=NULL;ptr=root;
while(ptr!=NULL)
{
if(x<ptr->info)
{
save=ptr;
ptr=ptr->left;
}
else
{
save=ptr;
ptr=ptr->right;
}


}
if(x<save->info)
save->left=temp;
else
save->right=temp;
}
}

void determineHeight(node *tree, int *height)
{
int left_height, right_height;
if( tree == NULL)
*height = 0;
else
{
determineHeight(tree->left, &left_height);
determineHeight(tree->right, &right_height);
if( left_height > right_height)
*height = left_height + 1;
else
*height = right_height + 1;
}
}



void inorder(node *root)
{
if(root==NULL)
return;
else
{
inorder(root->left);
cout<<"  " <<root->info;
inorder (root->right);
}
}
void inorder_e(node *root)
{
if(root==NULL)
return;
else
{
inorder_e(root->left);
if((root->left==NULL)&&(root->right==NULL))
{
 count_e++;
 cout<<" "<<root->info; 
 }                                    
inorder_e(root->right);
}

}
void inorder_i(node *root)
{
if(root==NULL)
return;
else
{
inorder_i(root->left);
if((root->left!=NULL)||(root->right!=NULL))
{
     count_i++;                                      
      cout<<" "<<root->info;  
      }                                   
inorder_i(root->right);
}

}
int main()
{
int ch;
int height=0;
do
{
cout<<"\n press 1 for insertion :"   ;
cout<<"\n press 2 for traversal :"  ;
cout<<"\n press 3 for printing external nodes and internal nodes";
cout<<"\n press 4 for display height of tree:" 
cout<<"\n any key for exit:" ;
cin>>ch;
if(ch==1)
insert();
else if(ch==2)
inorder(root) ;
else
if(ch==3)
     {
     count_e=0;count_i=0;
     cout<<"\n ";
     inorder_e(root);
     cout<<" \n number of external nodes are"<<count_e;
      cout<<"\n ";
     inorder_i(root);
     cout<<" \n number of internal nodes are"<<count_i;

     }
else if(ch==4)
{
determineHeight(root,&height);
cout<<"\n\nHeight of Tree : "<<height<<endl;
}
else
exit(0);
}while((ch==1)||(ch==2)||(ch==3)||(ch==4));
getch();
return 0;
}

Quick Sort

Quick Sort

#include<conio.h>
#include<iostream.h>
quick(int a[],int beg,int end)
{
int loc,left,right,temp;
left=beg;
right=end;
loc=beg;
step2: while((a[loc]<=a[right])&&(right!=loc))
{
right=right-1;
}
if(loc==right)
{
return loc;
}
if(a[loc]>a[right])
{
temp=a[loc] ;
a[loc]=a[right];
a[right]=temp;
loc=right;
}

while((a[loc]>=a[left])&&(left!=loc))
{
left=left+1;
}
if(loc==left)
{
return loc;
}
if(a[loc]<a[left])
{
temp=a[loc] ;
a[loc]=a[left];
a[left]=temp;
loc=left;
}

goto step2;
}
int main()
{
int a[100],n,l[20],u[20];
int top=-1,beg,end,loc;
cout<<"Enter no. element in the list";
cin>>n;
cout<<"enter element in the list:" ;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
top=top+1 ;
l[top]=0;
u[top]=n-1;
if(n<2)
{
cout<<"list is already sorted";
}
else
{
while(top!=-1)
{
beg=l[top];
end=u[top];
top=top-1;
loc=quick(a,beg,end);
if(loc-1>beg)
{
top=top+1;
l[top]=beg;
u[top]=loc-1;
}
if(loc+1<end)
{
top=top+1;
l[top]=loc+1;
u[top]=end;
}
}
}
cout<<"sorted element are:";
for(i=0;i<n;i++)
{
cout <<a[i];
}
getch();
return 0;
}