Implementation of Binary Trees
A node of a binary tree can be
represented as:
{
int data;
struct
btree *left ;
struct btree *right
}
Left
|
Data
|
Right
|
Fig: Node of a Binary Tree
In the above structure two pointers of
struct btree type are defined. One points to the left child of this node and
other points to the right child of the node.
Algorithm to implement a Binary Tree
proceed in two phases. The first phase builds a binary tree, and the second
traverses the tree. In the first phase as we read, the number for insertion
into a Binary Tree, is compared with the contents of a node in the tree, a left
branch is taken if the number is smaller than the contents of the node and a
right branch is taken if it is greater or equal to the contents of the node.
Code to implement this is given below:
insert
(struct btree *s, int num)
{ /*s
is a pointer points to the existing tree*/
struct btree *temp, *p;
temp =
malloc(sizeof(struct btree));
temp ->
data =num; temp -> left=temp -> right = NULL;
if(s==NULL)/*if current
tree is input*/
s=temp;
else
{
p=s;
while(p
-> left != NULL && p -> right != NULL)
{
if
(p ->data<=num) //if num is greater
p=p
->right ; //than p data go Right
p=p
->left; // else go left
else
}
if
(p->data <=num)
p->right
=temp;
else
p->left
=temp;
}
}
The
functioning of the above code can be explained through an example. Suppose we have
to make a tree with the following data :
5, 3, 7, 8, 2, 4, 6, 1.
When
5 came the tree was empty hence tree is formed having only one node pointed by
temp and s. Both the child pointers of this node are NULL.
Then
next number is 3. In the while Loop this number is compared with 5 because 5 is
greater than 3, control is moved to the left child of 5 which is NULL. After
exiting from while loop 3, is attached to the left of 5 Next number is 7 which
is greater than 5 hence, it is attached to the right of 5. Proceeding in the
same manner the Binary tree of Fig. below
is produced.
Such
a binary tree has the property that all elements in the left subtree of a node
n are less than the contents of n, and all elements in the right subtree of n
are greater than or equal to the contents of n. Binary Tree with this property
is called a Binary Search Tree.
In
the second phase we can Traverse a Tree in either of the three fashions(ie.
Inorder, Preorder, Postorder). A Recursive
Method can be used to traverse a Binary Tree. The method starts by
checking whether the tree is empty or not. If the tree is not empty i.e. our
pointer s of struct btree type doesn't point to NULL then we will proceed.
Depending upon the desired fashion of traversing, we will call recursively the
traversing function by passing either left child pointer or right child pointer
of the node as an argument. The function to implement this is given below:
/* Inorder Traversing of a Binary
Search Tree */
inorder (struct btree*s)
{
if (s!=NULL)
{
inorder(s->left);
printf("%d",
s->data);
} inorder(s->right);
else
} return;
/*Preorder Traversing of a Binary
Search Tree*/
preorder (struct btree*s)
{
if (s != NULL)
{
printf("%d",s
->data);
preorder(s
->left);
preorder(s
->right);
}
else
return;
}
/* Post order Traversing of Binary
Search Tree */
postorder (struct btree *s)
{
if (s!=NULL)
{
postorder (s
->left);
postorder (s
->left);
} printf("%d", s ->data);
else
return;
}
No comments:
Post a Comment