In link list we saw the method of traversing the list from one node to another. One of the better way to access the same thing one step towards by decreasing the work required to traverse a list to subdivided the list into two "SUBLISTS". One of these would contain the "LARGE" values, the other would contain the "small" values. Both of these sublists can be stored when you had new element to add So you could decide whether the element to a sublists is about half of the original list can save considerable time.
DEFINITION
Trees are common data structures for such an approach in terms of sublists. Linked lists, trees uses the nodes that contains both information and pointers to other nodes. In a linked list each node pointed to exactly one other node. In the same one node may be pointed to the other nodes of the same type. As with linked list the node like the tree is the type of node. This can be referred as the root of the tree.
Binary Tree and its applications
A B'tree is a useful data structure when two-way decisions must be made at each point in a process. Suppose, that we wanted to find all duplicates in a list of numbers, on way of doing this to compare two no's with all those that processed it. However, this involves a large no of comparisons.
Another common operation of B'tree is to traverse a B'Tree, that is to pass through the tree, enumerating each of it's node once.
Picture of a Binary Tree
TREE TRAVERSAL methods
1. Preorder Traversing – Root, Left, Right
1. Visit Root
2. Left Sub Tree in Preorder
3. Right Sub Tree in Preorder
2. Inorder Traversing –Left, Root, Right
1. Left Sub Tree in inorder
2. Visit Root
3. Right Sub Tree in inorder
3. Postorder Traversing –Left, Right, Root
1. Left Sub Tree in postorder
2. Right Sub Tree in postorder
3. Visit Root
/* Binary Tree Implementation and traversing Methods */
struct tree
{
int data;
struct tree *left,*right;
};
typedef struct tree node;
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
#include<stdlib.h>
node *tree;
node *create(node*, int);
void preorder(node*);
void inorder(node*);
void postorder(node*);
int search(node*, int);
void total(node*, int*);
void main()
{
int ch,ele,key,flag,tp;
clrscr();
tree=NULL;
do
{
clrscr();
gotoxy(30,1); printf("1. Create");
gotoxy(30,2); printf("2. Preorder");
gotoxy(30,3); printf("3. Inorder");
gotoxy(30,4); printf("4. Postorder");
gotoxy(30,5); printf("5. Search");
gotoxy(30,6); printf("6. Total");
gotoxy(30,7); printf("7. Exit");
gotoxy(30,9); printf("Enter Your Chocie :");
scanf("%d", &ch);
switch(ch)
{
case 1:
printf("\n Enter Element to insert or (0 to Stop) :\n");
scanf("%d", &ele);
while(ele!=0)
{
tree=create(tree,ele);
scanf("%d", &ele);
}
getch();
break;
case 2:
printf("\n Preorder of the tree is.........\n");
preorder(tree);
getch();
break;
case 3:
printf("\n Inorder of the tree is.........\n");
inorder(tree);
getch();
break;
case 4:
printf("\n Postorder of the tree is........\n");
postorder(tree);
getch();
break;
case 5:
printf("\n Enter Element to be search :");
scanf("%d", &key);
flag=search(tree,key);
if(flag==0)
printf("\n No such element");
else
printf("\n Element is present");
getch();
break;
case 6:
tp=0;
total(tree,&tp);
printf("\n Total Number of Nodes :%d", tp);
getch();
break;
case 7:
exit(0);
default :
printf("\n Invalid Chocie");
getch();
}
}while(1);
getch();
}
node *create(node *t, int ele)
{
if(!t)
{
t=(node*)malloc(sizeof(node));
t->data=ele;
t->left=NULL;
t->right=NULL;
return(t);
}
if(ele<t->data)
t->left=create(t->left,ele);
if(ele>t->data)
t->right=create(t->right,ele);
return(t);
}
void preorder(node *t)
{
if(t)
{
printf("%d\t", t->data);
preorder(t->left);
preorder(t->right);
}
}
void inorder(node *t)
{
if(t)
{
inorder(t->left);
printf("%d\t", t->data);
inorder(t->right);
}
}
void postorder(node *t)
{
if(t)
{
postorder(t->left);
postorder(t->right);
printf("%d\t", t->data);
}
}
int search(node *t, int key)
{
if(!t)
return(0);
else if(key==t->data)
return(1);
else if(key<t->data)
return(search(t->left,key));
else
return(search(t->right,key));
}
void total(node *t, int *count)
{
if(t)
{
(*count)++;
total(t->left, count);
total(t->right,count);
}
}
No comments:
Post a Comment