BINARY TREE and OPERATIONS OF BINARY TREE | Data Structures Tutorial pdf

BINARY TREE:- 

Binary tree is a special form of tree where each node can have at most two child nodes.

OPERATIONS OF BINARY TREE

1.TRAVERSING- Traversing a tree means simply visiting each node of the tree exactly once.different methods are available to traverse a tree.
DEPTH FIRST TRAVERSAL-DFT is based on the idea of processing all descendents of a child node before processing the next child.The dft is classified into three common categories:
=> Preorder traversal
=> Inorder traversal
=> Post order Traverse
Breath first traversal-Breath First Traverse is based on the idea of level processing of nodes i.e. first root is processed then all nodes at level two processed and so on.nodes are processed from left to right.

/*PROGRAM TO TRAVERSE THE BINARY TREE*/

#include<stdio.h>
#include<malloc.h>
struct tree
{
int Info;
struct tree *l_child;
struct tree *r_child;
};
struct tree *create_tree (int , struct tree *);
void display(struct tree *, int );
void pre_order(struct tree *);
void in_order(struct tree *);
void post_order(struct tree *);

/* Function to create a tree */
struct tree * create_tree (int item, struct tree *node)
{
if (node == NULL)
{
node = (struct tree *) malloc( sizeof(struct tree ));
node->Info = item;
node->l_child = NULL;
node->r_child = NULL;
return (node);
}
if (item < node->Info) 
/* Smaller item becomes left child */
node->l_child = create_tree (item, node->l_child);
else
 /* Greater or equal item becomes right child */
node->r_child = create_tree (item, node->r_child);
return(node);
}
 /* Function to display tree */
void display(struct tree *T, int level)
{
int i;
if (T)
{
display(T->r_child, level+1);
printf("\n");
for (i = 0; i < level; i++)
printf("\t");
printf("|----%d", T->Info);
printf("\n");
display(T->l_child, level+1);
}
}

/* Function to perform Pre-order traversal */
void pre_order (struct tree *node)
{
if (node)
{
printf(" %d", node->Info);
pre_order(node->l_child);
pre_order(node->r_child);
}
}

/* Function to perform In-order traversal */
void in_order (struct tree *node)
{
if (node)
{
in_order(node->l_child);
printf(" %d", node->Info);
in_order(node->r_child);
}
}
/* Function to perform Post-order traversal */
void post_order (struct tree *node)
{
if (node)
{
post_order(node->l_child);
post_order(node->r_child);
printf(" %d", node->Info);
}
} 
/* Main Function */
void main()
{
int n,item,i=0;
struct tree *T = (struct tree *) malloc(sizeof(struct tree *));
clrscr();
T = NULL;
printf("\n\n\n -------------------------------------");
printf("\n How many nodes you want to create:");
scanf("%d",&n);
while(i != n)
{
printf("\n\n ----------------------------------");
printf("\n Enter item you want to insert: ");
scanf("%d", &item);
T = create_tree (item, T);
printf("\n\n\t----------");
printf("\n\t Tree is: ");
printf("\n\t----------\n\n");
display(T, 1);
i++;
}
printf("\n\n==========================");
printf("\n\n\n\n\t -------------------");
printf("\n\t Pre-order traversal");
printf("\n\t -------------------\n\n\t");
pre_order (T);
printf("\n\n\n\t -------------------");
printf("\n\t In-order traversal");
printf("\n\t -------------------\n\n\t");
in_order (T);
printf("\n\n\n\t -------------------");
printf("\n\t Post-order traversal");
printf("\n\t -------------------\n\n\t");
post_order (T);
getch();
}