C中的二进制搜索树程序表现异常

Question

我编写了以下代码来创建 二叉搜索树 ，但是当创建函数被调用并且它第一次尝试调用 insertNode(...)程序挂了。以下是代码：

struct BstNode{
    int value;
    struct BstNode* left;
    struct BstNode* right;
};

struct BstNode *root; 

struct BstNode* insertNode(struct BstNode* root, int data){
    if(data <= root->value)
        root->left = insertNode(root->left, data);
    else
        root->right = insertNode(root->right, data);

    printf("%d  ",root->value);
    return root;
}


void create(struct BstNode* root){ 
    int data;
    if(root == NULL){
        //create the root node
        printf("\nInside create");
        root = (struct BstNode*) malloc(sizeof(struct BstNode));
        printf("\nData :: ");
        scanf("%d",&data);
        root->value = data;
        root->left = NULL;
        root->right = NULL;
    }
    else{
        printf("\nCalling insertNode()");
        printf("\nData :: ");
        scanf("%d",&data);
        root = insertNode(root, data);  // The program hangs up here : the very first time this line is executed
        printf("\nCalled insert");
    }
}

int main(){
    root = NULL;
    int i;
    for(i=0;i<5;i++){
        create(root);
        printf("%d ",root->value); // For checking the value 
    }
    return 0;
}

谁能指出我的错误。任何建议都有帮助。

Answer 1

插入这种树的算法是(insert(node, value)):

如果node为NULL分配一个节点，设置left/right为NULL（它是一片叶子），设置值为value，return分配的节点
else if value < node->value: node->left = insert(node->left, value)
其他：node->right = insert(node->right, value)
return node（这样我们的代码就齐了）

假设您的 main 插入是相同的：root = insert(root, val).

除了 return 值之外，您还可以将指针传递给您的指针 (&root)，但是您必须在函数中处理取消引用它。您似乎对指针不是很熟悉，如果您打算使用此类结构，您真的应该阅读更多相关内容。

另请注意，main 函数中的 printf 没有用：在那种树中，根值始终是第一个插入的值（或者您必须在树中执行移位以平衡分支，但这是另一个问题）。打印一个 btree 也意味着一个递归函数，你必须选择如何打印它（深度优先，排序......）。示例：如果节点为 NULL return；称呼自己在左边；打印值；在右边称呼自己 → 将按从小到大的顺序打印内容。

Answer 2

Could anybody point out my mistake.

主要问题是 createNode 修改了 root 的本地副本。全局变量 root 永远不会被修改，并保持设置为 NULL.

Any suggestion(s) is helpful.

避免使用全局变量。移动 root 成为 main.
更改 create 的签名和用途，使其仅创建一个节点，仅此而已。
不要投射 malloc 的结果。参见 Specifically, what's dangerous about casting the result of malloc?
在 main 中使用 insertNode 而不是 create。在正确的地方从 insertNode 调用 create。
添加打印树内容的函数。
测试代码时，使用随机数代替用户输入的数据。
允许使用命令行参数灵活地创建 5 个以上的节点。

这是我对该程序的建议：

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

struct BstNode{
   int value;
   struct BstNode* left;
   struct BstNode* right;
};

struct BstNode* create(int data){ 
   printf("Creating a node with value: %d\n", data);
   struct BstNode* node = malloc(sizeof(*node));
   node->value = data;
   node->left = NULL;
   node->right = NULL;
   return node;
}

struct BstNode* insertNode(struct BstNode* root, int data){
   if ( root == NULL )
   {
      return create(data);
   }

   if(data <= root->value)
      root->left = insertNode(root->left, data);
   else
      root->right = insertNode(root->right, data);

   return root;
}

void print(struct BstNode* node, int indent, char const* nodeName)
{
   if ( node == NULL )
   {
      return;
   }

   for (int i = 0; i < indent; ++i )
   {
      printf("   ");
   }
   printf("%s: %d\n", nodeName, node->value);
   print(node->left, indent+1, "left");
   print(node->right, indent+1, "right");
}

int main(int argc, char** argv){
   struct BstNode *root = NULL; 
   int i;
   int data;
   int num = 5;
   if ( argc > 1 )
      num = atoi(argv[1]);

   srand(time(NULL));
   for(i=0;i<num;i++){
      data = rand()%10000;
      root = insertNode(root, data);
   }

   printf("\n");
   print(root, 0, "root");
   return 0;
}

Answer 3

insertNode 函数无限递归导致程序崩溃。

更具体地说

struct BstNode* insertNode(struct BstNode* root, int data){
  if(data <= root->value)
      root->left = insertNode(root->left, data);
  else
      root->right = insertNode(root->right, data);

printf("%d  ",root->value);
return root;

你进入函数并检查 if(data <= root->value)。在这两种情况下（真和假）你再次调用 insertNode 函数，然后一次又一次地调用 insertNode - 你永远不会到达 return 语句。递归函数需要具有 return 一些值而无需再次调用自身的基本情况。

thisFunction()
   if (base case)
     return value;
   else
     return thisFunction()

在二叉搜索树的情况下，基本情况是当您插入的键（数据）是 A) 插入的键大于当前节点并且当前节点的右子节点是叶（空）或 B) 插入key 小于（或等于取决于你想如何解决关系）当前节点和当前节点的左子节点为 null .(data > cur->data && cur->right == NIL) 或 (data < cur->data && cur->left == NIL)。如果您遇到其中一种情况，只需将新节点设为当前节点的右子节点或左子节点即可。

C中的二进制搜索树程序表现异常

Binary Search Tree program in C behaving oddly

c

binary-tree

linked-list

binary-search-tree