个节点且该节点是左孩子，那么用其左孩子来替换node
3. 否则node既有一个左孩子又有一个右孩子，我们要查找node的后继y，这个后继位于node的右子树中并且没有左孩子，现在需要将y移除原来的位置进行拼接，并替换树中的node
3.1. 如果y是z的node的右孩子，那么用y替换node
3.2 否则，y位于z的右子树中但并不是z的右孩子，这种情况下，先用y的右孩子替换y，然后用y替换node(最后步骤同3.1)
为了在二叉搜索树内移动子树，定义一个函数bst_transplant,它用凉意可子树替换一棵字数并成为双亲的孩子节点。以下实现为用一棵以v为根的子树来替换一棵以u为根的子树，节点u的双亲就变为节点v的双亲，并且最后v成为u的双亲的相应孩子
[cpp]
//replace subtree of u with subtree of v
BST *bst_transplant(BST *root, BST *u, BST *v)
{
if(u->parent==NULL) //u is root
root = v;
else if(u->parent->right == u) // u is his parent's right subtree
u->parent->right = v;
else u->parent->left = v; //u is his parent's left subtree
if(v!=NULL) //set v's parent
v->parent = u->parent;
return root;
}
[cpp]
//replace subtree of u with subtree of v BST *bst_transplant(BST *root, BST *u, BST *v) { if(u->parent==NULL) //u is root root = v; else if(u->parent->right == u) // u is his parent's right subtree u->parent->right = v; else u->parent->left = v; //u is his parent's left subtree if(v!=NULL) //set v's parent v->parent = u->parent; return root; } //replace subtree of u with subtree of v
BST *bst_transplant(BST *root, BST *u, BST *v)
{
if(u->parent==NULL) //u is root
root = v;
else if(u->parent->right == u) // u is his parent's right subtree
u->parent->right = v;
else u->parent->left = v; //u is his parent's left subtree
if(v!=NULL) //set v's parent
v->parent = u->parent;
return root;
}
树的删除代码如下
[cpp]
BST *bst_delete(BST *root, data_t data)
{
BST *node = NULL, *y = NULL;
node = bst_search(root, data); //find the deleted node
if(node==NULL)
return NULL;
if(node->left == NULL) //case 1
root = bst_transplant(root, node, node->right);
else if(node->right == NULL) //case 2
root = bst_transplant(root, node, node->left);
else
{
y = bst_mininum(node->right); //find node's successor
if(y->parent!=node) //case 3 follow make y's parent to node
{
root = bst_transplant(root, y, y->right);
y->right = node->right;
node->right->parent = y;
}
//case 3 y->parent == node
root = bst_transplant(root, node, y);
y->left = node->left;
y->left->parent = y;
}
return root;
}
BST *bst_delete(BST *root, data_t data)
{
BST *node = NULL, *y = NULL;
node = bst_search(root, data); //find the deleted node
if(node==NULL)
return NULL;
if(node->left == NULL) //case 1
root = bst_transplant(root, node, node->right);
else if(node->right == NULL) //case 2
root = bst_transplant(root, node, node->left);
else
{
y = bst_mininum(node->right); //find node's successor
if(y->parent!=node) //case 3 follow make y's parent to node
{
root = bst_transplant(root, y, y->right);
y->right = node->right;
node->right->parent = y;
}
//case 3 y->parent == node
root = bst_transplant(root, node, y);
y->left = node->left;
y->left->parent = y;
}
return root;
}