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)
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