c++ - 二叉搜索树 - 插入

Question

我正在尝试编写一个将值插入二叉树的函数。到目前为止我得到了这个:

struct node
{
     int data;
     struct node* left;
     struct node* right;
};


struct node* newNode(int data)
{
     struct node* node = (struct node*)
     malloc(sizeof(struct node));
     node->data = data;
     node->left = NULL;
     node->right = NULL;

     return(node);
}

// Insert
struct node* insert (struct node* node, int data)
{
    if (node == NULL)
        node->data=data;
    else 
    {
      if (data < node->data)
         node->left = insert(node->left, data);
      else
         node->right = insert(node->right ,data);
    }
    node->left = NULL;
    node->right = NULL;
    return node;
}

但每次我运行它时，它都会停止工作。因此我认为我的插入功能一定有问题。有什么想法吗？

Answer 1

据我所知有两个问题:

struct node* insert (struct node* node, int data)
{
    if (node == NULL)
        node->data=data;  // 1: Dereferencing a null pointer is a bad idea.
    else 
    {
      if (data < node->data)
         node->left = insert(node->left, data);
      else
         node->right = insert(node->right ,data);
    }

    // 2: Throwing away the subtrees is also a bad idea.
    node->left = NULL;
    node->right = NULL;
    return node;
}

您应该使用 newNode 在树中创建一个节点，并保留子树:

struct node* insert (struct node* node, int data)
{
    if (node == NULL)
        node = newNode(data);
    else 
    {
      if (data < node->data)
         node->left = insert(node->left, data);
      else
         node->right = insert(node->right ,data);
    }
    return node;
}