Friday 14 September 2012

Program to create a binary tree of integers,Traversing the above binary tree in preorder, inorder and post order

Description:  The data structure tree is of non linear type. Binary tree is bit special. The proparty of a binary tree is the value at the root must be grater than the left node and less than the right node. The binary tree consist of almost two childrens. Tree is a recursive data structure and recursive programming techniques are popularly used in trees. A tree can can be traversed in three major ways
i)                    Inorder traversal: here left child is visited first followed by root and finally by right child.
ii)                  Preorder traversal: Here root is visitedfirst follwed by left child and finally by right child.
iii)                Postorder traversal: Here left child is visited first followed by  right child finally by the root.
ALGORITHM:

Step 1: Start

Step 2: Define a structure btree

Step 3: Type define struct btree as  node

Step 4: While(tree), begin

Step 5: Print MENU

Step 6: Write your choice

Step 7: If choice=1

Step 8: Enter your no of nodes

Step 9:Read nodes n

Step 10: for i=1 to n in steps of 1 do

Step 11: Print enter item

Step 12: Read item

Step 13: Root =call create (root, item).end for

Step 14: if choice=2

Step15: Read element to be deleated

Step 16: Call delete(root, item) end for

Step 17: If choice=3

Step 18: Call preorder(root)

Step 19: Call postorder(root)

Step 20: Call inorder(root)

Step 21: Break, end of switch

Step 22: Stop
             
For insert function

Step 1: Start

Step 2: If t= null

Step 3: Allocate memory to temp

Step 4: Temp->data =item

Step 5: Temp-> lc=null

Step 6: Temp->rc=null

Step 7: return t to main and end

Step 8: If item< (l->data)

Step 9: T->lc=call insert(e->lc, t)

Step 10: T->rc=call isert(e->lc,t)

Step 11:Return t

Step 12: Stop

For  DELETION  function

Step 1: Start

Step 2: x=d

Step 3: while x!=null

Step 4: If x->data =t

Strep 5:Break

Step 6: Parent =x

Step 7: if t<x->data

Step 8: t=tàlc

Step 9: t=làrc

Step 10: If xàlc!=null &&xàrc!=null

Step11: parent =x

Step12: If parent==null

Step 13: parentàlc==null

Step 14: parentàrc==null

Step 15: If p->lc=x->rc

Step 16: If p->rc=x->rc

Step 17: While insert->lc=null

Step 18: Insert=insert->la

Step 19:x->data=insert->data

Step 20:x=insert

Step 21: Return d

Step 22: Stop

For  INORDER function

Step 1: Start

Step 2: If t!=null

Step 3: Call inorder(t->lc)

Step 4: Write t->data

Step 5: Call inorder(t->rc)

Step 6: Stop








For  POSTORDER function

Step 1: Start

Step 2: If t!=null

Step 3: Call postorder(t->lc)

Step 4: Call postorder(t->rc)

Step 5: Write data

Step 6: Stop

For PREORDER function

Step 1: Start

Step 2: If t!=null

Step 3: Write data

Step 4: Call postorder(t->lc)

Step 5: Call postorder(t->rc)

Step 6: Stop
Program:

