c - 在 C 循环中将节点插入 BST

Question

我正在尝试插入到我的 BST 中，但我正在努力创建一个循环。当我逐一插入时，代码可以工作，但是当我尝试将其放入循环时，它无法正确插入。

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h> // for strcmp()
#include <ctype.h> // for toupper()

typedef struct BstNode{
  //char name[20];
  // int data;
  struct BstNode* left;
  struct BstNode* right;
  char* name;
}BstNode;

typedef int (*Compare)(const char*, const char*); // makes comparisons easier

/* Returns pointer address to newly created node */
BstNode* createNode(char* name){ 
  BstNode* newNode = (BstNode*)malloc(sizeof(BstNode)); // Allocates memory for the newNode
  newNode->name = name; // newNode->data is like newNode.data
  newNode->left= NULL;
  newNode->right = NULL;
  return newNode;
}

//insert node into Tree recursively
BstNode* insertNode(BstNode* node, char* name, Compare cmp){
  int i;
  /* char *s1 = node->name;
     char *s2 = name;
     printf("s1: %s, s2: %s\n", s1,s2);
     i = strcmp(s1, s2); // if =1, s1 is greater
     printf("i: %d\n", i); */

  if(node == NULL){// if tree is empty
    // printf("inside NULL\n");
    node = createNode(name);
    //return node;
  }
  else{
    i = cmp (name, node->name); // sweet
    if(i == -1){
      // printf("inside left\n");
      node->left = insertNode(node->left, name, cmp);
      //return node;
    }
    else if(i == 1){
      // printf("inside right\n");
      node->right =  insertNode(node->right, name, cmp);
      //return node;
    }
    else if(i == 0 ){ //avoid duplicates for now
      // printf("inside 0\n");
      printf("Name is in BST\n");
      return NULL;
    }
  }
  return node;
}

BstNode* printTree(BstNode* node){
  if(node == NULL){
    return NULL;
  }
  printTree(node->left);
  printf("%s\n",node->name);
  printTree(node->right);
}

int CmpStr(const char* a, const char* b){
  return (strcmp (a, b));     // string comparison instead of pointer comparison
}
//void Insert(Person *root, char name[20]);

int main(){
  BstNode* root = NULL; // pointer to the root of the tree
  char buf[100];
  char option = 'a';

  while(1) { 
    printf("Enter employee name");
    scanf("%s",buf); 
    printf ("Inserting %s\n", buf);
    root =  insertNode(root, buf, (Compare)CmpStr);
    printTree(root);
  }
}

我可以做 root = insertNode(root, name, (Compare)CmpStr)在代码中多次，但如果我尝试使用用户输入循环它，它将无法正确插入。我不确定这是否与我使用 scanf() 或 root 设置不正确有关。我也尝试过使用 fgets() ，但我不太确定如何使用它并继续搞砸。如有任何帮助，我们将不胜感激。

Answer 1

在循环中，您始终将相同的缓冲区传递给插入函数；您的 createNode 不会复制缓冲区的内容，而是存储对(始终)相同缓冲区的引用；因此，插入后更改缓冲区内容也会更改先前插入节点的“内容”。

我建议将 createNode 中的 newNode->name = name 替换为 newNode->name = strdup(name)。这实际上会复制传递的“内容”，并让 BST 控制要保留的内存。因此，稍后删除节点时不要忘记释放此内存。