在int中將int與NULL進行比較 - 本教程不正確嗎？

Question

我在看本教程http://www.learn-c.org/en/Binary_trees，並在插入函數中將int與NULL進行比較。它似乎在tut網站上運行良好，但它對我無效，我的研究告訴我它不應該工作。我的代碼如下。

1. 我錯了，或者是教程錯誤？

2. 如果教程有誤，有什麼辦法可以動態設置BST的第一個節點的值？我想過檢查左右兩者是否都是空的，但這隻會重置第一個節點。有一個節點的值的第三個指針看起來很浪費，但也許這是唯一的方法？

   #include <stdio.h> 
   #include <malloc.h> 
   struct bstNode { 
       int val; 
       struct bstNode *left; 
       struct bstNode *right; 
   }; 
   
   int insert(struct bstNode *head, int val); 
   
   void printDFS(struct bstNode *head); 
   
   int main() { 
       struct bstNode *bstTree = malloc(sizeof(struct bstNode)); 
       insert(bstTree, 8); 
       insert(bstTree, 5); 
       insert(bstTree, 98); 
       insert(bstTree, 2); 
       insert(bstTree, 15); 
       insert(bstTree, 65); 
       insert(bstTree, 15); 
       printDFS(bstTree); 
   } 
   
   int insert(struct bstNode *head, int val) { 
       //This is the problem statement, it contains random data when I debug as it's uninitialized 
       if (head->val == NULL) { 
        head->val = val; 
        return 0; 
       } 
   
       if (val < head->val) { 
        if (head->left != NULL) { 
         return insert(head->left, val); 
        } else { 
         head->left = malloc(sizeof(struct bstNode)); 
         head->left->val = val; 
         return 0; 
        } 
       } else { 
        if (head->right != NULL) { 
         return insert(head->right, val); 
        } else { 
         head->right = malloc(sizeof(struct bstNode)); 
         head->right->val = val; 
         return 0; 
        } 
       } 
   } 
   
   void printDFS(struct bstNode *head) { 
       if (head->left != NULL) printDFS(head->left); 
       printf("%d ", head->val); 
       if (head->right != NULL) printDFS(head->right); 
   } 
   

Answer 1

該教程是不正確更換。這使得兩個無效的假設。

1. 它假定NULL相當於0。雖然在大多數情況下，它在(void *)0被定義，它不會總是一定是這種情況。它也在使用一個指針，其中預期的是int，所以依賴於指針的表示。
2. 它假定val中的初始節點爲0。當內存分配爲malloc時，內存未被初始化（正如您找到的那樣）。

此代碼還通過假定0不是要插入列表中的有效值來起作用，因爲它將0用於標記值以表示空列表。

使用0作爲標記的假設，代碼可以固定如下。

首先，在創建初始節點時，使用calloc而不是malloc。 calloc函數會將所有字節初始化爲0.這將爲您提供val設置爲0並且left和right設置爲NULL的初始成員。

此外，您應該始終檢查返回值malloc,calloc和realloc以防萬一它們失敗。

int main() { 
    struct bstNode *bstTree = calloc(1, sizeof(struct bstNode)); 
    if (bstTree == NULL) { 
     perror("calloc failed"); 
     exit(1); 
    } 

其次，獲得通過更換NULL以0

if (head->val == 0) { 

做這些事情2應該得到的代碼都正常工作擺脫整數/指針比較的。

回過頭來看看大圖，這裏有一些設計問題。

insert函數返回一個int，但從不使用返回值。實際上，此函數只能返回0.更好的是將返回類型更改爲void。

空樹包含一個帶有標記值的單個節點，可以限制您可以放入的值。通過使頭節點成爲NULL指針，最好有一棵空樹。

void insert(struct bstNode **head, int val) { 
    if (*head == NULL) { 
     *head = malloc(sizeof(struct bstNode)); 
     if (*head == NULL) { 
      perror("malloc failed"); 
      exit(1); 
     } 
     (*head)->val = val; 
     (*head)->left = NULL; 
     (*head)->right = NULL; 
     return; 
    } 

    if (val < (*head)->val) { 
    ... 

然後調用它像這樣：

struct bstNode *bstTree = NULL; 
insert(&bstTree, 8); 
... 

Answer 2

if (head->val == NULL) { 
    head->val = val; 
    return 0; 
} 

我覺得政黨成員要檢查，如果val爲NULL，因爲插入返回一個int值。你應該通過類似的東西代替插入功能：

struct bstNode *new_bstNode(int val, struct bstNode *left, struct bstNode *right) 
{ 
    struct bstNode *elem = malloc(sizeof(*elem)); 
    if (elem == NULL) 
     return NULL; 
    elem->val = val; 
    elem->left = left; 
    elem->right = right; 
    return elem; 
} 

struct bstNode *insert(struct bstNode *head, int val) { 
    if (head == NULL) 
     return new_bstNode(val, NULL, NULL); 

    if (val < head->val) { 
     if (head->left != NULL) 
      return insert(head->left, val); 
     else 
      return head->left = new_bstNode(val, NULL, NULL); 
    } else { 
     if (head->right != NULL) 
      return insert(head->right, val); 
     else 
      return head->right = new_bstNode(val, NULL, NULL); 
    } 
} 

所以你的主要需求是由

int main() { 
    struct bstNode *bstTree = insert(bstTree, 8); 
    insert(bstTree, 5); 
    insert(bstTree, 98); 
    insert(bstTree, 2); 
    insert(bstTree, 15); 
    insert(bstTree, 65); 
    insert(bstTree, 15); 
    printDFS(bstTree); 
}