December 7, 2022

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

```