#include<stdio.h>
#include<alloc.h>
struct bstnode
{
int data;
struct bstnode *lc,*rc;
}*root,*a[20],*b[20];
int top=-1,top1=-1,n,i;
main()
{
int ch,ele;
struct bstnode *t,*insert(),*pop();
clrscr();
t=root=NULL;
while(1)
{
printf("\n **** M E N U **** \n");
printf("1.INSERT\n2.RECURSSIVE TRAVERSE\n3.NON-RECURSIVE TRAVERSE\n4.EXIT\n");
printf("Enter your choice: ");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("Enter how many elements u want to insert:");
            scanf("%d",&n);
            printf("Enter tree elements: ");
            for(i=1;i<=n;i++)
            {
            scanf("%d",&ele);
            t=insert(t,ele);
            }
            break;
case 2: /*  RECURSSIVE TRAVERSE  */
            if(t==NULL)
            printf("**** TREE IS EMPTY ****");
            else
            {
            printf("INORDER   :");
            inorder(t);
            printf("\nPREORDER  :");
            preorder(t);
            printf("\nPOSTORDER :");
            postorder(t);
            }
            break;
case 3: /*  NON-RECURSSIVE TRAVERSE  */
            if(t==NULL)
            printf("TREE IS EMPTY");
            else
            {
        printf("INORDER :");
            nrinorder(t);
            printf("\nPREORDER :");
            nrpreorder(t);
            printf("\nPOSTORDER :");
            nrpostorder(t);
            }
            break;
case 4:
            exit();
}
}
}
struct bstnode *insert(struct bstnode *x,int y)
{
            if(x==NULL)
            {
            x=malloc(sizeof(struct bstnode));
            x->data=y;
            x->lc=NULL;
            x->rc=NULL;
            }
            else
            {
            if(y<x->data)
            x->lc=insert(x->lc,y);
            else
            x->rc=insert(x->rc,y);
            return(x);
            }
}
inorder(struct bstnode *x)
{
            if(x!=NULL)
            {
            inorder(x->lc);
            printf("%3d",x->data);
            inorder(x->rc);
            }
}
preorder(struct bstnode *x)
{
            if(x!=NULL)
            {
            printf("%3d",x->data);
            preorder(x->lc);
            preorder(x->rc);
            }
}
postorder(struct bstnode *x)
{
            if(x!=NULL)
            {
            postorder(x->lc);
            postorder(x->rc);
            printf("%3d",x->data);
            }
}
nrinorder(struct bstnode *x)
{
struct bstnode *l;
l=x;
do
{
            while(l!=NULL)
            {
            push(l);
            l=l->lc;
            }
            while(top>-1)
            {
                        l=pop();
                        printf("%d",l->data);
                        if(l->rc!=NULL)
                        {
                        l=l->rc;
                        break;
                        }
                        else
                        l=NULL;
            }
}while(l!=NULL);
}
nrpreorder(struct bstnode *x)
{
struct bstnode *l;
l=x;
            do
            {
            printf("%d",l->data);
            if(l->rc!=NULL)
            push(l->rc);
            l=l->lc;
            if(l==NULL&&top>-1)
            l=pop();
            }while(l!=NULL);
}
nrpostorder(struct bstnode *x)
{
  struct bstnode *l;
  l=x;
  do
  {
            while(l!=NULL)
            {
                        push(l);
                        if(l->rc!=NULL)
                        {
                        push(l->rc);
                        b[++top1]=l->rc;
                        }
                        l=l->lc;
            }
            do
            {
            l=pop();
            if(l!=b[top1])
            printf("%3d",l->data);
            else
            {
            top1-=1;
            break;
            }
            } while(top>-1);
  }while(l!=NULL&&top>-1);
}
push(struct bstnode *y)
{
top+=1;
a[top]=y;
}
struct bstnode *pop()
{
return a[top--];
}

Input/Output:


Enter your choice
1.Insert  2.Delete 3.Traversal
Enter the element 92
Enter your choice
1. Insert  2.Delete 3. Traversal
Enter the element 26
Enter your choice
1.Insert  2.Delete 3.Traversal
Enter the element 12
Enter your choice
1.Insert  2.Delete 3.Traversal
Enter the element 123
Enter your choice
1.Insert  2.Delete 3.Traversal
Enter the element 135
Enter your choice
1.Insert  2.Delete 3.Traversal
Enter the element 128
Enter your choice
1.Insert  2.Delete 3.Traversal
3
InorderSequence:   12 26 92 123 128 135
Preorder sequence:92 26 12 123 135 128
Postorder sequence: 12 26 128 135 12 92
Conclusion: the program is error free.



VIVA QUESATIONS:

1) Define Binary tree ?
Ans:  Binary tree is a bit special, because whan they are in the sorted form, they facilitate quick search, insertion, and deletion.
2) How many ways a tree can be traversed ?
Ans: In three ways. They are  i) In-order  ii) pre-order iii) post-order
3) define graph ?
Ans: A graph is a set of nodes(vertices) and a set of arcs(edges). A graph is connected if there is a path between any two nodes of the graph.

 

No comments:

Post a Comment