遞歸二叉樹插入

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