Вставка в двоичное дерево поиска (C), используемое для цикла

Question

У меня возникли проблемы с вставкой в ​​двоичное дерево поиска, используя для цикла, когда я вызываю функцию InorderTraversal, нет вывода, которое я получаю, это пустая строка, как я думаю, остальная часть кода в порядке, единственная проблема заключается в функции вставки.

#include <stdio.h> 
#include <stdlib.h> 
#include <stdbool.h> 

typedef struct BinaryTree{ 

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

node* Insert(node* head, int value) 
{ 
    _Bool flag = true; 

    for(node *temp = head; flag == true; (temp = (value >= temp->data)?(temp->right):(temp->left))) 
    { 
     if(temp == NULL) 
     { 
      temp = (node*)malloc(sizeof(node*)); 
      temp->data = value; 
      temp->left = NULL; 
      temp->right = NULL; 
      flag = false; 
     } 
    } 

    return head; 
} 

void InorderTraversal(node* head) 
{ 
    if(head == NULL) 
    { 
     return; 
    } 

    InorderTraversal(head->left); 
    printf("%d ",head->data); 
    InorderTraversal(head->right); 
} 

int main(void) 
{ 
    node *head = NULL; 

    for(int i = 0; i < 40; i++) 
    { 
     head = Insert(head,i); 
    } 

    InorderTraversal(head); 

    return 0; 
} 

Answer 1

Вот попробуйте эти изменения в вашей функции Insert

node* Insert(node *head, int value) 
{ 

    if(!head)        //Explicitly insert into head if it is NULL 
    { 
     head = malloc(sizeof *head); 
     head->data = value; 
     head->left = NULL; 
     head->right = NULL; 
     return head; 
    } 

    for(node *temp = head,*temp2 = head; ;(temp = (value >= temp->data)?(temp->right):(temp->left))) 
    { 
     if(temp == NULL) 
     { 
      temp = malloc(sizeof *temp); 
      temp->data = value; 
      temp->left = NULL; 
      temp->right = NULL; 

      if(value >= temp2->data) //update previous nodes left or right pointer accordingly 
       temp2->right = temp; 
      else 
       temp2->left = temp; 

      break; 
     } 

     temp2 = temp;  //Use a another pointer to store previous value of node 
    } 

    return head; 
} 

Answer 2

Позови меня с ума, но не следует, что malloc(sizeof(node*)) быть malloc(sizeof node)?
Я не то, что информируется, кроме того, чтобы иметь возможность читать C, так что извините, если это просто неправильно ...

Edit: ... или malloc(sizeof * temp)

Answer 3

При вставке в первый узел, разыменовать неинициализированный указатель здесь:

temp->data 

Где температура находится голова и голова в неинициализированном и указывая на NULL.

Таким образом, вы должны сначала сделать специальный случай, когда голова NULL:

if(!head) 
{ 
    head = malloc(sizeof(node)); 
    head->data = value; 
    head->left = NULL; 
    head->right = NULL; 

    return head ; 
} 

Когда вы будете продолжать добавлять элементы не обновлять указатель последнего узла. Ваш цикл for должен иметь дополнительный указатель на предыдущий узел и когда вы дойдете до последнего узла и найдите NULL, обновите предыдущие указатели слева или справа.

if(temp == NULL) //wrong, should be: not equal 
{ 
    temp = (node*)malloc(sizeof(node*)); //wrong, should be: sizeof the node not the pointer 
    temp->data = value; 
    temp->left = NULL; 
    temp->right = NULL; 
    flag = false; //use break instead 
} 

здесь предыдущий указатель узла слева или справа не обновляется, и при поиске вы не можете найти ни одного узла.