Page 108 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 5: Trees

and deletion in a tree costly. Therefore, instead of using an array representation, we can use a Notes

linked representation, in which every node is represented as a structure with three fields: one for
holding data, one for linking it with the left subtree, and the third for linking it with right subtree
as shown here:
leftchild data rightchild

We can create such a structure using the following C declaration:
struct tnode
{
int data
struct tnode *lchild,*rchild;
};
A tree representation that uses this node structure is shown in Figure 5.7.

Figure 5.7: Linked representation of a Binary Tree

A

B C

NULL NULL NULL
D

NULL NULL

5.4 Implementation of a Binary Tree

Like general tree, binary trees are implemented through linked lists. A typical node in a Binary
tree has a structure as follows (refer to Figure 5.8):

struct NODE
{
struct NODE *leftchild;
int nodevalue; /* this can be of any data type */
struct NODE *rightchild;
};
Figure 5.8: Node Structure of a Binary Tree

The ‘left child’and ‘right child’
left child value right child are pointers to another
tree-node. The “leaf node” (not
shown) here will have NULL
values for these pointers.

The binary tree creation follows a very simple principle. For the new element to be added,
compare it with the current element in the tree. If its value is less than the current element in the
tree, then move towards the left side of that element or else to its right. If there is no sub tree on

LOVELY PROFESSIONAL UNIVERSITY 103