c - 递归二叉树插入

Question

所以我试图使用这个递归函数将一个值插入二叉树：

void add(node* *hd, int v){
node* curr = *hd;
if(curr == NULL){
    curr = (node*)malloc(sizeof(node));
    curr->value = v;
}else{
    if(v < curr->value){
        add(&curr->left, v);
    }else{
        add(&curr->right, v);
    }
}
}

它似乎不起作用，我只是不明白为什么我不能做这样的事情。我将如何解决它？

Answer 1

您需要初始化指针，因为它们可能会被设置为分配空间时获得的任何值。现在当你通过时add(&curr->left, v); curr->left可能不是某个地方的指针，但它仍然不是NULL；

void add(node* *hd, int v){
    node* curr = *hd;
    if(curr == NULL){
        curr = malloc(sizeof(node));
        curr->left = curr->right = NULL;
        curr->value = v;
        *hd = curr; // from Mohamed KALLEL
    }else{
        if(v < curr->value){
            add(&curr->left, v);
        }else{
            add(&curr->right, v);
        }
    }
}

Answer 2

您的新节点没有正确“连接”，因为您只是将指针存储在局部变量curr中，而不是写入它*hd来更改调用者的指针。

另外，不要强制转换malloc()in C的返回值。

Answer 3

if(curr == NULL){
    curr = malloc(sizeof(node));
    curr->right = NULL;
    curr->left = NULL;  // From ks6g10 in order to initialize right and left to NULL
    curr->value = v;
    *hd = curr; // add this
}

顺便说一句，使用calloc而不是malloc. 它将您的节点内存初始化为0

Answer 4

另一种递归添加二叉树的方法可以这样完成：

node *add(node *hd, int v) {
   node* curr = NULL;

   if(!hd){
      curr = malloc(sizeof(node));
      curr->value = v;
      curr->left = NULL;
      curr->right = NULL;
      return curr;
   }
   else {
     if(v < curr->value)
        curr->left = add(curr->left,v);
     else 
        curr->right = add(curr->right,v);  
  }
  return hd;
}

Answer 5

您需要使用 NULL 初始化新形成的节点的左右指针，并让 hd 指向该节点。

void add(node* *hd, int v){
node* curr = *hd;
if(curr == NULL){
    curr = malloc(sizeof(node));
    curr->value = v;
    curr->left=curr->right=NULL;
    *hd = curr;

}else{
    if(v < curr->value){
        add(&curr->left, v);
    }else{
        add(&curr->right, v);
    }
}
}

Answer 6

我是这样做的：

void insert(int data, node *&cur)
{
    if (cur == NULL)
    {
        cur = (struct node*) malloc(sizeof(struct node));
        cur->data = data;
        cur->left = NULL;
        cur->right = NULL;              
    }
    else
    {
        if (data > cur->data)
        {
            insert(data, cur->right);
        }
        else
        {
            insert(data, cur->left);
        }
    }
}