Chinaunix首页 | 论坛 | 博客
  • 博客访问: 201319
  • 博文数量: 26
  • 博客积分: 567
  • 博客等级: 中士
  • 技术积分: 420
  • 用 户 组: 普通用户
  • 注册时间: 2011-06-05 18:48
文章分类

全部博文(26)

文章存档

2011年(26)

分类:

2011-10-10 15:13:12

原文地址:二叉搜索树的C实现 作者:Bean_lee

    看再多的算法书数据结构书,都不如自己实现一遍代码来的印象深刻。很多时候我们总是眼高手低的,要看书,更要写代码。 对于IT民工而言,一个讲算法头头世道但无法实现算法的民工,远不如 一个just do it民工。

    吐槽完毕,最近实现了二叉搜索树的算法,和大家分享。不对之处,请各位指正。本文实现的是最基本的二叉搜索树,非平衡二叉搜索树。 

    测试代码在linux下编译通过,同时验证了几轮,暂是没有发现bug。读者可以直接使用这份代码。如何使用这份代码,可以参考测试文件 bst_test.c。

    测试用例,写的不够周全,只是初步体现了测试驱动开发的思想,并没有对每个接口进行详备的测试。

    代码中注释不多,原因有二
    1 二叉搜索树 算法比较简单
    2 我深信:好的代码,是自注释的。

    二叉搜索树中,稍复杂的接口是删除,算法导论中的删除 伪码层次并不清晰,倒是讲述比较清晰。本实现将删除接口按照下面三种情况,分别实现,相对比较好理解。
    1 删除节点 无孩子
    2 删除节点 只有一个孩子
    3 删除节点有两个孩子

