c - 如何找到二叉搜索树右子树中的最小值

Question

我正在尝试在二叉搜索树中创建删除功能。 我已经完成了删除函数，但我在使用 FindMin() 函数时遇到了一些问题，如下所示:

BST* delete_node(BST* root, int key)
{
BST* temp;
if (root == NULL)
    return root;
else if (key < root->key)
    root->left_child = delete_node(root->left_child, key);
else if (key > root->key)
    root->right_child = delete_node(root->right_child, key);
else //If the key is found delete it according to the following cases
{
    if (root->left_child == NULL && root->right_child == NULL)
    {
        free(root);
        root = NULL;
    }
    else if (root->left_child == NULL){ //right child exists
        temp = root;
        root = root->right_child;
        free(temp);
    }
    else if (root->right_child == NULL){ //left child exists
        temp = root;
        root = root->left_child;
        free(temp);
    }
    else{
        temp = FindMin(root->right_child);
        root->key = temp->key;
        root->right_child = delete_node(root->right_child, temp->key);
    }
}
return root; /*Returning the address of node to be reattached to 
            the parent of the deleted node*/

}

BST* FindMin(BST* root) //This functions finds the minimum key value in the 
right subtree
{
BST* temp = NULL;
if (root->left_child != NULL)
{
    temp = FindMin(root->left_child);
    return temp;
}
else
    return root;
}

我非常确定我需要修复 FindMin() 函数才能使其正常工作。但我的删除函数遇到了问题，因为每次删除一个节点时，都会出现错误，我认为这是因为 FindMin() 的原因。

Answer 1

这就是我做二叉搜索树的方式。

这是结构:

struct _Node;

typedef struct _Node* Position;

struct _Node
{
    int element;
    Position left;
    Position right;
};

这是搜索最小值的函数:

Position SearchMin(Position P)
{
    while(P->left != NULL)
    {
        P = P->left;
    }
    return P;
}