Question

WİTH C LANGUAGE

Write a program that counts the leaves of a given binary tree. Hint: You will make a small (and smart) update to the add function we discussed in class. a) 125 pointsl Create the following binary trees by creating the nodes (malloc) and setting the related pointers (leftChild, rightChild). Make content random. 60 50 40 60 70 30 45 42 b) 125 points Display the trees on screen the way we did in slide 9 using listAll function. You will of course modify it slightly as we do not deal with directories here c 150 pointsl Count the leaves and print the result. Your code will be tested with additional trees as well

Answer 1

PROGRAM :

#include <stdio.h>
#include <stdlib.h>

/*structure of the node -> data|left|right*/
struct node
{
int data;
struct node* left;
struct node* right;
};
struct node *TEMP,*ROOT; //gobal node pointers

/*function to count leaves of left and right subtrees recursively*/

unsigned int countLeaves(struct node* node)
{
if(node == NULL)
return 0;
if(node->left == NULL && node->right==NULL) // leaves have left and right pointers of node set to NULL
return 1;   
else
return countLeaves(node->left)+
countLeaves(node->right);   
}
  
/*function to create new node*/
struct node* newNode(int data)
{
/*initially left and right ointers are ste to NULL */
struct node* node = (struct node*) malloc(sizeof(struct node)); //dynamic allocation of memory
node->data = data;
node->left = NULL;
node->right = NULL;
  
return(node);
}

/* Recursive function to check is a node is present. This is used to check if parent
node to which the child is to be attached is present*/
int isPresent(struct node* root, int x) {
       if (root != NULL) {

           // check if current node has the element we are looking for
           if (root->data == x) {
               TEMP=root;
               return 1;
           } else {
               // check if the sub trees
               return isPresent(root->left, x) || isPresent(root->right, x);
           }
       }
       return 0;
   }
  
  /*to traverse the tree level by level and dispaly the data*/
void displayLevelOrder(struct node* root)
{
int h = height(root); //to determine number of levels
int i;
for (i = 1; i <= h; i++)
{
  dispCurrentLevel(root, i);
printf("\n");
}
}
  
/* Print nodes at a given level */
void dispCurrentLevel(struct node* root, int level)
{
if (root == NULL)
return;
if (level == 1)
printf("%d\t",root->data);
else if (level > 1)
{
dispCurrentLevel(root->left, level-1);
dispCurrentLevel(root->right, level-1);
}
}
  
int height(struct node* node)
{
if (node == NULL)
return 0;
else
{
/* compute the height of left and right subtrees recursively */
int lheight = height(node->left);
int rheight = height(node->right);
  
/* larger one is used*/
if (lheight > rheight)
return(lheight + 1);
else return(rheight + 1);
}
}

void createTree()
{
   int num_c,num_p;
   int temp;
   char ch;
   printf("enter the data of the child node to be inserted: \n");
   scanf("%d",&num_c);
    printf("enter the data of the parent node to be inserted: \n");
   scanf("%d",&num_p);
    temp=isPresent(ROOT,num_p);//check if parent is present
    /*if parent node is not found.*/
   if(temp==0)
   {
       printf("there is no parent node with data %d",num_p);
      
   }
   /*if parent node is found*/
   else
   {
    printf("insert L or R ?: \n");//prompt user whetehr to attach the node to left or rigth of parent node    scanf("%c",&ch);// neglect '\n' when user presses ENTER
   scanf("%c",&ch);
   if(ch=='L' && TEMP->left==NULL)
   {
       TEMP->left=newNode(num_c);//attaching newnode to left of parent
       printf("inserted node %d to the LEFT of parent %d\n",num_c,num_p);
   }
   else if(ch=='R' && TEMP->right==NULL)
   {
       TEMP->right=newNode(num_c);//attaching newnode to right of parent
       printf("inserted node %d to the RIGHT of parent %d\n",num_c,num_p);
   }
   else
   {
       printf("Required position is not empty");
      
   }
  
   }
  
  }
  
int main()
{
  
  int ch,num;
printf("enter the data of root node:\n");
scanf("%d",&num);
ROOT=newNode(num);
printf("press 1 to keep inserting new nodes to tree else press 0\n");
scanf("%d",&ch);
while(ch){
    createTree();
   printf("press 1 to keep inserting new nodes to tree else press 0\n");
scanf("%d",&ch);
}
  
printf("LEVEL ORDER TRAVERSAL\n");
displayLevelOrder(ROOT);
  
/*get leaf count*/
printf("Leaf count of the tree is %d", countLeaves(ROOT));
  
getchar();
return 0;
}