二分搜索树的节点的删除还是挺有意思的，下面先从特例开始写，然后通过特例再写通例。
一、删除最小值所在的节点
根据二分搜素树的性质可知，最小值就是：至到某左节点没有左孩子，它就是最小值
代码如下：
// 在以node为根的二叉搜索树中,返回最小键值的节点 Node* minimum(Node* node){ if( node->left == NULL ) return node; return minimum(node->left); }
二、删除最大值所在的节点
根据二分搜素树的性质可知，最小值所在的节点就是：至到某左节点没有左、右孩子，它就是最小值
代码如下：
// 在以node为根的二叉搜索树中,返回最大键值的节点 Node* maximum(Node* node){ if( node->right == NULL ) return node; return maximum(node->right); }
三、删除某一个节点
如图：
删除58所在的节点，那哪个节点去取代58所在的位置了？
方案一：
根据二叉搜索树的性质可知，58的所有右节点都比它大，58所有的左节点都比它小。所以可以用59取代58的位置。
用比较标准的说法就是：58所在节点的右孩子的左节点来代替58.
原因：
- 改节点是58的某个右节点的一支，所以比50大。
- 改节点肯定比自己之前的父节点下，因为改节点是父节点的左节点。
下面就是代码实现：
// 删除掉以node为根的二分搜索树中的最大节点 // 返回删除节点后新的二分搜索树的根 Node* removeMax(Node* node){ if( node->right == NULL ){ Node* leftNode = node->left; delete node; count --; return leftNode; } node->right = removeMax(node->right); return node; } // 删除掉以node为根的二分搜索树中键值为key的节点 // 返回删除节点后新的二分搜索树的根 Node* remove(Node* node, Key key){ if( node == NULL ) return NULL; //如果是某一左节点，好处理，直接删除 if( key < node->key ){ node->left = remove( node->left , key ); return node; }//如果是某一右节点，好处理，直接删除 else if( key > node->key ){ node->right = remove( node->right, key ); return node; } else{ // key == node->key 如果是一个根节点，有以下3种情况 if( node->left == NULL ){ Node *rightNode = node->right; delete node; count --; return rightNode; } if( node->right == NULL ){ Node *leftNode = node->left; delete node; count--; return leftNode; } // node->left != NULL && node->right != NULL Node *successor = new Node(minimum(node->right)); count ++; successor->right = removeMin(node->right); successor->left = node->left; delete node; count --; return successor; } }
方案二：
选取，58所在左节点的右节点，即图中的53.也是满足二叉搜索树的性质的。
代码实现：
// 删除掉以node为根的二分搜索树中键值为key的节点
// 返回删除节点后新的二分搜索树的根
Node* removeSomeone(Node* node, Key key){
if (node == NULL) {
return NULL;
}
if (key < node->key) {
node->left = removeSomeone(node->left,key);
return node;
}
if (key > node->key) {
node->right = removeSomeone(node->right,key);
return node;
}
else{ // key == node->key 如果是一个根节点，有以下3种情况
//左节点为空 直接把右节点移上去
if (node->left == NULL) {
Node *rightNode = node->right;
delete node;
count --;
return rightNode;
}
if (node->right == NULL) {
Node *leftNode = node->left;
delete node;
count --;
return leftNode;
}
// node->left != NULL && node->right != NULL
//左节点的右子节点
Node *successor = new Node(maximum(node->left));
count ++;
successor->left = removeMax(node->left);
successor->right = node->right;
delete node;
count --;
return successor;
}
}
代码中的注释还是蛮详细的，也方便自己以后看。方案二是仿造方案一写的，思想最重要，有了思想，代码表达是迟早的事情。