Binary Search Tree Insert Not Functioning Correctly in C (可能是一个无知的错误)

Question

我正在尝试用 C 语言创建 BST 树结构，但我在插入函数工作时遇到了一些困难。阅读一些示例后，我发现最好的方法是传递一个指向树根的指针，然后递归地插入该节点，直到找到一个空节点 (NULL)。但是，我试图传递整个树结构（只是为了将所有内容都整齐地封装起来），我想我想出了以下解决方案：

void insert(struct Node* temp, char *s){

if (temp  == NULL) {
  struct Node *newNode = make_node();
  newNode-> data = strdup(s);
  temp = newNode;
  return;


}
 if (strcmp(s,temp->data) > 0) {
  temp = temp->left;
  insert(temp, s);
  }
 if (strcmp(s,temp->data) < 0) {
   temp = temp->right;
   insert(temp, s);
  }

 }
//--------------------------------------------------------------                                      
 void insert_tree(struct BSP * tree, char *s) {

    struct Node *temp = tree->root;
    insert(temp, s);

 }
//-------------------------------------------------------------

当我插入到树中时，我调用了 insert_tree()，但随后我使用 insert() 作为递归插入应指向树根的节点的方法。 P.S BSP 的结构和节点是：

typedef struct Node {
   struct Node * left;
   struct Node * right;
   char * data;

 } node;

 typedef struct BSP {
  struct Node * root;
  int size;
}

任何人都可以帮助我理解我做错了什么吗？

Answer 1

您的问题是您正在丢弃新节点。在 C 函数中，参数是按值传递的，这意味着在插入函数中更改 temp 不会在调用者中更改它。

插入应该 return 新创建的节点，您需要在调用者中对其进行一些操作。

Answer 2

第一个答案是正确的，但你总是可以使用指针指向指针，就像这样。

typedef struct Node
{
    Node()
    {
        left = NULL;
        right = NULL;
        data = NULL;
    }

    struct Node* left;
    struct Node* right;
    char* data;
} node;

typedef struct BSP
{
    BSP()
    {
        root = NULL;
        size = 0;
    }

    struct Node* root;
    int size;
} bsp;

void insert(struct Node** temp, char* s)
{
    Node* node = *temp;

    if (node == NULL)
    {
        struct Node* newNode = new Node();
        newNode->data = strdup(s);
        (*temp) = newNode;
        return;
    }

    if (strcmp(s, node->data) > 0)
    {
        insert(&node->left, s);
    }

    if (strcmp(s, node->data) < 0)
    {
        insert(&node->right, s);
    }
}

void insert_tree(struct BSP* tree, char* s)
{
    insert(&tree->root, s);
    tree->size++;
}

Binary Search Tree Insert Not Functioning Correctly in C (可能是一个无知的错误)

Binary Search Tree Insert Not Functioning Correctly in C (possibly an ignorant error)

c

binary-tree

data-structures