二叉搜索樹的刪除功能無法正常工作

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