Page 251 - DCAP407_DATA_STRUCTURE

Data Structure

2. An object called NODE is created to access the structure element.
3. Two functions are created namely max and height.
4. The two arguments x and y are compared by the max function, and the
greater number is returned.
5. The value of root is checked by the height function. If root is NULL, 0 is
returned.
6. The max function is recursively called by the height function by passing
the left and right sub-trees as parameters. The value returned by the max
function is incremented and returned.

To Find the Maximum and Minimum Value in a tree
In a binary search tree, a node with maximum value is found by traversing and obtaining the extreme
right node of the tree. If there is no right sub-tree, then the root is returned as the node that holds the
item of the highest value.
The C function to return the address of highest item in binary search tree is shown in the following
example.

struct node
{
int element;
struct node *L;
struct node *R;
};
typedef struct node* NODE;
NODE maximum(NODE root)
{
NODE data;
if(root==NULL)
return root;
data=root;
while(data->R!=NULL)
data=data->R; // find right most node in binary search tree
return data;
}

In this example:
1. 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.
2. An object called NODE is created to access the structure element.
3. The function maximum is defined which accepts the address of the root node
as the parameter.
4. In the function maximum():
(a) A variable data is declared as type NODE.
(b) If root is entered as NULL, then the function returns root. Else, the
value of root is assigned to the variable data.
(c) Using the while loop, the extreme right node in the tree is found and its
address is returned.

244 LOVELY PROFESSIONAL UNIVERSITY