C 中的 BST - 元素删除

Question

编辑：问题并不完全出在我最初假设的地方。提出的问题和其中的代码仅与实际问题部分相关。查看我接受的答案。

我正在做一项任务，我保留了用户的 BST，它是根据他们的名字按字母顺序排列的。

删除函数使用中序遍历根据用户名查找用户，然后将其从树中删除。

作业在学校系统中测试，我不知道输入是什么，只有使用元素删除的测试失败，因为一旦系统再次要求树内容，我 return 错误的名称.我已经研究了几个小时了，我不知道我做错了什么。

相关代码：

//User struct
struct user{
  char name[100];
  int height;
  struct user* left;
  struct user* right;
};


//finds the leftmost child of a node
struct user* minUser(struct user* user)
{
    struct user* min = user;
    while (min->left != NULL)
        min = min->left;
    return min;
}


//recursive delete function 
struct user* delete(struct user *root, char *name){
  if (root == NULL)
    return NULL;
  int compare = strcmp(name,root->name);
  if (compare<0){
    root->left = delete(root->left,name);
  }
  else if (compare>0){
   root->right = delete(root->right,name); 
  }
  else {
    //If node has only one child
    if (root->left == NULL){
      struct user* temp = root->right;
      free(root);
      return temp;
    } else if (root->right == NULL){
      struct user* temp = root->left;
      free(root);
      return temp;
    }
    //If node has both children. I suspect the error to be here most likely
    struct user* temp = minUser(root->right);

    strcpy(root->name, temp->name);
    //root->height = temp->height;
    root->right = delete(root->right, strdup(temp->name));
  }
  return root;
}

Answer 1

问题不在我最初假设的地方。它在包含 char name[100]; 的结构定义中。当我将其更改为指针 char *name 并在插入新用户时为其动态分配内存时，它通过了测试。

抱歉造成混淆。

C 中的 BST - 元素删除

BST in C - element deletion

c

binary-search-tree