递归二叉树插入

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以更改调用者的指针。

另外，don't cast the return value of 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 
} 

BTW使用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，让您的高清点该节点。

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); 
     } 
    } 
}