我已经实现的二叉搜索树，但我也想使它通用。 代码如下：
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;
至
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;
}
