二叉查找树 --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");
}
   


 

  

评论

1 楼 a06062125 2012-02-27  

挺好！值得学习