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