BSTNode *bst_delete(BSTNode *root, int key) {
if (root == NULL) return NULL;
// 先按 BST 查找规则定位待删结点。
if (key < root->key) root->left = bst_delete(root->left, key);
else if (key > root->key) root->right = bst_delete(root->right, key);
else {
// 找到待删结点 root。
if (root->left == NULL || root->right == NULL) {
// 叶结点或只有一棵子树:用 child 替代 root。
BSTNode *child = root->left ? root->left : root->right;
free(root);
return child;
}
// 有两棵子树:用右子树中的最小结点,即直接后继替代。
BSTNode *s = min_node(root->right);
root->key = s->key;
// 删除右子树中原来的后继结点。
root->right = bst_delete(root->right, s->key);
}
return root;
}