版本情况
 V1.0   --实现基本二叉树的插入 删除 查找功能
 V1.1 ----新增select功能,查找第k大的节点。从0开始,即最小节点是bst_select(root,0);



  1. #ifndef _BSTREE_H
  2. #define _BSTREE_H
  3.  
  4. #define OPERATION_SELECT
  5.  
  6. typedef int key_type ;
  7. typedef struct __bst_node
  8. {
  9.     struct __bst_node* parent;
  10.     struct __bst_node* left;
  11.     struct __bst_node* right;
  12.     key_type key;
  13.     int data;
  14.  
  15. #ifdef OPERATION_SELECT
  16.     int counter;
  17. #endif
  18.  
  19. }bst_node;
  20.  
  21. typedef struct __bs_tree
  22. {
  23.     bst_node *bst_root;
  24. }bs_tree;
  25. bst_node* bst_search_aux(bst_node* root,key_type key,bst_node** pparent);
  26. bst_node* bst_search(bst_node* root,key_type key);
  27. bst_node* bst_min(bst_node* root);
  28. bst_node* bst_max(bst_node *root);
  29. bst_node* bst_successor(bst_node* node);
  30. bst_node* bst_predecessor(bst_node* node);
  31. bst_node* bst_allocnode(key_type key,int data);
  32. int bst_freenode(bst_node* node);
  33. bst_node* bst_insert(bst_node *root,bst_node* node);
  34. bst_node* bst_delete(bst_node* root,bst_node *node);
  35.  
  36. #endif

  1. #include"bst.h"
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4.  
  5. /* if find the node whose key equal to key,return the node;
  6.   * else return null;
  7.   * if not find and pparent is not null, return the futurn father
  8.   * if your want insert a node whose key is equal to key
  9.   */
  10. bst_node* bst_search_aux(bst_node* root,key_type key,bst_node** pparent)
  11. {
  12.     bst_node *parent = root;
  13.     bst_node* cur = root;
  14.  
  15.     while(cur&&cur->key != key)
  16.     {
  17.         parent = cur;
  18.         if(cur->key >key)
  19.             cur = cur->left;
  20.         else
  21.             cur = cur->right;
  22.     }
  23.  
  24.     if(cur == NULL)
  25.     {
  26.         if(pparent != NULL)
  27.             *pparent = parent;
  28.     }
  29.     return cur;
  30. }
  31.  
  32. /*just find ,if found,return the node ,else return null*/
  33. bst_node* bst_search(bst_node* root,key_type key)
  34. {
  35.     return bst_search_aux(root,key,NULL);
  36. }
  37.  
  38. /*find the node whose key is the smallest in the tree*/
  39. bst_node* bst_min(bst_node* root)
  40. {
  41.     bst_node *cur = root;
  42.     if(cur == NULL)
  43.         return NULL; /*empty tree, return null*/
  44.  
  45.     while(cur->left != NULL)
  46.         cur = cur->left;
  47.  
  48.     return cur;
  49. }
  50.  
  51. bst_node* bst_max(bst_node *root)
  52. {
  53.     bst_node *cur = root;
  54.     
  55.     if(cur == NULL)
  56.         return NULL;
  57.  
  58.     while(cur->right)
  59.         cur = cur->right;
  60.  
  61.     return cur;
  62.     
  63. }
  64.  
  65. bst_node* bst_successor(bst_node* node)
  66. {
  67.     bst_node *par;
  68.     bst_node *node_tmp;
  69.     if(node == NULL)
  70.         return NULL;
  71.  
  72.     if(node->right != NULL)
  73.         return bst_min(node->right);
  74.  
  75.     par = node->parent;
  76.     node_tmp = node;
  77.  
  78.     while(par && node_tmp == par->right)
  79.     {
  80.         node_tmp = par ;
  81.         par = par->parent;
  82.     }
  83.  
  84.     return par;
  85.  
  86.     
  87. }
  88.  
  89. bst_node* bst_predecessor(bst_node* node)
  90. {
  91.     bst_node *par;
  92.     bst_node *node_tmp;
  93.  
  94.           if(node == NULL)
  95.         return NULL;
  96.  
  97.     if(node->left != NULL)
  98.     {
  99.         return bst_max(node->left);
  100.     }
  101.  
  102.     par = node->parent;
  103.     node_tmp = node;
  104.  
  105.     while (par && node_tmp == par->left)
  106.     {
  107.         node_tmp = par;
  108.         par = par->parent;
  109.     }
  110.  
  111.     return par;
  112.     
  113. }
  114.  
  115.  
  116. bst_node* bst_allocnode(key_type key,int data)
  117. {
  118.     bst_node *node = NULL;
  119.     node = (bst_node*)malloc(sizeof(bst_node));
  120.     if(node == NULL)
  121.     {
  122.         printf("alloc node failed \n");
  123.         return NULL;
  124.     }
  125.     
  126.  
  127.     node->key = key;
  128.     node->data = data ;
  129.     node->parent = NULL;
  130.     node->left = NULL;
  131.     node->right = NULL;
  132. #ifdef OPERATION_SELECT
  133.     node->counter = 1;
  134. #endif
  135.     return node;
  136. }
  137.  
  138. int bst_freenode(bst_node* node)
  139. {
  140.     if(node)
  141.     free(node);
  142.     
  143.     node = NULL;
  144.     return 0;
  145. }
  146.  
  147. #ifdef OPERATION_SELECT
  148. bst_node* bst_up_counter(bst_node* root,bst_node* node)
  149. {
  150.     bst_node *cur = root;
  151.     if(root == NULL||node == NULL)
  152.     {
  153.         printf("invalid input,root or node is null\n");
  154.         return NULL;
  155.     }
  156.  
  157.     while(cur->key != node->key)
  158.     {
  159.         cur->counter++;
  160.         if(cur->key > node->key)
  161.             cur = cur->left;
  162.         else
  163.             cur = cur->right;
  164.     }
  165.  
  166.     return root;
  167. }
  168.  
  169. bst_node* bst_down_counter(bst_node *root,bst_node* node)
  170. {
  171.     bst_node *cur = root;
  172.     if(root == NULL|| node == NULL)
  173.     {
  174.         printf("invalid input ,root or node is null\n");
  175.         return NULL;
  176.     }
  177.  
  178.     while(cur->key != node->key)
  179.     {
  180.         cur->counter--;
  181.         if(cur->key > node->key)
  182.             cur = cur->left;
  183.         else
  184.             cur = cur->right;
  185.     }
  186.     return root;
  187.     
  188. }
  189.  
  190. #endif
  191.  
  192. /* return 0 means succeed,else failed*/
  193. bst_node* bst_insert(bst_node *root,bst_node* node)
  194. {
  195.     bst_node* par;
  196.     bst_node* same_node = NULL;
  197.  
  198.     if(node == NULL)
  199.     {
  200.         printf("[bst_insert] invalid input ,please check the input\n");
  201.         return root;
  202.     }
  203.     
  204.     same_node = bst_search_aux( root, node->key, &par);
  205.     if(same_node != NULL)
  206.     {
  207.         printf("same node has been existed ,insert failed \n");
  208.         return root;
  209.     }
  210.  
  211.     if(par == NULL)
  212.     {
  213.         root = node;
  214.         return root;
  215.     }
  216.  
  217.     if(node->key >(par)->key)
  218.     {
  219.         (par)->right = node;
  220.     }
  221.     else
  222.     {
  223.         (par)->left = node;
  224.     }
  225.  
  226.     node->parent = par;
  227. #ifdef OPERATION_SELECT
  228.     root = bst_up_counter(root,node);
  229. #endif
  230.     
  231.     return root;
  232.     
  233. }
  234.  
  235. bst_node* bst_delete(bst_node* root,bst_node *node)
  236. {
  237.     bst_node *par = node->parent;
  238.     bst_node* child;
  239.     bst_node* successor;
  240.     
  241.  
  242.     if(root == NULL || node == NULL)
  243.     {
  244.         printf("invalid input ,root or node is null\n");
  245.         return root;
  246.     }
  247.  
  248.     if(node->left == NULL && node->right == NULL) /*no child*/
  249.     {
  250.  
  251. #ifdef OPERATION_SELECT
  252.         bst_down_counter(root,node);
  253. #endif
  254.  
  255.         if(par)
  256.         {
  257.             if(node == par->left)
  258.                 par->left = NULL;
  259.             else
  260.                    par->right = NULL;
  261.         }
  262.  
  263.         else
  264.          root = NULL;/*no father means root node*/
  265.  
  266.         bst_freenode(node);
  267.  
  268.         return root;
  269.     }
  270.  
  271.     if(node->left == NULL || node->right == NULL) /*only one child*/
  272.     {
  273.     
  274. #ifdef OPERATION_SELECT
  275.         bst_down_counter(root,node);
  276. #endif
  277.         if(node->left)
  278.             child = node->left;
  279.         else
  280.             child = node->right;
  281.  
  282.         child->parent = par;
  283.  
  284.         if(par)
  285.         {
  286.             if(node == par->left)
  287.                 par->left = child;
  288.             else
  289.  
  290.                 par->right = child;
  291.         }
  292.         else
  293.         {
  294.             root = child;
  295.         }
  296.  
  297.         bst_freenode(node);
  298.         return root;
  299.     }
  300.  
  301.     /*both chld,so successor must be existed*/
  302.  
  303.     successor = bst_successor(node);
  304.     node->key = successor->key;
  305.     node->data = successor->data;
  306.     return bst_delete(root,successor);
  307.     
  308. }
  309.  
  310. #ifdef OPERATION_SELECT
  311. bst_node* bst_select(bst_node* root,int k)
  312. {
  313.     if(root == NULL)
  314.         return NULL;/*not find the kth node*/
  315.     int t=0;
  316.     if(root->left ==NULL)
  317.         t = 0;
  318.     else
  319.         t = root->left->counter;
  320.  
  321.     if(t>k)
  322.         return bst_select(root->left,k);
  323.     else if(t<k)
  324.         return bst_select(root->right,k-t-1);
  325.     return root;
  326. }
  327.  
  328. #endif


  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<time.h>
  4. #include"bst.h"
  5.  
  6. #define random(x) (rand()%(x))
  7.  
  8. #define N 10
  9. int test_bst()
  10. {
  11.     bs_tree bst;
  12.  
  13.     bst_node *node[N];
  14.     bst_node *node_4;
  15.     bst_node *node_max;
  16.  
  17.     
  18.     
  19.     int i;
  20.     int array[N];
  21. // srand((int)time(NULL)) ;
  22.     bst.bst_root = NULL;
  23.     for(i = 0;i<N;i++)
  24.     {
  25.         array[i] = random(100);
  26.     }
  27.  
  28.     for(i = 0;i<N;i++)
  29.     {
  30.         printf("a[%d] = %d\n",i,array[i]);
  31.     }
  32.  
  33.     for(i = 0;i<N;i++)
  34.     {
  35.         node[i] = bst_allocnode(array[i],array[i]);
  36.         if(node[i] != NULL)
  37.             bst.bst_root = bst_insert(bst.bst_root,node[i]);
  38.         else
  39.         {
  40.             printf("alloc failed ,should exit\n");
  41.             return -1;
  42.         }
  43.     }
  44.  
  45.     node_4 = bst_select(bst.bst_root,4);
  46.     if(node_4 == NULL)
  47.     {
  48.         printf("the fourth node is not existed\n");
  49.         return -2;
  50.     }
  51.     printf("the fourth node's key is %d\n",node_4->key);
  52.     bst.bst_root = bst_delete(bst.bst_root,node_4);
  53.     for(i = 0;i<N;i++)
  54.     {
  55.         node_max = bst_max(bst.bst_root);
  56.         if(node_max)
  57.             printf("%d\t",node_max->key);
  58.         else
  59.         {
  60.           printf("find the max failed \n");
  61.             return -2;
  62.         }
  63.         bst.bst_root = bst_delete(bst.bst_root,node_max);
  64.     }
  65.     
  66.     printf("\n");
  67.     return 0;
  68. }
  69. int main()
  70. {
  71.     test_bst();
  72.     return 0;
  73. }
阅读(597) | 评论(0) | 转发(0) |
0

上一篇:没有了

下一篇:我的C++技巧总结

给主人留下些什么吧!~~