C中的通用二叉搜索树
我已经实现了二叉搜索树，但我也想让它变得通用。 代码如下：
typedef struct treeNode { int data; struct treeNode *left; struct treeNode *right; } treeNode; 和function：
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 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 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); } }
首先是改变结构
int data;
至
void *data;
编辑更多代码：
#include #include #include 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; }
您将需要为所使用的每种数据类型创建一个比较函数，并将函数指针传递给每个需要知道两个数据是否相等或更大/更小的函数。 只有这个function必须知道内部数据类型。
这个function看起来像：
int compare_X(const void *d1, const void *d2)
如果两个对象相等，则函数应返回0，如果d1指向的对象小于0，则返回小于0，否则返回大于0。 您将拥有一系列这些函数，例如compare_int ， compare_double等，具体取决于您在特定树中存储的数据类型。
然后，您将此参数添加到需要比较两个对象的函数中：
int (*cpm_fptr)(const void *, const void *)
现在例如在Insert ， if(data > (node->data))将成为：
if (cmp_fptr(data, node->data) > 0) /* data > node->data */
也：
if (cmp_fptr(data, node->data) == 0) /* data == node->data */ if (cmp_fptr(data, node->data) < 0) /* data < node->data */
Insert的签名现在看起来像：
treeNode * Insert(treeNode *node, int data, int (*cpm_fptr)(const void *, const void *))
如果您的内部类型是int ，您可以将其称为：
Insert(node, my_int, compare_int);
这就是bsearch和qsort等函数能够对任何类型的数据进行操作的方式。
您可以使用union表示要存储的数据，以及联合在任何时候表示的类型的信息。 如下所示：
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;
当然，为了完整起见，您也应该为上述类型提供相应的unsigned类型。 设置type_id以清楚地标识元素。 例如：
const int char_type_id = 1; const int long_type_id = 2; .... const int blob_type_id = 10; const int error_type_id = -42;
等等，以便适用于generic_data gd;
- 当
gd.type_id == char_type_id，则gd.value.c是有效值。 - 其他类型也是如此。
所以现在，你的Node看起来像：
typedef struct treeNode { generic_data* data; struct treeNode *left; struct treeNode *right; } treeNode;
您需要将您的function修改为
treeNode * Insert(treeNode *node, generic_data* data); treeNode * Delete(treeNode *node, generic_data* data);
您还需要一个能够在两个generic_data值之间进行比较的函数。 像这样的东西：
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. */ } }
这将用于替换您现有的代码，如下所示：
-
if(data < node->data)到：if ( compare_generic( data, node->data ) < 0 ) -
if(data > node->data)到：if ( compare_generic( data, node->data ) > 0 ) -
if(data == node->data)to this：if ( compare_generic( data, node->data ) == 0 )
您现在必须格外小心地访问您的值。
如果你真的希望它在C中，你需要一个更复杂的方法（将树中的数据类型存储在变量中，并在必要时执行类型转换）。
但是，如果您决定在C ++中执行相同操作，则可以使用模板。 网上提供的模板有很多例子。
希望这可以帮助！