4.
6 Counting the Total Nodes in a Tree
in order to count the total number of nodes in a tree, we have to traverse the tree such that each node-
is visited. Any one of the traversal methods can be used for this
element, a counter has to be
purpose. Instead of displaying the
incremented. Since the function is a recursive function, the counter must
be declared 'static'.
as
int
countnodes (NODE* Ioot) N u
mbe
static int count =0;
NODE *temp =
root Oct. 2015-3M suo
Suo
if (temp! =
NULL) Write 'C' function to
display the data of leaf
COunt++; nodes of a binary search
countnodes ( temp- >left) ; tree and also display the
countnodes (temp- >right) total number of leaf
nodes.
return count;
4.7 Counting the Leaf Nodes of a Tree
A leaf node is node, which has
no children.
method can be used. If the node does not To count the leaf nodes of a tree, any tree traversal
int have a left and
countleaf (NODE* root)
a
right child, a counter should be
static int leaf = 0
NODE * temp =
IOot;
if (temp! =NULL)
if ( (temp- >left==NULL) &&
leaf++; (temp- >right= =NULL))
countleaf (temp- >left);
Data Structures
UsingC 7 25 Trees SION
countleaf (temp- >right);
return leaf;
hove function can be modified to count the non leaf nodes (internal nodes). A node is non-leaf
nToit has atleast one child node. The condition can be modified as:
sF ((temp->left! =NULL) I(temp ->right!=NULL) )
Count++;
Copying a Tree
4.8
Copying a binary tree creates an exact image of the tree. This can be performed by a recursive
method.
method. We will start from root of treel. If the root is NULL, NULL is returned as the copied tree.
If it exists, a new node is created and it becomes the root of the new tree. If root has a left child, a
left child is created for the new tree. The same applies for the right child. The process continues till
the entire tree is copied.
Thefunction is as follows.
NODE treecopy (NODE *Ioot)
NODE * newnode;
if (root! =NULL)
newnode = (NODE *)malloc (sizeof (NODE) )
newnode->info = root->info;
newnode- >left = treecopy (root->left) ;
newnode - >right = treecopy (root - > r i g h t ) ;
return (newnode);
else
return NULL;
Given Tree
4.10 Mirroring a
interchanged as
shown
sub-trees
tree contains its left and right
The mirror image of a
(10
10
20 6
6 (20
(30) (30)
2 9
Mirror
Original tree
Mirror ofa Tree
children of each node have to be interchanged.
In order to mirror a tree, the left and right
This can be done by the following recursive junction.
void mirror (NODE Ioot)
NODE *temp = root, *temp1;
if (temp! =NULL)
i f (temp->left ! =NULL)
mirror (temp- >left) ;
if (temp - >right! =NULL)
mirror (temp->right);
/* interchange */
temp1 = temp->left;
temp->left = temp->right;
temp-right = temp1;
