Page 253 - DCAP407_DATA_STRUCTURE

Data Structure

if(root!=NULL)
{
count_node(root->L);
count++;
count_node(root->R); }
}
return count;
}
In this example:
1. The variable count is a global variable and it is initialized to zero. It is
also declared static so that it retains its value in consequent function
calls.
2. A structure named node is created. It consists of two pointer variables
named L and R that point to the left node and right node.

3. An object called NODE is created to access the structure element.
4. The function count_node is defined and has a parameter root of type
NODE.
5. In the function count_node(),
(a) If root is not NULL, then the number of left nodes is counted by
recursively calling the function and by passing the address of the
left sub-tree. The count variable is also incremented.
(b) Then, the number of right nodes is recursively counted by the
function by passing the address of the right sub-tree. The count
variable is also incremented.

A leaf node is a node that has zero child nodes. To obtain the number of leaves in the tree, visit each
node in the given tree. Whenever a leaf is found, update the count by one. The following example
shows the function to count the leaves in a binary tree.

static count = 0;
struct node
{
int element;
struct node *L;
struct node *R;
};
typedef struct node* NODE;
void count_leaf(NODE root)
{
if(root!=NULL)
{
count_leaf(root->L); // traverses recursively towards left
if (root->L==NULL &&root->R==NULL)
/* if a node has empty left and right child */
count++;
count_leaf(root->R);
/* traverses recursively towards right */
}
}

246 LOVELY PROFESSIONAL UNIVERSITY