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

有人可以指出我的错误。

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

任何建议是有帮助的。

1. 避免使用全局变量。移动root成为main中的局部变量。
2. 更改create的签名和目的，以便它只创建一个节点，而不是其他任何东西。
3. 请勿投下malloc的结果。见Specifically, what's dangerous about casting the result of malloc?
4. 使用insertNode而不是create在main。拨打create从insertNode在正确的地方。
5. 添加一个打印树内容的函数。
6. 在测试代码时，使用随机数代替用户输入的数据。
7. 通过使用命令行参数，可以灵活地创建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 2

用于这种树插入算法是（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返回;在左边称自己;打印值;打电话给自己→将打印按小到大排序的内容。

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; 

你去功能，并检查是否（数据< =根 - >值）。在这两种情况下（true和false），都会再次调用insertNode函数，然后再次调用insertNode - 您将永远不会收到返回语句。递归函数需要有基本的情况下返回一些值，而无需再次调用自己。

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

在二叉搜索树的情况下，基本情况是，当你的密钥（数据）要插入的A）插入钥匙，比目前的节点，当前节点的右孩子越大叶（空）或B ）插入的关键字比当前节点更小（或等于您要解析关系的方式），并且当前节点的左侧子项为空。 (data > cur->data && cur->right == NIL)或(data < cur->data && cur->left == NIL)。如果您遇到这些情况之一，只需将新节点设置为当前节点的子节点或子节点。