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

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; 
}