C中的二叉搜索树程序行为奇怪

我编写了以下代码来创建二叉搜索树，但是当创建函数被调用并且它第一次尝试调用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;
}

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

谁能指出我的错误。

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

任何建议都是有帮助的。

避免使用全局变量。将root移动到 main 中的局部变量。
更改create的签名和用途，使其仅创建一个节点，而不创建其他节点。
不要投malloc的结果。具体来看，铸造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: %dn", 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: %dn", 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;
}

在这样的树中插入的算法是(insert(node, value)(：

如果node为 NULL 分配节点，则将左/右设置为 NULL(它是一个叶(，将值设置为 value，返回分配的节点
否则如果value < node->value：node->left = insert(node->left, value)
其他： node->right = insert(node->right, value)
return node(这样我们就有了同构的代码(

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

除了返回值，您还可以将指针传递给指针(&root(，但是您必须处理在函数中取消引用它的问题。你似乎对指针不是很熟悉，如果你打算玩这样的结构，你真的应该阅读更多关于它的信息。

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

函数 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 - 您将永远不会得到返回语句。递归函数需要具有基本大小写，该基本情况返回一些值而无需再次调用自身。

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

在二叉搜索树的情况下，基本情况是当您插入的键(数据(是 A( 插入的键大于当前节点，并且当前节点的右子节点是叶子节点 (null( 或 B( 插入的键小于(或等于，具体取决于您想要如何解析关系(比当前节点和当前节点的左子节点为 null。(data > cur->data && cur->right == NIL)或(data < cur->data && cur->left == NIL).如果您遇到这些情况之一，只需使新节点成为当前节点的右子节点或左子节点即可。

相关内容

最新更新

热门标签：