研碎bst
bst ：binary search tree（二叉搜索树）
对于树中的每个节点n，左子树中的所有节点的关键字都小于节点n的关键字，右子树中所有节点的关键字都大于节点n的关键字
struct node{
int key;
struct node *left; //左节点
struct node *right; //右节点
};
#include <iostream> #include <iomanip> #include <stdlib.h> using namespace std; const int chy_ok = 0; const int chy_error = -1; struct node{ node(int k):key(k),left(NULL),right(NULL){} int key; struct node *left; struct node *right; }; class bst{ public: bst(int k):tree(new node(k)){} bst():tree(NULL){} ~bst(); node *min(node *n); node *max(node *n); node *parent(node *n); node *find(int k); bool is_empty(){ return tree == NULL ;} void chy_insert(int k); node *insert(int k,node *n); void insert(int k); //insert(k,tree) node *remove(node *n,int k); void remove(node *n); void remove(int k);// be called by ~bst void chy_remove(int k); node *get_root(){return tree;} void print(node *n); void print(); private: node *tree; }; bst::~bst(){ remove(tree); } node *bst::parent(node *n){ node *tmp; tmp = tree; if(n == tree){ return NULL; } while(tmp){ if((tmp->left == n) || (tmp->right == n)){ return tmp; }else if(tmp->key < n->key){ tmp = tmp->right; }else if(tmp->key > n->key){ tmp = tmp->left; } } return NULL; } node *bst::min(node *n){ while(n){ if(n->left == NULL){ return n; } n = n->left; } return NULL; } node *bst::max(node *n){ while(n){ if(n->right == NULL) return n; n = n->right; } return NULL; } node *bst::find(int k){ node *tmp; tmp = tree; while(tmp){ if(tmp->key < k){ tmp = tmp->right; }else if(tmp->key > k){ tmp = tmp->left; }else{ return tmp; } } return NULL; } void bst::print(node *n){ if(n){ print(n->left); cout << n->key << endl; print(n->right); } } void bst::print(){ print(tree); } void bst::chy_insert(int k){ //直接插入 node *tmp; tmp = tree; if(tmp == NULL){ tree = new node(k); return ; } while(tmp){ if(tmp->key < k){ if(tmp->right == NULL){ tmp->right = new node(k); return ; } tmp = tmp->right; }else if(tmp->key > k){ if(tmp->left == NULL){ tmp->left = new node(k); return ; } tmp = tmp->left; }else { return ; } } } node *bst::insert(int k,node *n){ //递归调用插入 node *tmp; if(n == NULL){ n = new node(k); } if(n->key < k){ n->right = insert(k,n->right); }else if(n->key > k){ n->left = insert(k,n->left); } return n; } void bst::insert(int k){ if(tree == NULL){ tree = new node(k); return ; } insert(k,tree); } //cycle node *bst::remove(node *n,int k){ //递归调用删除 node *tmp,*x; tmp = n; if(n == NULL){ return NULL; } if(tmp->key == k){ if((tmp->left != NULL ) && (tmp->right != NULL) ){ x = min(tmp->right); tmp->key = x->key; tmp->right = remove(tmp->right,tmp->key); }else if(tmp->left != NULL && tmp->right == NULL){ x = tmp; //要结合递归，因为tmp可能是某个节点的左节点或者右节点，而且又因为此时才是真正的删除，所以在此之前肯定调用了 tmp = tmp->left; //tmp->right = remove(tmp->right,k) 或者tmp->left = remove(tmp->left,k) 所以返回的是tmp的左节点作为tmp原来的作为 delete x; //左节点或者右节点的位置的值，如果没有递归调用，则必须找到父节点才能删除 }else if(tmp->right != NULL && tmp->left == NULL){ x = tmp; tmp = tmp->right; delete x; }else if((tmp->left == NULL ) && (tmp->right == NULL)){ delete tmp; tmp = NULL; } }else if(tmp->key < k){ tmp->right = remove(tmp->right,k); }else if(tmp->key > k){ tmp->left = remove(tmp->left,k); } return tmp; } void bst::remove(int k){ tree = remove(tree,k); } void bst::remove(node *n){ if(n){ remove(n->left); remove(n->right); delete n; } } //no cycle void bst::chy_remove(int k){ //直接删除 node *tmp; node *p; node *x; tmp = tree; if(tmp == NULL){ return ; } while(tmp){ if(tmp->key == k){ if((tmp->left != NULL )&& (tmp->right != NULL)){ //tmp have left child and right child x = min(tmp->right); //x must have no left child p = parent(x); //one can't be two's postion tmp->key = x->key; //two can't be one's postion if(p->left == x){ p->left = x->right; cout << "delete value is " << x->key << endl; delete x; return ; }else{ p->right = x->right; cout << "delete value is " << x->key << endl; delete x; return ; } }else if(tmp->left != NULL){ p = parent(tmp); if(p == NULL){ tree = tree->left; cout << "delete value is " << tmp->key << endl; delete tmp; return ; }else{ if(p->left == tmp){ p->left = tmp->left; cout << "delete value is " << tmp->key << endl; delete tmp; return ; }else{ p->right = tmp->left; cout << "delete value is " << tmp->key << endl; delete tmp; return ; } } }else if(tmp->right != NULL){ p = parent(tmp); if(p == NULL){ tree = tree->right; cout << "delete value is " << tmp->key << endl; delete tmp; return ; }else{ if(p->left == tmp){ p->left = tmp->right; cout << "delete value is " << tmp->key << endl; delete tmp; return ; }else{ p->right = tmp->right; cout << "delete value is " << tmp->key << endl; delete tmp; return ; } } }else { //tmp have no child p = parent(tmp); if(p == NULL){ tree = NULL; cout << "delete value is " << tmp->key << endl; delete tmp; return ; }else{ if(p->left == tmp){ p->left = NULL; }else{ p->right = NULL; } cout << "delete value is " << tmp->key << endl; delete tmp; return ; } } }else if(tmp->key < k){ //k may be in tree's right tmp = tmp->right; }else if(tmp->key > k){ //k may be in tree's left; tmp = tmp->left; } } return ; //k not in tree } void f1(){ srand(NULL); bst b1; int arr[1000]; #if 1 for(int i =0;i < 1000;i ++){ arr[i] = rand() % 1232127; b1.chy_insert(arr[i]); } #endif优质内容筛选与推荐>>
#if 0
for(int i = 0;i < 1000;i ++){
arr[i] = rand() % 1232127;
b1.insert(arr[i]);
}
#if 0 for(int i = 0;i < 1000;i ++){ b1.chy_remove(arr[i]); } #endif b1.print(); #if 0 for(int i =0;i < 1000;i ++){ b1.remove(arr[i]); } #endif #if 1 for(int i = 0;i < 1000;i ++){ b1.remove(arr[i]); } #endif } int main(){ f1(); return 0; }
1、LeetCode - Add Binary
2、C# HTTP返回代码表
3、Sql server中的几个系统表（一）
4、v
5、20155335俞昆《java程序设计》第6周总结