二叉查找树简介
二叉查找树(Binary Search Tree)，又被称为二叉搜索树。 它是特殊的二叉树：对于二叉树，，假设x为二叉树中的任意一个结点，x节点包含关键字key，节点x的key值记为key[x]。如果y是x的左子树中的一个结点，则key[y] <= key[x]；如果y是x的右子树的一个结点，则key[y] >= key[x]。那么，这棵树就是二叉查找树。
集合操作search搜索
有迭代版和递归版。 思想都是向下查找合适的值，有值会返回节点，无合适值会一直向下走直到返回null
/* * (递归实现)查找”二叉树x”中键值为key的节点 */BNode* search(BSTree x, Type key){x->key==key)return x;if (key < x->key)return bstree_search(x->left, key);elsereturn bstree_search(x->right, key);}/* * (非递归实现)查找”二叉树x”中键值为key的节点 */BNode* search(DataType key) const{BNode *p=root;p->key!=key){if (key<p->key){p=p->left;}else{p=p->right;}}if(p!=NULL)printf(“search %d\n”,p->key);return p;}mininum寻找子树的最小key节点
最小节点是最左子节点
maxnum子树最大key节点
最大节点是最右子节点
predecessor前序寻找比此节点小的最大节点
两种情况， 正常来说是找次节点的左子树最大节点，如果没有左子树，向上寻找根
BNode* Predecessor(BNode *T){BNode *x=T;if (x->left!=NULL){return maxmun(x->left);}BNode *y=x->p;x==y->left){x=y;y=y->p;}return y;};succesor后序
同样两种情况，右子树的最小值，或者没有右子树的情况下，向上找根
BNode* Successor(BNode *T){BNode *x=T;if(x->right!=NULL){return minmun(x->right);}BNode *y=T->p;y->right==x){x=y;y=y->p;}return y;}insert插入
向下插入， 两种情况，有根和无根。注意对root的操作
delete删除
删除节点x 1。无左子树，右子树接上。 2。无右子树，左子树接上。 3。左右都有，寻找右子树最小值y 3.1如果最小值为直接右子树，直接替换接上 3.2不是直接右子树，把y右子树替换y，y再替换x
c++实现cstdiocstringcstdlib>using namespace std;typedef int DataType;struct BNode{DataType key;BNode *p,*left,*right;};class Btree{private:BNode *root;public:Btree(){root=NULL;};~Btree(){destoryNode(root);root=NULL;};void Insert(DataType key){BNode *z=new BNode;BNode *y=NULL;BNode *x=root;z->key=key;z->p=z->right=z->left=NULL;){y=x;if (x->key>key){x=x->left;}else{x=x->right;}}//x指向root，向下查找z->p=y;if (y==NULL){root=z;}else if(y->key>key){y->left=z;}else{y->right=z;}//建立z的双亲节点y与z的联系printf(“Node %d”,z->key);if(y!=NULL){printf(“p %d\n”,y->key);}else{printf(“\n”);}};BNode* search(DataType key) const{BNode *p=root;p->key!=key){if (key<p->key){p=p->left;}else{p=p->right;}}if(p!=NULL)printf(“search %d\n”,p->key);return p;}BNode* minmun(BNode *T){BNode *p=T;while(p->left!=NULL){p=p->left;}printf(“%d’s minmun %d\n”,T->key,p->key);return p;}BNode* maxmun(BNode *T){BNode *p=T;while(p->right!=NULL){p=p->right;}printf(“%d’s maxmun %d\n”,T->key,p->key);return p;}BNode* Successor(BNode *T){BNode *x=T;if(x->right!=NULL){return minmun(x->right);}BNode *y=T->p;y->right==x){x=y;y=y->p;}return y;}BNode* Predecessor(BNode *T){BNode *x=T;if (x->left!=NULL){return maxmun(x->left);}BNode *y=x->p;x==y->left){x=y;y=y->p;}return y;};void Translate(BNode *u,BNode *v){if (u->p==NULL){root=v;}else if(u->p->left==u){u->p->left=v;}else{u->p->right=v;}if (v!=NULL){v->p=u->p;}}int TreeDelete(BNode *z){if (z->left==NULL){printf(“Translate z z->right\n”);Translate(z,z->right);delete z;}){printf(“Translate z z->left\n”);Translate(z,z->left);delete z;}else{BNode *y=minmun(z->right);if (y->p!=z){Translate(y,y->right);y->right=z->right;y->right->p=y;printf(“Translate y y->right\n”);}Translate(z,y);y->left=z->left;y->left->p=y;printf(“Translate z y\n”);}}void destoryNode(BNode *T){if (T->left!=NULL){destoryNode(T->left);}if (T->right!=NULL){destoryNode(T->right);}printf(“destory %d\n”,T->key);BNode *p=T;delete p;};};int main(int argc, char const *argv[]){Btree *T=new Btree();T->Insert(3);T->Insert(7);T->Insert(1);T->Insert(12);T->Insert(8);BNode *t=T->search(12);BNode *t1=T->search(3);T->maxmun(t);T->minmun(t);T->TreeDelete(t);T->TreeDelete(t1);delete T;return 0;}
初初尝试着拥抱的人，一派新鲜幸福都来不及沉浸，
