插入二进制搜索树（C）使用for循环

Question

我在使用for循环插入二进制搜索树时遇到问题，当我调用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

这里尝试在插入函数这些变化

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，所以原谅我，如果这是完全错误的其他...

编辑：...或者malloc(sizeof * temp)

Answer 3

当您插入第一个节点，你在这里解引用未初始化的指针：

temp->data 

其中temp是未初始化的头部和头部并指向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 
} 

这里前一个节点指针向左或向右不更新，当你搜索时你找不到任何节点。