C++学习记录-数据结构-二叉搜索树删除节点

C++学习记录-数据结构-二叉搜索树删除节点

从二叉搜索树中删除节点，有三种可能的情况：

• 情况1：欲删除的节点是叶子节点：只需切断链接
• 情况2：欲删除的节点有一个子节点，则令其父节点的指针指向子节点
• 情况3：与删除的节点有两个子节点：另节点的值等于其右子树的最小值，再删除右子树的最小值

代码示例：

删除节点函数：

Node* deletenode(Node* root,int value)
{
	//第一步，找出节点
	if (root == NULL) { return NULL; }
	else if (root->data > value) { root->left = deletenode(root->left, value); }
    //如果当前节点的值大于欲删除的值，左拐
	else if (root->data < value) { root->right = deletenode(root->right, value); }
    //如果当前节点的值小于欲删除的值，右拐
    
	else if (root->data == value)//找到了，开始删除
	{
		//第一种情况，节点为叶子节点
		if (root->left == NULL && root->right == NULL)
		{
			delete root;
			root = NULL;
		}

		//第二种情况，节点下只有一个子节点
		else if (root->left == NULL && root->right != NULL)
		{
			Node* temp = root;
			root = root->right;
			delete temp;
		}//左空
		else if (root->right == NULL && root->left != NULL)
		{
			Node* temp = root;
			root = root->left;
			delete temp;
		}//右空

		//第三种情况，节点有两个子节点
		else
		{
			Node* small = findmin(root->right);
			root->data = small->data;
			root->right = deletenode(root->right, small->data);
			//注意，右边最小值还可能有右子节点，因此要调用函数删除而不是暴力delete
		}
	}

	return root;//最后return节点，让上一个递归函数接收
}

寻找最小值节点函数

Node* findmin(Node* root)
{
	while (root->left != NULL)
	{
		root = root->left;
	}
	return root;
}