c - C 中的 BST - 元素删除

Question

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

我正在做一项任务，其中保留了用户的 BST，该 BST 根据用户姓名的字母顺序排序。

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

该作业在学校系统中进行了测试，我不知道输入是什么，但只有使用元素删除的测试失败，因为一旦系统再次询问树内容，我就会返回错误的名称。我已经研究了几个小时了，但我不知道我做错了什么。

相关代码:

//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 并在插入新用户时为其动态分配内存时，它通过了测试。

抱歉造成困惑。