插入二進制搜索樹（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 
} 

這裏前一個節點指針向左或向右不更新，當你搜索時你找不到任何節點。