Data Structure - [Binary Tree Example]

♠ Posted by Unknown in , at 02:59

The Binary Tree with Example


A tree is a binary tree if each node of it can have at the most two branches. 

A binary tree T is a finite set of nodes, which is either empty or consists of special node called root R and two disjoint binary trees T1 and T2 (which are called the left sub-tree and right sub-trees, respectively). If T1 is non-empty then the root of T1 is called the left successor of R. If T2 is non-empty then the root of T2 is known as right successor of R.

Image: Binary Tree



Recursive algorithm for binary tree creation :


Create_Tree (Info, Node)

Where, 
             Info -> Information for which we have to create node. 
             Node -> structure type variable to points both left and right child.

Step 1: [Check whether the tree is empty]
            If Node = NULL
            Node = Create a node
            Left_Child [Node] = NULL
            Right_Child [Node]] = NULL
Step 2: [Test for the left child]
            If  Info [node] >= Info
            Left_child [Node] = call Create_Tree
(Info, Left_child [Node])
            Else
            Right_child [Node] = call Create_Tree
(info, Right_child [Node])
Step 3: Return (Node)

Recursive algorithm of preorder traversing:


Preorder (Node)

Step 1: [Do through step 3]
            If Node  is not equal to NULL
            Output Info [Node]
Step 2: Call Preorder (Left_child [Node])
Step 3: Call Preorder (Right_child Node])
Step 4: Exit

Recursive algorithm of inorder traversing:

Inorder (Node)

Step 1: [Do through Step 4]
            If  Node is not equal to NULL
Step 2: Call Inorder (Left_Child [Node])
Step 3: Output Info [Node]
Step 4: Call Inorder (Right_child [Node])
Step 5: Exit

Recursive algorithm of postorder traversing:


Postorder (Node)

Step 1: [Do through step 4]
            If Node is not equal to NULL
Step 2: Call Postorder  (Left_Child [Node])
Step 3: Call Postorder (Right_Child Node)
Step 4: Output Info [Node]
Step 5: Exit


Example :

/*program for tree operation*/
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
struct tree
{
   int no;
   struct tree *r,*l;
};
void insert(struct tree *root,int x);
void preorder(struct tree *root);
void inorder(struct tree *root);
void postorder(struct tree *root);
void main()
{
  struct tree *root = NULL;
  int ch=1,x,level,info;
  root=(struct tree *)malloc(sizeof(struct tree));
  clrscr();
  printf("\n enter the value of root:=");
  scanf("%d",&root->no);
  root->l = root->r=NULL;
  while(ch!=0)
  {
    printf("\n 1:inert\t 2:preorder\t 3:inorder\t 4:postorder");
    printf("\t 0:exit");
    printf("\n\n enter the choice:=");
    scanf("%d",&ch);
    switch(ch)
    {
      case 1:
               printf("\n enter the no");
               scanf("%d",&x);
               insert(root,x);
               break;
      case 2:
               preorder(root);
               break;
      case 3:
               inorder(root);
               break;
      case 4:
               postorder(root);
               break;
    }
  }
}//main over

void insert(struct tree *root,int x)
{
    if(x==root->no)
    {
      printf("\n duplicate no \n\n\n");
      return;
    }
    if(x < root->no)
    {
       if(root->l!=NULL)
             insert(root->l,x);
       else
       {
             root->l=(struct tree*)malloc(sizeof(struct tree));
             root->l->no=x;
             root->l->l=root->l->r=NULL;
       }
    }
    else
    {
      if(root->r!=NULL)
            insert(root->r,x);
      else
      {
            root->r=(struct tree*)malloc(sizeof(struct tree));
            root->r->no=x;
            root->r->r=root->r->l=NULL;
      }
    }
}//insert over

void inorder(struct tree *root)
{
  if(root!=NULL)
  {
    inorder(root->l);
    printf("\n %d",root->no);
    inorder(root->r);
  }
}//inorder over

void preorder(struct tree *root)
{
  if(root !=NULL)
  {
    printf("\n %d",root->no);
    preorder(root->l);
    preorder(root->r);
  }
}//preorder over

void postorder(struct tree *root)
{
  if(root!=NULL)
  {
    postorder(root->l);
    postorder(root->r);
    printf("\n %d",root->no);
  }
}//postorder over

0 comments:

Post a Comment