Binary tree
A tree is a finite set of nodes having a distinct node
called root.
Binary Tree is a tree which is either empty or has at most two subtrees,
each of the subtrees also being a binary tree. It means each node in a binary
tree can have 0, 1 or 2 subtrees. A left or right subtree can be empty.
A binary tree is made of nodes, where each node contains a
"left" pointer, a "right" pointer, and a data element. The
"root" pointer points to the topmost node in the tree. The left and
right pointers point to smaller "subtrees" on either side. A null
pointer represents a binary tree with no elements -- the empty tree. The formal
recursive definition is: a binary tree is either empty (represented by a null
pointer), or is made of a single node, where the left and right pointers
(recursive definition ahead) each point to a binary tree.
Representation of Binary
Tree
The
structure of each node of a binary tree contains one data field and two
pointers, each for the right & left child. Each child being a node has also
the same structure.
Struct
node
{
struct node *lc ; /* points to the left child */
int data; /* data field */
struct node *rc; /* points to the right child */
}
1. Array Representation of Binary Tree:
A single array can be used to represent a binary tree.
For these nodes are numbered / indexed according to a scheme
giving 0 to root. Then all the nodes are numbered from left to right level by
level from top to bottom. Empty nodes are also numbered. Then each node having
an index i is put into the array as its ith element.
In the figure shown below the nodes of binary tree are
numbered according to the given scheme.
The figure shows how a binary tree is represented as an
array. The root 3 is the 0 th element while its left child 5 is the 1 st
element of the array. Node 6 does not have any child so its children ie 7 th
& 8 th element of the array are shown as a Null value.
It is found that if n is the number or index of a node, then
its left child occurs at (2n + 1) th position & right child at (2n + 2) th
position of the array. If any node does not have any child, then null value is
stored at the corresponding index of the array.
/* Prorgram to implement the above array representation * /
Struct node
{
struct node * lc;
int data;
struct node * rc;
};
struct node * buildtree(int); /* builds the tree*/
void inorder(struct node *); /* Traverses the tree
in inorder*/
int a[]={
3,5,9,6,8,20,10,/0,/0,9,/0,/0,/0,/0,/0,/0,/0,/0,/0,/0,/0};
void main( )
{
struct node * root;
root= buildtree(0);
printf(“\n Inorder Traversal”);
inorder(root);
getch( );
}
struct node * buildtree(int n);
{
struct node * temp=NULL;
if( a[n] != NULL)
{
temp = (struct node *) malloc(sizeof(struct node));
temp-> lc=buildtree(2n + 1);
temp-> data= a[n];
temp-> rc=buildtree(2n + 2);
}
return temp;
}
void inorder(struct node * root);
{
if(root != NULL)
{
if(root!= NULL)
{
inorder(root-> lc);
printf(“%d\t”,root->data);
inorder(root->rc);
}
}
Courtesy : NPTEL
