C 中的通用二叉搜索树

我已经实现了二叉搜索树，但我也想使其通用。代码如下：

typedef struct treeNode {
  int data;
  struct treeNode *left;
  struct treeNode *right;
} treeNode;

和功能：

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);
  }
}

首先是改变结构

int data;

to

void *data;

用更多代码编辑：

#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;
 }

您需要为使用的每种数据类型创建一个比较函数，并将函数指针传递给每个需要知道两条数据是否相等或大于/小于彼此的函数。只有这个函数必须知道内部数据类型。

这个函数看起来像：

int compare_X(const void *d1, const void *d2)

如果两个对象相等，则该函数应返回 0；如果 d1 指向的对象较小，则该函数应返回小于 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 */

Also:

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 and qsort能够对任何类型的数据进行操作。