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

问题描述：

这是用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; 
}

请比'不正常工作'更具体，并改善代码格式。通过[ask howto]（https://stackoverflow.com/help/how-to-ask） – creimers

'findmin（t-> left）;'应该是'return findmin（t->左）;'！编译器最有可能告诉你（或多或少间接）。 – alk

我增加了return.it没有区别。通过“不正常工作”，我的意思是所需的既不删除也不删除。唯一的变化是，它在第一次调用时被替换为0，并且下一次被替换为垃圾值 – thehalberdier

答

您正在将函数参数中的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; 
}

我已经全局地声明了变量“root”。那么它是如何按值传递？我实施了更改并且程序正常工作。 – thehalberdier

嘿..全局变量哈克不会工作，因为它的递归函数。函数调用的每个实例都会为根分配不同的值。如果你想坚持无效返回，那么你可能可以通过引用在C++中传递参数，虽然我不确定。 –

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

相关推荐