A Binary Search is such a Binary Tree in which the info field of any of the nodes to the left of a particular node nd will be < that of nd and of those to the right of nd will be >= nd. The in-order traversal of such a tree will give the sorted form of the original file.

Below is a simple implementation of Binary Search in C to find duplicates in a file. I have included full code for your ease, sample test scenario, Binary Tree Traversal and output. As a tip and food for thought to the students .. implement and include intrav(PTREE) to the last of main() to implement a Binary Tree Sort process!

# include <stdio.h>
# include <stdlib.h>
struct nodetype{
int info;
struct nodetype * left;
struct nodetype * right;
};
typedef struct nodetype * NODEPTR;
main(){
NODEPTR maketree(int);
void setleft(NODEPTR p, int);
void setright(NODEPTR p, int);
NODEPTR p,q,PTREE, int num;
printf("Enter original file of integers>");
/*scans first number*/
scanf("%d",&num);
PTREE = maketree(num); /*make num the root node*/
while(scanf("%d", &num) != EOF){
p = q = PTREE; /*p,q always initialized to root node for checking*/
while(q != NULL){
p = q;
if(num < p->info)
q = p->left;
else
q = p->right;
}
if(num < p->info)
setleft(p,num);
else{
if(num == p->info)
printf("\n%d is a duplicate",num);
setright(p,num);
}
}
}
NODEPTR maketree(int x){
NODEPTR getnode (void); NODEPTR p;
p = getnode();
p->info = x;
p->left = p->right = NULL;
p->father = NULL;
return(p);
}
NODEPTR getnode(void){
return((NODEPTR) malloc(size of struct nodetype));
}
void setright(NODEPTR p, int x){
NODEPTR maketree(int);
if(p == NULL)
printf("\nVoid insertion\n");
elseif(p->right != NULL)
printf("\nInvalid insertion\n");
else
p->right = maketree(x);
return;
}
void setleft(NODEPTR p, int x){
NODEPTR maketree(int);
if(p == NULL)
printf("\nVoid insertion\n");
elseif(p->left!= NULL)
printf("\nInvalid insertion\n");
else
p->left= maketree(x);
return;
}

/*END Program Binary Search*/

Sample Input:

Enter original file of integers>12 13 12 10 9 6 13 10
Binary Tree formed:
12
/ \
10 13
/ \ / \
9 10 12 13
/
6
Inorder Tree Traversal:
6 9 10 10 12 12 13 13
OUTPUT:
10 is a duplicate
12 is a duplicate
13 is a duplicate