二叉查找树 --c代码
二叉查找树实现：
#include <stdio.h>#include <stdlib.h>#include <malloc.h>#define malloc_thing(thing) (thing *)malloc(sizeof(thing))//此函数指针用来插入时做比较使用 typedef int (*tree_compare_t)(void *node_value,void *insert_value); typedef struct tree_node_t tree_node_t;typedef struct tree_t tree_t;//树节点结构 struct tree_node_t{ tree_node_t *left; //左子树 tree_node_t *right; //右子树 void *value; //存储的值 };//树结构 struct tree_t{ tree_node_t *root; //树根 unsigned int count; //节点数 tree_compare_t compare; //节点比较方法 };/////////////////////////////////////////////////////////创建一个节点 tree_node_t *tree_node_create(void *value){ tree_node_t *node=malloc_thing(tree_node_t); node->value=value; node->left=NULL; node->right=NULL; return node;}//节点销毁 void tree_node_destroy(tree_node_t *node){ free(node);}//销毁子树void tree_all_node_destroy(tree_node_t *node){ if(node!=NULL) { tree_all_node_destroy(node->left); tree_all_node_destroy(node->right); tree_node_destroy(node); }}//子树最大值tree_node_t *tree_node_max(tree_node_t *node){ while(node->right!=NULL) { node=node->right; } return node;}//子树最小值tree_node_t *tree_node_min(tree_node_t *node){ while(node->left!=NULL) { node=node->left; } return node;}//递归插入一个节点 /* 算法解释: 插入一个节点，首先要看是否已经存在，也就是先查找， 所以要不断的递归进行比较。 (1)如果一直到NULL，也就是没有找到，说明插入的为新节点， 需要创建新的节点。 (2)如果相等，说明已经存在，不需要再插入了，则返回即可 (3)如果不相等，根据大小插入节点的左子树或者右子树*/tree_node_t *tree_node_insert(tree_t *tree,tree_node_t *node,void *value){ //节点为空表明已经查找到了叶子，插入的值为新值，需要创建新的节点 if(node==NULL) { tree->count++; tree_node_t *node=tree_node_create(value); return node; } //如果插入值等于节点值，说明已经存在，无需插入，直接返回 else if(tree->compare(node->value,value)==0) { return node; } //如果插入值大于节点值，继续往右子树插入 else if(tree->compare(node->value,value)<0) { node->right=tree_node_insert(tree,node->right,value); return node; } //如果插入值小于节点值，继续往左子树插入 else { node->left=tree_node_insert(tree,node->left,value); return node; }} // 递归删除一个节点/* 算法解释: 删除一个节点，删除和插入很像，不过要复杂点。 也要先查找点，不过找到要执行删除操作，没找到反而不用干什么。 (1)如果为NULL，说明没找到，只要返回NULL就行了 (2)如果相等，说明已经存在要删除的节点，那就需要删除此节点了 1)如果此节点左右子树都为空，那就直接删除节点，返回NULL就行 2)如果此节点左子树不空，而右子树为空，删除节点，返回左子树 3)如果此节点右子树不空，而左子树为空，删除节点，返回右子树 4)如果左右子树都不空，那就需要早到左子树中最大的数或则右子树 中最小的值，替换到要删除的值，然后在左子树中删除最大的节点 或者右子树删除最小的节点。 (3)如果不相等，根据大小删除节点*/tree_node_t *tree_node_delete(tree_t *tree,tree_node_t *node,void *value){ //如果为NULL，说明没找到，只要返回NULL就行了 if(node==NULL) { return NULL; } //如果相等，说明已经存在要删除的节点，那就需要删除此节点了 else if(tree->compare(node->value,value)==0) { tree_node_t *left=node->left; tree_node_t *right=node->right; //如果此节点左右子树都为空，那就直接删除节点，返回NULL就行 if(!left&&!right) { tree_node_destroy(node); return NULL; } //如果此节点左子树不空，而右子树为空，删除节点，返回左子树 else if(left&&!right) { tree_node_destroy(node); return left; } //如果此节点右子树不空，而左子树为空，删除节点，返回右子树 else if(!left&&right) { tree_node_destroy(node); return right; } //如果左右子树都不空，那就需要早到左子树中最大的数 //替换到要删除的值 //然后在左子树中删除最大的节点 //返回节点 else { tree_node_t *max=tree_node_max(left); node->value=max->value; node->left =tree_node_delete(tree,left,max->value); return node; } } //如果不相等，根据大小删除节点 else if(tree->compare(node->value,value)<0) { node->right=tree_node_delete(tree,node->right,value); return node; } else { node->left=tree_node_delete(tree,node->left,value); return node; }}// 递归查找一个节点 tree_node_t *tree_node_search(tree_t *tree,tree_node_t *node,void *value){ //如果为NULL，说明没找到，只要返回NULL就行了 if(node==NULL) { return NULL; } //如果相等，说明已经存在要删除的节点，那就需要删除此节点了 else if(tree->compare(node->value,value)==0) { return node; } //如果不相等，根据大小删除节点 else if(tree->compare(node->value,value)<0) { return tree_node_search(tree,node->right,value); } else { return tree_node_search(tree,node->left,value); }} //打印结构 ---先序遍历 void display_tree_node(tree_node_t *node){ if(node!=NULL) { printf(" [ %d ] ",*((int *)node->value)); display_tree_node(node->left); display_tree_node(node->right); }} //////////////////////////////////////////////////////////*下面的方法才是对外的方法*/ //创建一棵树 tree_t *tree_create(tree_compare_t compare){ tree_t *tree=malloc_thing(tree_t); tree->root=NULL; tree->count=0; tree->compare=compare; return tree;}//向树种插入一个节点 void tree_insert(tree_t *tree,void *value){ tree->root=tree_node_insert(tree,tree->root,value);}//向树中删除一个节点 void tree_delete(tree_t *tree,void *value){ tree->root=tree_node_delete(tree,tree->root,value);}//向树中删除一个节点 void * tree_search(tree_t *tree,void *value){ tree_node_t *node=tree_node_search(tree,tree->root,value); if(node!=NULL) { return node->value; } else { return NULL; }}//销毁此树 void tree_destroy(tree_t *tree){ if(tree->root!=NULL) { tree_all_node_destroy(tree->root); } free(tree);}//打印树，用来查看我们的树 void display_tree(tree_t *tree){ display_tree_node(tree->root); printf("\n");} ////////////////////////////////////////////////////int tree_compare(int *node_value,int *insert_value){ int a=*node_value; int b=*insert_value; if(a==b) { return 0; } else if(a>b) { return 1; } else { return -1; }}main(){ tree_t *tree=tree_create((tree_compare_t)tree_compare); int a=1; int b=2; int c=3; int d=0; int e=5; //插入a printf("插入%d：",a); tree_insert(tree,&a); display_tree(tree); printf("插入%d：",a); tree_insert(tree,&a); display_tree(tree); printf("插入%d：",b); tree_insert(tree,&b); display_tree(tree); printf("插入%d：",c); tree_insert(tree,&c); display_tree(tree); printf("插入%d：",d); tree_insert(tree,&d); display_tree(tree); //查找 if(tree_search(tree,&a)!=NULL) { printf("查找%d: 找到\n",a); } else { printf("查找%d: 没有找到\n",a); } //查找 if(tree_search(tree,&e)!=NULL) { printf("查找%d: 找到",e); } else { printf("查找%d: 没有找到\n",e); } //删除节点a printf("删除%d：",a); tree_delete(tree,&a); display_tree(tree); //删除节点c printf("删除%d：",c); tree_delete(tree,&c); display_tree(tree); //删除节点d printf("删除%d：",d); tree_delete(tree,&d); display_tree(tree); //删除节点b printf("删除%d：",b); tree_delete(tree,&b); display_tree(tree); //删除节点a printf("删除%d：",a); tree_delete(tree,&a); display_tree(tree); tree_destroy(tree); system("pause");} ??