I have the implemented a binary search tree but I also want to make it generic. The code is the following:
typedef struct treeNode {
int data;
struct treeNode *left;
struct treeNode *right;
} treeNode;
and the functions:
treeNode* FindMin(treeNode *node) {
if(node==NULL) {
/* There is no element in the tree */
return NULL;
}
if(node->left) /* Go to the left sub tree to find the min element */
return FindMin(node->left);
else
return node;
}
treeNode * Insert(treeNode *node,int data) {
if(node==NULL) {
treeNode *temp;
temp = (treeNode *)malloc(sizeof(treeNode));
temp -> data = data;
temp -> left = temp -> right = NULL;
return temp;
}
if(data > (node->data)) {
node->right = Insert(node->right,data);
}
else if(data <= (node->data)) {
node->left = Insert(node->left,data);
}
/* Else there is nothing to do as the data is already in the tree. */
return node;
}
treeNode * Delete(treeNode *node, int data) {
treeNode *temp;
if(node==NULL) {
printf("Element Not Found");
}
else if(data < node->data) {
node->left = Delete(node->left, data);
}
else if(data > node->data) {
node->right = Delete(node->right, data);
}
else {
/* Now We can delete this node and replace with either minimum element
in the right sub tree or maximum element in the left subtree */
if(node->right && node->left) {
/* Here we will replace with minimum element in the right sub tree */
temp = FindMin(node->right);
node -> data = temp->data;
/* As we replaced it with some other node, we have to delete that node */
node -> right = Delete(node->right,temp->data);
}
else {
/* If there is only one or zero children then we can directly
remove it from the tree and connect its parent to its child */
temp = node;
if(node->left == NULL)
node = node->right;
else if(node->right == NULL)
node = node->left;
free(temp); /* temp is longer required */
}
}
return node;
}
void PrintInorder(treeNode *node) {
if (node != NULL) {
PrintInorder(node->left);
printf("%d ",node->data);
PrintInorder(node->right);
}
}
First thing is to change in the struct
int data;
to
void *data;
Edited with more code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct treeNode {
void *data;
struct treeNode *left;
struct treeNode *right;
}treeNode;
treeNode * Insert(treeNode *node, void *data, int sizeOfType, int (*compare) (void *arg1, void *arg2)) {
if(node==NULL) {
treeNode *temp;
temp = malloc(sizeof(*temp));
temp->data = malloc(sizeOfType);
memcpy(temp->data, data, sizeOfType);
temp -> left = temp -> right = NULL;
return temp;
}
if(compare(data, node->data) == 1) {
node->right = Insert(node->right, data, sizeof(int), compare(data, node->data));
}
else if(compare(data, node->data) == -1 || compare(data, node->data) == 0) {
node->left = Insert(node->left, data, sizeof(int), compare(data, node->data));
}
return node;
}
void print(void* a) {
printf("%d ",*(int*)a);
}
void InorderGeneric(treeNode *node, void(*p)(void *)) {
if (node != NULL) {
InorderGeneric(node->left, p);
p(node->data);
InorderGeneric(node->right, p);
}
}
int int_sorter( void *first_arg, void *second_arg ) {
int first = *(int*)first_arg;
int second = *(int*)second_arg;
if ( first < second ) {
return -1;
}
else if ( first == second ) {
return 0;
}
else {
return 1;
}
}
int main(void) {
treeNode *root = NULL;
int item;
void *v;
printf("Add nodes in binary tree:\n");
while (scanf("%d ", &item) == 1) {
v = &item;
root = Insert(root, v, sizeof(int), int_sorter);
}
printf("\n---Initial tree---\n");
printf("IN-order walk of tree:\n");
InorderGeneric(root, print);
printf("\n");
return 0;
}
You're going to need to create a comparison function for each data type that's used and pass a function pointer to each function that needs to know if two pieces of data are equal or greater/less than each other. Only this function will have to know the internal data type.
This function would look like:
int compare_X(const void *d1, const void *d2)
And the function should return 0 if the two objects are equal, less than 0 if the object pointed to by d1 is smaller, or greater than 0 otherwise. You would have a range of these functions, such as compare_int
, compare_double
, etc, depending on the type of data you're storing in a specific tree.
You would then add this argument to the functions the need to compare two objects:
int (*cpm_fptr)(const void *, const void *)
Now for example in Insert
, if(data > (node->data))
would become:
if (cmp_fptr(data, node->data) > 0) /* data > node->data */
Also:
if (cmp_fptr(data, node->data) == 0) /* data == node->data */
if (cmp_fptr(data, node->data) < 0) /* data < node->data */
The signature of Insert
would now look like:
treeNode * Insert(treeNode *node, int data,
int (*cpm_fptr)(const void *, const void *))
And if your internal type was int
, you might call it like:
Insert(node, my_int, compare_int);
This is how functions like bsearch
and qsort
are able to operate on data of any type.
You may use a union
to represent the data you want to store, along with information of the type the union represents at any time. Something like below:
typedef struct _generic_data {
union {
int i; /* Integer */
long l; /* Long */
float f; /* floating point */
double d; /* double precision floating point */
char c; /* char */
char *s; /* c string */
struct {
void *blob; /* Arbitrary blog of binary data */
int size; /* Size of this blob */
} b; /* You may not really need it
* So you can get rid of this struct
* if you want.
*/
} value; /* To access the above values */
int type_id; /* To identify which data type is actually
* being stored in this generic data struct
*/
} generic_data;
Of course you should also have the corresponding unsigned
types for the above types too for completeness sake. Set type_id
to distinctly identify elements. For example:
const int char_type_id = 1;
const int long_type_id = 2;
....
const int blob_type_id = 10;
const int error_type_id = -42;
and so on, so that the following holds for generic_data gd;
gd.type_id == char_type_id
, then gd.value.c
is the valid value.So now, your Node
would look like:
typedef struct treeNode {
generic_data* data;
struct treeNode *left;
struct treeNode *right;
} treeNode;
You would need to modify your functions as
treeNode * Insert(treeNode *node, generic_data* data);
treeNode * Delete(treeNode *node, generic_data* data);
You would also need a function which is able to compare between two generic_data
values. Something like this:
long compare_generic(generic_data* lhs, generic_data* rhs) {
if ( lhs == NULL || rhs == NULL ) {
return error_type_id;
}
if ( lhs->type_id != rhs->type_id ) {
/*
* ERROR: Trying to compare two different types.
* Do appropriate error handling here.
* return some eror code.
*/
return error_type_id;
}
switch( lhs->type_id ) {
case char_type_id: return (long)(lhs->value.c - rhs.value.c); break;
case int_type_id: return (long)(lhs->value.i - rhs.value.i); break;
/*
* Something similarly logical for long, float, double.
* The basic idea if this function returns 0
*
* void *blob allows you to store arbitrary binary data. You
* may not need it, but if you do, there should be some way to
* compare between the two.
*/
default:
/*
* No type_id matches.
* Handle this error case.
* return some error code.
*/
return error_type_id;
break; /* Just a habbit to always have a break so that
* you don't have to deal with special cases.
*/
}
}
This would be used to replace your existing code as below:
if(data < node->data)
to this : if ( compare_generic( data, node->data ) < 0 )
if(data > node->data)
to this : if ( compare_generic( data, node->data ) > 0 )
if(data == node->data)
to this : if ( compare_generic( data, node->data ) == 0 )
You would now have to be extra careful in accessing your values.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With