BST insert operation. don't insert a node if a duplicate exists already
- by jeev
the following code reads an input array, and constructs a BST from it. if the current arr[i] is a duplicate, of a node in the tree, then arr[i] is discarded. count in the struct node refers to the number of times a number appears in the array. fi refers to the first index of the element found in the array. after the insertion, i am doing a post-order traversal of the tree and printing the data, count and index (in this order). the output i am getting when i run this code is:
0 0 7
0 0 6
thank you for your help.
Jeev
struct node{
int data;
struct node *left;
struct node *right;
int fi;
int count;
};
struct node* binSearchTree(int arr[], int size);
int setdata(struct node**node, int data, int index);
void insert(int data, struct node **root, int index);
void sortOnCount(struct node* root);
void main(){
int arr[] = {2,5,2,8,5,6,8,8};
int size = sizeof(arr)/sizeof(arr[0]);
struct node* temp = binSearchTree(arr, size);
sortOnCount(temp);
}
struct node* binSearchTree(int arr[], int size){
struct node* root = (struct node*)malloc(sizeof(struct node));
if(!setdata(&root, arr[0], 0))
fprintf(stderr, "root couldn't be initialized");
int i = 1;
for(;i<size;i++){
insert(arr[i], &root, i);
}
return root;
}
int setdata(struct node** nod, int data, int index){
if(*nod!=NULL){
(*nod)->fi = index;
(*nod)->left = NULL;
(*nod)->right = NULL;
return 1;
}
return 0;
}
void insert(int data, struct node **root, int index){
struct node* new = (struct node*)malloc(sizeof(struct node));
setdata(&new, data, index);
struct node** temp = root;
while(1){
if(data<=(*temp)->data){
if((*temp)->left!=NULL)
*temp=(*temp)->left;
else{
(*temp)->left = new;
break;
}
}
else if(data>(*temp)->data){
if((*temp)->right!=NULL)
*temp=(*temp)->right;
else{
(*temp)->right = new;
break;
}
}
else{
(*temp)->count++;
free(new);
break;
}
}
}
void sortOnCount(struct node* root){
if(root!=NULL){
sortOnCount(root->left);
sortOnCount(root->right);
printf("%d %d %d\n", (root)->data, (root)->count, (root)->fi);
}
}
