二叉搜索树中删除节点
一、引言
卧槽，好累。
我们来看看在二叉搜索树中删除一个节点的情况，如果要删除的是叶子节点，那么就十分容易！
我们要切断最右下角的17，只需要做两件事，一是切断15的右孩子指向，让他指向NULL。二是释放掉17的内存。
这看上去十分之容易。
那么如果我们要删掉15这个节点呢？
哎我操！这下我不能直接切断12和他的链接，这根本行不通。我们还需要保证15的子树依旧留在树里面，而不是断联，就和爱答不理的男神女神一样。🤔
我们知道，15这个b· · · · · ·友，有两个孩子。而7这种只有一个孩子，删除7只需要让它的父亲和他的孩子链接一下就行。如果9还有很多孩子，我们什么操作都不需要做，他们依然会保留在树上。
但是对于要删除有两个孩子的节点。我们不推荐这么做！💢
为什么？我们来看看删除15的情况。
我们将13链接到12上面，但是这样我们就会丢失17节点！为什么？你看看再链上17节点后是几叉树？回答我！😡
二、尝试
删除节点会有三种情况：
- 删除没有孩子的节点
- 一个孩子
- 两个孩子
我们增加一些节点，增加通用性。现在我们要删除15节点。
来看看怎么操作。
然后怎么操作就不用说了吧？删除原来的17节点！他只有一个孩子，删除起来很方便，之前讲过哦。
这个操作简直就像是夺舍一样，找了个替死鬼，细思极恐！😱
你可能会问，为什么要用右子树的最小值呢？
因为我们要满足二叉搜索树，就必须让左子树较小，右边较大。如果我们取右边最小值，那么它就会比原来的值更大，而左边的元素当然将会较小，右边当然会比他大！
你可能会说想要用左子树最大值，很好！你很聪明！😎
对于这里，就会像删除情况1一样简单！
我们利用一个性质想一想，一颗树中，值最小的那个节点是没有左孩的！因为左孩要比他小。
所以对于情况3（也就是有两个孩子），我们需要在目标节点的右子树中，找到最小值，然后拷贝或者说填入这个值。最后我们需要删除重复的节点。
三、cpp实现
#include<iostream>using namespace std;struct Node{ int data; Node *left; Node *right;};Node* findmin(Node *root){ //优先处理空树的情况 if(root==NULL){ cout<<"This is a empty tree!\n"; } //写上终止条件哦！！！！！！！！！！！！ if(root->left==NULL){ return root; } return findmin(root->left);}
struct Node *Delete(Node* root,int data){ if(root==NULL)return root;//处理空树 //利用递归找到要删除的节点。 else if(data<=root->data){//如果我们要找的树比根的值小，那么问题被降级为从左子树删除。 root->left=Delete(root->left,data); } else if(data>root->data){ root->right=Delete(root->right,data); } else{//小节点在吗，here is 胖狗，我要来删你咯！🤫 //case1:no child if(root->left==NULL&&root->right==NULL){ delete root;//虽然root指的内存被删了，但是root此时为悬空指针里面还有值，危险！ root=NULL;//懂什么叫内存安全吗！ } //case2:one child else if(root->left==NULL){ Node *temp=root; root=root->right; delete temp;
} else if(root->right==NULL){ Node *temp=root; root=root->left; delete temp;
} //case3:two child else{ Node *temp; temp=findmin(root->right);//查找右子树最小值 root->data=temp->data; root->right=Delete(root->right,temp->data); } } return root;}太难了，卧槽！😱
部分信息可能已经过时