看再多的算法书数据结构书,都不如自己实现一遍代码来的印象深刻。很多时候我们总是眼高手低的,要看书,更要写代码。 对于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);
- #ifndef _BSTREE_H
- #define _BSTREE_H
-
- #define OPERATION_SELECT
-
- typedef int key_type ;
- typedef struct __bst_node
- {
- struct __bst_node* parent;
- struct __bst_node* left;
- struct __bst_node* right;
- key_type key;
- int data;
-
- #ifdef OPERATION_SELECT
- int counter;
- #endif
-
- }bst_node;
-
- typedef struct __bs_tree
- {
- bst_node *bst_root;
- }bs_tree;
- bst_node* bst_search_aux(bst_node* root,key_type key,bst_node** pparent);
- bst_node* bst_search(bst_node* root,key_type key);
- bst_node* bst_min(bst_node* root);
- bst_node* bst_max(bst_node *root);
- bst_node* bst_successor(bst_node* node);
- bst_node* bst_predecessor(bst_node* node);
- bst_node* bst_allocnode(key_type key,int data);
- int bst_freenode(bst_node* node);
- bst_node* bst_insert(bst_node *root,bst_node* node);
- bst_node* bst_delete(bst_node* root,bst_node *node);
-
- #endif
- #include"bst.h"
- #include<stdio.h>
- #include<stdlib.h>
-
- /* if find the node whose key equal to key,return the node;
- * else return null;
- * if not find and pparent is not null, return the futurn father
- * if your want insert a node whose key is equal to key
- */
- bst_node* bst_search_aux(bst_node* root,key_type key,bst_node** pparent)
- {
- bst_node *parent = root;
- bst_node* cur = root;
-
- while(cur&&cur->key != key)
- {
- parent = cur;
- if(cur->key >key)
- cur = cur->left;
- else
- cur = cur->right;
- }
-
- if(cur == NULL)
- {
- if(pparent != NULL)
- *pparent = parent;
- }
- return cur;
- }
-
- /*just find ,if found,return the node ,else return null*/
- bst_node* bst_search(bst_node* root,key_type key)
- {
- return bst_search_aux(root,key,NULL);
- }
-
- /*find the node whose key is the smallest in the tree*/
- bst_node* bst_min(bst_node* root)
- {
- bst_node *cur = root;
- if(cur == NULL)
- return NULL; /*empty tree, return null*/
-
- while(cur->left != NULL)
- cur = cur->left;
-
- return cur;
- }
-
- bst_node* bst_max(bst_node *root)
- {
- bst_node *cur = root;
-
- if(cur == NULL)
- return NULL;
-
- while(cur->right)
- cur = cur->right;
-
- return cur;
-
- }
-
- bst_node* bst_successor(bst_node* node)
- {
- bst_node *par;
- bst_node *node_tmp;
- if(node == NULL)
- return NULL;
-
- if(node->right != NULL)
- return bst_min(node->right);
-
- par = node->parent;
- node_tmp = node;
-
- while(par && node_tmp == par->right)
- {
- node_tmp = par ;
- par = par->parent;
- }
-
- return par;
-
-
- }
-
- bst_node* bst_predecessor(bst_node* node)
- {
- bst_node *par;
- bst_node *node_tmp;
-
- if(node == NULL)
- return NULL;
-
- if(node->left != NULL)
- {
- return bst_max(node->left);
- }
-
- par = node->parent;
- node_tmp = node;
-
- while (par && node_tmp == par->left)
- {
- node_tmp = par;
- par = par->parent;
- }
-
- return par;
-
- }
-
-
- bst_node* bst_allocnode(key_type key,int data)
- {
- bst_node *node = NULL;
- node = (bst_node*)malloc(sizeof(bst_node));
- if(node == NULL)
- {
- printf("alloc node failed \n");
- return NULL;
- }
-
-
- node->key = key;
- node->data = data ;
- node->parent = NULL;
- node->left = NULL;
- node->right = NULL;
- #ifdef OPERATION_SELECT
- node->counter = 1;
- #endif
- return node;
- }
-
- int bst_freenode(bst_node* node)
- {
- if(node)
- free(node);
-
- node = NULL;
- return 0;
- }
-
- #ifdef OPERATION_SELECT
- bst_node* bst_up_counter(bst_node* root,bst_node* node)
- {
- bst_node *cur = root;
- if(root == NULL||node == NULL)
- {
- printf("invalid input,root or node is null\n");
- return NULL;
- }
-
- while(cur->key != node->key)
- {
- cur->counter++;
- if(cur->key > node->key)
- cur = cur->left;
- else
- cur = cur->right;
- }
-
- return root;
- }
-
- bst_node* bst_down_counter(bst_node *root,bst_node* node)
- {
- bst_node *cur = root;
- if(root == NULL|| node == NULL)
- {
- printf("invalid input ,root or node is null\n");
- return NULL;
- }
-
- while(cur->key != node->key)
- {
- cur->counter--;
- if(cur->key > node->key)
- cur = cur->left;
- else
- cur = cur->right;
- }
- return root;
-
- }
-
- #endif
-
- /* return 0 means succeed,else failed*/
- bst_node* bst_insert(bst_node *root,bst_node* node)
- {
- bst_node* par;
- bst_node* same_node = NULL;
-
- if(node == NULL)
- {
- printf("[bst_insert] invalid input ,please check the input\n");
- return root;
- }
-
- same_node = bst_search_aux( root, node->key, &par);
- if(same_node != NULL)
- {
- printf("same node has been existed ,insert failed \n");
- return root;
- }
-
- if(par == NULL)
- {
- root = node;
- return root;
- }
-
- if(node->key >(par)->key)
- {
- (par)->right = node;
- }
- else
- {
- (par)->left = node;
- }
-
- node->parent = par;
- #ifdef OPERATION_SELECT
- root = bst_up_counter(root,node);
- #endif
-
- return root;
-
- }
-
- bst_node* bst_delete(bst_node* root,bst_node *node)
- {
- bst_node *par = node->parent;
- bst_node* child;
- bst_node* successor;
-
-
- if(root == NULL || node == NULL)
- {
- printf("invalid input ,root or node is null\n");
- return root;
- }
-
- if(node->left == NULL && node->right == NULL) /*no child*/
- {
-
- #ifdef OPERATION_SELECT
- bst_down_counter(root,node);
- #endif
-
- if(par)
- {
- if(node == par->left)
- par->left = NULL;
- else
- par->right = NULL;
- }
-
- else
- root = NULL;/*no father means root node*/
-
- bst_freenode(node);
-
- return root;
- }
-
- if(node->left == NULL || node->right == NULL) /*only one child*/
- {
-
- #ifdef OPERATION_SELECT
- bst_down_counter(root,node);
- #endif
- if(node->left)
- child = node->left;
- else
- child = node->right;
-
- child->parent = par;
-
- if(par)
- {
- if(node == par->left)
- par->left = child;
- else
-
- par->right = child;
- }
- else
- {
- root = child;
- }
-
- bst_freenode(node);
- return root;
- }
-
- /*both chld,so successor must be existed*/
-
- successor = bst_successor(node);
- node->key = successor->key;
- node->data = successor->data;
- return bst_delete(root,successor);
-
- }
-
- #ifdef OPERATION_SELECT
- bst_node* bst_select(bst_node* root,int k)
- {
- if(root == NULL)
- return NULL;/*not find the kth node*/
- int t=0;
- if(root->left ==NULL)
- t = 0;
- else
- t = root->left->counter;
-
- if(t>k)
- return bst_select(root->left,k);
- else if(t<k)
- return bst_select(root->right,k-t-1);
- return root;
- }
-
- #endif
- #include<stdio.h>
- #include<stdlib.h>
- #include<time.h>
- #include"bst.h"
-
- #define random(x) (rand()%(x))
-
- #define N 10
- int test_bst()
- {
- bs_tree bst;
-
- bst_node *node[N];
- bst_node *node_4;
- bst_node *node_max;
-
-
-
- int i;
- int array[N];
- // srand((int)time(NULL)) ;
- bst.bst_root = NULL;
- for(i = 0;i<N;i++)
- {
- array[i] = random(100);
- }
-
- for(i = 0;i<N;i++)
- {
- printf("a[%d] = %d\n",i,array[i]);
- }
-
- for(i = 0;i<N;i++)
- {
- node[i] = bst_allocnode(array[i],array[i]);
- if(node[i] != NULL)
- bst.bst_root = bst_insert(bst.bst_root,node[i]);
- else
- {
- printf("alloc failed ,should exit\n");
- return -1;
- }
- }
-
- node_4 = bst_select(bst.bst_root,4);
- if(node_4 == NULL)
- {
- printf("the fourth node is not existed\n");
- return -2;
- }
- printf("the fourth node's key is %d\n",node_4->key);
- bst.bst_root = bst_delete(bst.bst_root,node_4);
- for(i = 0;i<N;i++)
- {
- node_max = bst_max(bst.bst_root);
- if(node_max)
- printf("%d\t",node_max->key);
- else
- {
- printf("find the max failed \n");
- return -2;
- }
- bst.bst_root = bst_delete(bst.bst_root,node_max);
- }
-
- printf("\n");
- return 0;
- }
- int main()
- {
- test_bst();
- return 0;
- }
阅读(1158) | 评论(0) | 转发(0) |