DS (II) Assignment 1: Set A- b)

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;   
        }
    }
}
 
Library Function ( .h file )
NOTE: save file name as ' btree.h'.
 
 
#include<stdio.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));   
}

0 Comments:

Post a Comment