删除一个二叉搜索树的节点

三种情况

1. Case 1

删除的节点没有子节点（即该节点为叶节点）

操作：直接delete

2. Case 2

删除的节点下有一个子节点

操作：用左/右子树代替该节点

3. Case 3

删除的节点有两个子节点

操作：

1. 找到右子树中的最小值
2. 复制该值到删除的节点处
3. （如果树中的数据都各不相同的话）我们需要删去右子树中的最小值，因为右子树的最小值没有左子树，所以删去它的情况就降为Case1或Case2

代码

BstNode* FindMin(BstNode* root) {
	if (root->left == NULL)return root;
	else
		return FindMin(root->left);
}
struct BstNode* Delete(BstNode* 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 {
		//no child
		if (root->left == NULL && root->right == NULL) {
			delete root;
			root = NULL;
		}
		//one child
		else if (root->left == NULL) {
			BstNode* temp = root;
			root = root->right;
			delete temp;
		}
		else if (root->right == NULL) {
			BstNode* temp = root;
			root = root->left;
			delete temp;
		}
		//two children
		else {
			BstNode* temp = FindMin(root->right);
			root->data = temp->data;
			root->right = Delete(root->right, temp->data);
		}
	}
	return root;
}