从二分搜索树中删除节点，但没有将父节点存储在结构中

Question

作为一个n练习，我正在使用二叉搜索树。我设法搜索二叉树，并添加节点，但现在我试图找到一种方法来删除，我似乎被卡在如何确定谁是要删除的节点的父节点。

于是开始与我有这样的结构

struct BST_node { 
    struct double_linked_list *data; 
    struct BST_node *left; 
    struct BST_node *right; 
}; 

，我也有这种结构指向根指针..

struct BST_node *BST_email_root = 0; 

我有这个功能来搜索节点

struct BST_node *BST_find_customer(struct BST_node *root, char *email) { 
if (root==NULL) 
    return NULL; 
if (strcmp(email,root->data->data->email)==0) 
    return root; 
else 
    { 
    if (strcmp(email,root->data->data->email)==-1) 
    return BST_find_customer(root->left,email); 
    else 
     return BST_find_customer(root->right,email); 
    } 

我打电话给其他功能，通过使用

b = BST_find_customer(BST_email_root, email); 

，我试图创建函数删除nodes..What我必须是这样的：

struct BST_node *BST_delete(struct BST_node *root, char *email) 
    { 
    struct BST_node *temp; 
    if (root==NULL) 
     return root; 
    else if(strcmp(root->data->data->email,email)>0) 
     root->left = BST_delete(root->left, email); 
    else if(strcmp(root->data->data->email,email)<0) 
     root->right = BST_delete(root->right, email); 
    else 
     { 
     if(root->left == NULL && root->right == NULL) 
      { 
      free(root); 
      root = NULL; 
      } 
     else if(root->right == NULL) 
      { 
      temp = root; 
      root = root->left; 
      free(temp); 
      } 
     else if(root->left == NULL) 
      { 
      temp = root; 
      root = root->right; 
      free(temp); 
      } 
     else 
      { 
      struct BST_node *maxNode = findMaxNode(root->left);//finding the maximum in LEFT sub-tree 
      root->data = maxNode->data; //Overwriting the root node with MAX-LEFT 
      root->left = BST_delete(root->left, maxNode->data);//deleted the MAX-LEFT node 
      } 

     return root; 
     } 

    } 

使用此功能也

struct BST_node *findMaxNode(struct BST_node *root) 
      { 
       if(root->right == NULL) return root; 
       findMaxNode(root->right); 
      } 

然而，这不工作还我得到错误

Answer 1

这是一个解决方案，虽然它不是递归的.....

要从BST删除节点N，您需要考虑三种情况：

1. 如果N是叶，则没有问题，只是删除它
2. 如果N只有一个儿子，只需更换N的儿子;你需要指向N的父亲去做

3. 如果N有两个儿子，那么你可以用其右儿子的左前儿子或其左儿子的最小儿子代替N，以保持订单属性。

   void *BST_delete(struct BST_node *root, char *email){ 
   
   if (root==NULL) 
       return; 
   
   struct BST_node * father = NULL; 
   char which_son; //will help us in remembering if root is the right or left son of his father 
   
   while (strcmp(email,root->data->data->email)!=0){ //first, finding root and remembering who's root father 
       if(root==NULL) { 
        return ; 
       } else if (strcmp(email,root->data->data->email) < 0){ 
        father = root; 
        root = root->left; 
        which_son = 'l'; 
       } else { 
        father = root; 
        root = root->right; 
        which_son = 'r'; 
       } 
   } 
       // now you have both the root node, and its father 
   if ((root->right == NULL) && (root->left == NULL)){ //case 1, if it's a leaf 
       free(root); 
       return; 
   } else if (root->left == NULL) { //case 2 
       if (which_son == 'l') { 
        father->left = root->right; 
       } else { 
        father->right = root->right; 
       } 
   
   } else { //case 3 : here i get the "rightest" son of root's left son 
       struct BSD_node * replacing_node = root->left; 
   
       while (replacing_node->right != NULL) { 
        replacing_node = replacing_node->right; 
       } //now replacing_node is a leaf, and can replace root 
       if (which_son == 'l') { 
        father->left = replacing_node; 
        replacing_node->left = root->left; 
        replacing_node->right = root->right; 
       } else { 
        father->right = replacing_node; 
        replacing_node->left = root->left; 
        replacing_node->right = root->right; 
       } 
   } 
   free (root); 
   } 
   

我你的函数的返回值改为void，因为它可能不需要任何返回值。

它可以通过简单地将一个节点的'data'字段替换为另一个节点来实现，但我故意以这种方式实现它，以强调删除节点被他的后代之一所取代。

如果你觉得压制的节点​​应该被左边（右边）儿子的最右边的（最左边的）儿子所取代，那么检查这些是否只有2个不存在的节点有可能违反BSD的规定。

另外，这个功能会受到很多因单片而受到影响，所以它会享受重构的乐趣。