二叉搜索树的删除功能无法正常工作

Question

这是用C编码的二叉搜索树的删除功能，但这不起作用。应该删除的节点被垃圾值替换。

void delete(struct node* root,int data) 
{ 
{ 
    struct node* t1; 
    if(root==0) { 
     printf("element not found\n"); 
    } else if(data>root->data) { 
     delete(root->right,data); 
    } else if(data<root->data) { 
     delete(root->left,data); 
    } else { 
     if(root->right&&root->left) { 
      t1=findmin(root->right); 
      root->data=t1->data; 
      free(t1); 
     } else { 
      t1=root; 
      if(root->right) { 
       root=root->right; 
      } else if(root->left) { 
       root=root->left; 
      } 
      free(t1); 
     } 
    } 
} 

它本身工作，但节点没有被删除，并被一些垃圾值所取代。

struct node* findmin(struct node* t) { 
    if(t==NULL) { 
     return NULL; 
    } else if(t->left) { 
     findmin(t->left); 
    } else 
     return t; 
} 

Answer 1

您正在将函数参数中的root传递给您，然后在您的代码的以下块中重新分配它。

  else 
     { 
       t1=root; 
       if(root->right) 
       { 
         root=root->right; 
       } 
       else if(root->left) 
       { 
         root=root->left; 
       } 
       free(t1); 
     } 

此重新分配对于当前函数调用是临时的（因为它已通过值传递）。 或者您也可以这样做，即删除指定节点后返回树的新根。

struct node* delete(struct node* root, int key) 
{ 
    if (root == NULL) return root; 

    if (key < root->key) 
     root->left = delete(root->left, key); 

    else if (key > root->key) 
     root->right = delete(root->right, key); 

    else 
    { 
     // node with only one child or no child 
     if (root->left == NULL) 
     { 
      struct node *temp = root->right; 
      free(root); 
      return temp; 
     } 
     else if (root->right == NULL) 
     { 
      struct node *temp = root->left; 
      free(root); 
      return temp; 
     } 

     struct node* temp = findmin(root->right); 

     root->key = temp->key; 

     root->right = delete(root->right, temp->key); 
    } 
    return root; 
}