# 二叉搜索树的基本操作
二叉搜索树真的是表面看上去简单，但是实际上有很多好玩有趣的东西，至少它的相关算法真的超级多
0.数据结构定义
typedef struct BTREE{ struct BTREE *p; struct BTREE *left; struct BTREE *right; //为了后面方便，如果一个节点的右儿子为null，那么我把它为 1， 与0（表示左子节点为null）区分开 int key;}bTree;bTree *root; 1.基本操作
①查找
②插入
③删除
查找和插入都没什么可说的，但是删除的情况稍微复杂一些
删除一个节点（非空）要分为一下几种情况：
- 如果左子节点和右子节点其中一个为空，一个不为空，那么就用不为空的那个子节点代替父节点原来的位置（如果都为空那就不用删了）
- 如果左右儿子都不为空，那么拿什么节点来代替这个被删除的节点呢？拿这个节点的后继节点！为什么拿后继节点呢？想一想如果拿某个不是后继的子节点，那么这个子节点代替了被删除的父节点的位置，那这个子节点原来的位置谁代替呢？这样会产生更多问题。后继就不一样了，注意被删掉的这个节点现在是有右儿子的，所以后继一定是右子树的最小节点，且后继如果不是被删除节点的右子节点，那么后继一定是某个父亲的左子节点!但是还是要根据后继和被删除节点的关系区分：
- 如果后继节点是被删除节点的右儿子，那么直接让它代替被删除节点的位置即可，即建立它与被删除节点的父亲的联系，以及建立它与被删除节点的左儿子的联系
- 如果后继节点不是父节点的右儿子，那么此时要分两步：①让它的右子树代替它②让它代替被删除节点
- 所以其实这个过程需要想清楚的是：
- 被删除节点的左右子节点的情况
- 被删除节点的后继的特点：①没有左子节点②如果不是被删除节点的右子节点，那么一定是它的父亲的左子节点③后继一定没有左儿子
- 新节点代替旧节点位置的过程：①新节点建立与旧节点的左右儿子的过程（如果存在）②新节点建立与旧节点的父亲的过程（如果父亲存在）
- 两个节点建立联系的过程：①子节点的p设置为父亲节点②父亲节点的left或者right设置为子节点
//这个过程主要是用v替代u原来的位置，是建立u的父亲与v之间的关系，u的儿子与v之间的关系由调用者完成void transplant(bTree *u, bTree *v){ if(isNull(u)) { //同样，如果u是一个null，那就不用考虑transplant了，因为根本得不到u的父亲的信息 return ; } //重写了一遍transplant，坑还是挺多的，但是只要把每种情况想清楚就好 //这里注意u是root节点时的设置 if(isNull(u->p)) { root = v; } else{ u->p->left == u ? u->p->left = v : u->p->right = v; } //又忘记考虑v是null的情况了！ if(!isNull(v)) v->p = u->p;}//注意删除并不一定是把后继作为它的代替！只有左右节点都存在时才是后继代替//删除还是挺难写的，很容易想不清，需要注意后继节点的一些特点void del(bTree *node){ if(isNull(node)) return ; if(isNull(node->left)) { //因为left是null了，所以也不需要设置left与node->right节点的关系了 transplant(node, node->right); } else if(isNull(node->right)) { transplant(node, node->left); } else{ //只有它的后继可以继承它的位置，后继一定在右子树中，后继一定是没有左子节点的,且后继如果不是node的右子节点，那么后继一定是某个父亲的左子节点! bTree *success = successor(node); bTree *successright = success->right; //1.如果success是node的右子节点，那么①建立success和node的左子节点之间的关系②建立success与node的父亲之间的关系 //2.如果success不是node右子节点，那么①建立success的右子节点和success的父亲之间的关系（因为右子节点要代替success）②建立success与node的左和右子节点之间的关系③建立success与node的父亲之间的关系 //所以公共的部分就是①success与node父亲之间的关系②success与node左子节点之间的关系 //两个节点之间建立关系的过程分为两步①子节点的p设置为父节点②父节点的left或者是right设置为子节点 if(!(success == node->right)) { transplant(success, success->right); //但是node原来就有右子节点，且不是success，所以这里需要建立好success与node的左右子节点之间的关系！ success->right = node->right; node->right->p = success; } success->left = node->left; node->left->p = success; transplant(node, success); }} ④遍历（4种）
遍历要说的太多了，放在下一篇
⑤前驱和后继
- 求给定节点的前驱节点
前驱节点，要么在左子树找，左子树为空则在父辈节点找
bTree *predecessor(bTree *root){ if(isNull(root)) return root; if(isNull(root->left)) { bTree *p = root->p; bTree *q = root; while(!isNull(p) && p->right != q) { q = p; p = p->p; } return p; } else{ return iterativeMaximum(root->left); }} - 求给定节点的后继节点
后继节点，要么在右子树找，右子树为空则在父辈节点找
//错误的惯性思维，对于一个节点，可能是父亲结点的左子节点也可能是右子节点//如果这个节点是其父亲的右子节点，那么这个节点是比其父亲大，但是！不能保证这个节点的父辈节点和它的大小关系bTree *successor(bTree *root){ if(!isNull(root->right)) { return minimum(root->right); } bTree *temp = root->p; while(!isNull(temp) && root != temp->left) { root = temp; temp = temp->p; } return temp;} ⑥最大和最小
- 求给定根节点的子树中key值最小的节点
就是不断的找这棵子树的最左子节点
//循环实现bTree *iterativeMinimum(bTree *root){ //注意对root的检查，因为后面是直接用到了root->left if(isNull(root)) return 0; while(!isNull(root->left)) { root = root->left; } return root;}//递归实现bTree *minimum(bTree *root){ if(isNull(root)) return root; if(isNull(root->left)) { return root; } else{ return minimum(root->left); }} - 求给定根节点的子树的key值最大的结点
就是找这棵子树的最右子节点
//递归实现bTree *maximum(bTree *root){ if(isNull(root)) return root; if(isNull(root->right)) { return root; } else{ return maximum(root->right); }}//循环实现bTree *iterativeMaximum(bTree *root){ if(isNull(root)) return 0; while(!isNull(root->right)) root = root->right; return root;}