b) Write a program which uses binary search tree library and counts the total nodes and total leaf nodes in the tree.
int count(T) – returns the total number of nodes from BST
int countLeaf(T) – returns the total number of leaf nodes from BST
Solution:
#include<stdio.h>
#include"BST.h"
void main()
{
struct node *root, *temp;
int ch,count, val;
root=NULL;
while(1)
{
printf("\nBST OPERATIONS ---");
printf("\n1 - Create BST\n");
printf("2 - Count Leaf Node\n");
printf("3 - Count NonLeaf Node\n");
printf("4 - Count Total Nodes\n");
printf("5 - Exit\n");
printf("\nEnter your choice : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
while(1)
{
printf("\nEnter The data");
scanf("%d", &val);
if(val==0)
break;
else
{
root=create(root, val);
}
}
break;
case 2:
val=countL(root);
printf("\nLeaf Nodes In The Tree Are\t%d\n",val);
break;
case 3:
val=countNL(root);
printf("\nNonLeaf Nodes In The Tree Are\t%d\n",val);
break;
case 4:
val=countAll(root);
printf("\nTotal Nodes In The Tree Are\t%d\n",val);
break;
case 7:
exit(0);
default :
printf("Wrong choice, Please enter correct choice ");
break;
}
}
}
#include"BST.h"
void main()
{
struct node *root, *temp;
int ch,count, val;
root=NULL;
while(1)
{
printf("\nBST OPERATIONS ---");
printf("\n1 - Create BST\n");
printf("2 - Count Leaf Node\n");
printf("3 - Count NonLeaf Node\n");
printf("4 - Count Total Nodes\n");
printf("5 - Exit\n");
printf("\nEnter your choice : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
while(1)
{
printf("\nEnter The data");
scanf("%d", &val);
if(val==0)
break;
else
{
root=create(root, val);
}
}
break;
case 2:
val=countL(root);
printf("\nLeaf Nodes In The Tree Are\t%d\n",val);
break;
case 3:
val=countNL(root);
printf("\nNonLeaf Nodes In The Tree Are\t%d\n",val);
break;
case 4:
val=countAll(root);
printf("\nTotal Nodes In The Tree Are\t%d\n",val);
break;
case 7:
exit(0);
default :
printf("Wrong choice, Please enter correct choice ");
break;
}
}
}
Library Function ( .h file )
NOTE: save file name as ' btree.h'.
NOTE: save file name as ' btree.h'.
#include<malloc.h>
struct node
{
int data;
struct node *left, *right;
};
struct node *create(struct node *root, int x)
{
if(root==NULL)
{
root=(struct node*)malloc(sizeof(struct node));
root->data=x;
root->left=root->right=NULL;
return(root);
}
else if(x<root->data)
{
root->left=create(root->left, x);
}
else
root->right=create(root->right, x);
return(root);
}
int countL(struct node *root)
{
int c=0;
if(root==NULL)
{
return(0);
}
if(root->left==NULL && root->right==NULL)
return(1);
c=countL(root->left)+countL(root->right);
return(c);
}
int countAll(struct node *root)
{
int c=0;
if(root==NULL)
{
return(0);
}
c=1+countAll(root->left)+countAll(root->right);
return(c);
}
int countNL(struct node *root)
{
int c=0;
if(root==NULL)
{
return(0);
}
if(root->left==NULL && root->right==NULL)
return(0);
//countL(root->left)+countL(root->right);
return(1+countNL(root->left)+countNL(root->right));
}
{
int c=0;
if(root==NULL)
{
return(0);
}
if(root->left==NULL && root->right==NULL)
return(1);
c=countL(root->left)+countL(root->right);
return(c);
}
int countAll(struct node *root)
{
int c=0;
if(root==NULL)
{
return(0);
}
c=1+countAll(root->left)+countAll(root->right);
return(c);
}
int countNL(struct node *root)
{
int c=0;
if(root==NULL)
{
return(0);
}
if(root->left==NULL && root->right==NULL)
return(0);
//countL(root->left)+countL(root->right);
return(1+countNL(root->left)+countNL(root->right));
}
0 Comments:
Post a Comment