| 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, 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 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. Check out the algo..
Algorithm:-
Step-1: If Value
of New element < current element then go to step-2 or else step-3
Step-2: If the Current element does not have a left sub-tree then make
your new element the left child of the current element; else make the
existing left child as your current element and go to step-1
Step-3: If the current element does not have a right sub-tree then make
your new element the right child of the current element; else make the
existing right child as your current element and go to step-1
C implementation:-
struct NODE
{
struct NODE *left;
int value;
struct NODE *right;
}
create_tree( struct NODE
*curr, struct NODE *new )
{
if(new->value <= curr->value)
{
if(curr->left != NULL)
create_tree(curr->left, new);
else
curr->left = new;
}
else
{
if(curr->right != NULL)
create_tree(curr->right, new);
else
curr->right = new;
}
}
Related Operations:
Trees – concepts
Binary tree creation
Traversals of a binary tree –
preorder, inorder and postorder
Binary threaded tree
Non-recursive implementation of traversals
Expressions-to-Trees
Balanced trees / AVL trees – Creation and Balancing of a binary tree
Balanced m-way tree / B-tree – Creation and balancing
|
