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;
}
