用C通用二叉搜索树 [英] Generic binary search tree in C
本文介绍了用C通用二叉搜索树的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我已经实现的二叉搜索树，但我也想使它通用。在code是以下内容：
typedef结构treeNode节点{
int数据;
结构treeNode的*离开;
结构treeNode的*权利;
} treeNode节点;
和功能：
treeNode的* FindMin（treeNode的节点*）{
如果（节点== NULL）{
/ *有树没有元素* /
返回NULL;
}
如果（与于节点GT;左）/ *转到左子树找到最小元素* /
返回FindMin（与于节点GT;左）;
其他
返回节点;
}treeNode的*插入（treeNode的节点*，int数据）{
如果（节点== NULL）{
treeNode的*温度;
TEMP =（treeNode的*）malloc的（的sizeof（treeNode节点））;
温度 - ＆GT;数据=数据;
温度 - ＆GT;左=温度 - ＆GT;右= NULL;
返回温度;
} 如果（数据＆GT;（＆于节点GT;数据））{
与于节点GT;右=插入（与于节点的GT;右，数据）;
}
否则，如果（数据＆LT; =（＆于节点GT;数据））{
与于节点GT;左=插入（与于节点GT;左，数据）;
}
/ *否则没有什么做的数据已经在树中。 * /
返回节点;
}treeNode的*删除（treeNode的节点*，int数据）{
treeNode的*温度;
如果（节点== NULL）{
的printf（找不到元素）;
}
否则，如果（数据＆LT;＆于节点GT;数据）{
与于节点GT;左=删除（＆于节点GT;左，数据）;
}
否则，如果（数据＆GT;及于节点GT;数据）{
与于节点GT;右=删除（＆于节点的GT;右，数据）;
}
其他{
/ *现在我们可以删除这个节点和任最小元素取代
在左子树*右子树或最大元素/
如果（与于节点的GT;右放大器;＆安培;＆于节点GT;左）{
/ *在这里，我们将与最小元素替换右子树* /
TEMP = FindMin（与于节点的GT;右）;
节点 - ＆GT;数据= TEMP-GT＆;数据;
/ *由于我们与其他一些节点取代了它，我们必须删除节点* /
节点 - ＆GT;右=删除（＆于节点的GT;右，TEMP-GT＆;数据）;
}
其他{
/ *如果只有一个或零孩子，我们便可以直接
从树中删除它和它的母公司连接到其子* /
TEMP =节点;
如果（与于节点GT;左== NULL）
节点=＆于节点GT;的权利;
否则，如果（与于节点的GT;右== NULL）
节点=＆于节点GT;左;
免费（TEMP）; / *温度是不再需要* /
}
}
返回节点;}无效PrintInorder（treeNode的节点*）{
如果（节点！= NULL）{
PrintInorder（与于节点GT;左）;
的printf（％D，与于节点GT;数据）;
PrintInorder（与于节点的GT;右）;
}
}
的第一件事是在结构变更
int数据;
到
void *的数据;
更多code ++编辑：
的#include＆LT;＆stdio.h中GT;
＃包括LT＆;＆stdlib.h中GT;
＃包括LT＆;＆string.h中GT;typedef结构treeNode的{
void *的数据;
结构treeNode的*离开;
结构treeNode的*权利;
} treeNode节点;treeNode的*插入（treeNode的节点*，void *的数据，诠释sizeOfType，INT（*比较）（无效* ARG1，无效* ARG2））{
如果（节点== NULL）{
treeNode的*温度;
TEMP =的malloc（sizeof的（*温度））;
TEMP-GT＆;数据=的malloc（sizeOfType）;
的memcpy（TEMP-＆GT;数据，数据sizeOfType）;
温度 - ＆GT;左=温度 - ＆GT;右= NULL;
返回温度;
} 如果（比较（数据，于节点＆GT;数据）== 1）{
与于节点GT;右=插入（与于节点的GT;右，数据的sizeof（INT），比较（数据，及于节点GT;数据））;
}
否则，如果（比较（数据，及于节点GT;数据）== -1 ||比较（数据，及于节点GT;数据）== 0）{
与于节点GT;左=插入（与于节点GT;左，数据的sizeof（INT），比较（数据，及于节点GT;数据））;
}
返回节点;
}无效打印（无效*一）{
的printf（％d个*（INT *）一）;
}无效InorderGeneric（treeNode的节点*，无效（* P）（无效*））{
如果（节点！= NULL）{
InorderGeneric（于节点＆GT;左页）;
ρ（于节点＆GT;数据）;
InorderGeneric（与于节点的GT;右页）;
}
}INT int_sorter（无效* first_arg，无效* second_arg）{
INT第一= *为（int *）first_arg;
INT秒= *为（int *）second_arg;
如果（第一＆lt;第二）{
返回-1;
}
否则，如果（第一==秒）{
返回0;
}
其他{
返回1;
}
}诠释主要（无效）{
treeNode的*根= NULL;
INT项目;
无效* V; 的printf（二叉树添加节点：\\ n）;
而（scanf函数（％d个，＆安培;项）== 1）{
V =＆放大器;项目;
根=插入（根，V的sizeof（INT），int_sorter）;
} 的printf（\\ n ---初始树--- \\ n）;
的printf（按顺序走树：\\ n）;
InorderGeneric（根，打印）;
的printf（\\ n）; 返回0;
}
解决方案
您会需要创建该公司所使用的每个数据类型的比较函数和函数指针传递给需要知道两件各功能数据等于或大于/小于彼此。只有这个功能必须知道内部的数据类型。
这个功能看起来像：
INT compare_X（常量无效* D1，常量无效* D2）
和功能应该返回0，如果两个对象是相等的，小于0，如果对象指向d1为小，或者大于0，否则。你将有一个范围的这些功能，如 compare_int ， compare_double 等，具体取决于数据的类型，你'重新存储在一个特定的树。
这样，你会这个参数添加到的功能，需要比较两个对象：
INT（* cpm_fptr）（常量无效*，常量无效*）
现在，例如插入，如果（数据＆GT;（于节点＆GT;数据））将变成：
如果（cmp_fptr（数据，及于节点GT;数据）0）/ *数据＆GT;与于节点GT;数据* /
还有：
如果（cmp_fptr（数据，及于节点GT;数据）== 0）/ *数据==＆于节点GT;数据* /如果（cmp_fptr（数据，于节点＆GT;数据）小于0）/ *数据＆下;与于节点GT;数据* /
插入的签名，现在看起来像：
treeNode的*插入（treeNode的节点*，int数据，
INT（* cpm_fptr）（常量无效*，常量无效*））
如果你的内部类型是 INT ，您可以调用它像：
插入（节点，my_int，compare_int）;
这是怎么样的功能 bsearch 和的qsort 能够在任何类型的数据进行操作。
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.
这篇关于用C通用二叉搜索树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
