Binary Tree
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 6.10):
struct NODE
{
struct NODE *leftchild;
int nodevalue; /* this can be of any data type */ struct NODE *rightchild;
};
|
left child |
value |
right child |
The ‘left child’and ‘right child’ are pointers to another tree-node. The “leaf node” (not shown) here will have NULL values for these pointers.
Figure 6.10 : Node structure of a binary tree
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 the left, then make your new element as the left child of that current element or else compare it with the existing left child and follow the same rule. Exactly, the same has to done for the case when your new element is greater than the current element in the tree but this time with the right child. Though this logic is followed for the creation of a Binary tree, this logic is often suitable to search for a key value in the binary tree.
