c - 在 C 中搜索 BST 元素函数

Question

我认为这一定是个简单的问题，但我不知道哪里出了问题..

gdb 说

Program received signal SIGSEGV, Segmentation fault.
0x000055555555543e in searchNode (root=0x0, X=1) at problem1.c:40
40      while(cursor->value != X || cursor != NULL)

插入和搜索功能

typedef struct TreeNode
{
    int value;
    struct TreeNode *left;
    struct TreeNode *right;
    struct TreeNode *parent;
}   tree;

tree *insert(tree *root, int X)
{
    tree *cursor = root;
    tree *parent;

    while(cursor != NULL)
    {
        parent = cursor;
        if(X >= cursor->value)
            cursor = cursor->right;
        else
            cursor = cursor->left;
    }
    cursor = (tree *)malloc(sizeof(tree));
    cursor->value = X;
    cursor->left = cursor->right = NULL;
    cursor->parent = parent;
        return cursor;  
}

tree *searchNode(tree *root, int X)
{
    tree *cursor = root;

    while(cursor->value != X || cursor != NULL)
    {
        if(X >= cursor->value)
            cursor = cursor->right;
        else
            cursor = cursor->left;
    }

    if(cursor == NULL)
        return NULL;

    else if(cursor->value == X)
        return cursor;
}

主要功能

int main()
{
    tree *root = (tree *)malloc(sizeof(tree));
    root = NULL;

    insert(root, 10);
    insert(root ,20);
    insert(root, 5);
    insert(root, 1);
    insert(root, 15);
    insert(root, 20);
    insert(root, 30);
    insert(root, 100);
    insert(root, 40);
    insert(root, 50);

    node = searchNode(root, 1);
}

据我所知，段错误主要出现在我引用 NULL 指针时，但我认为搜索功能没有错。 我想我在插入函数或初始化树根时犯了错误，但我不知道出了什么问题..

Answer 1

出于好奇，我查看了代码。

i don't think searching function is wrong

我不同意!

看看这行代码:

while(cursor->value != X || cursor != NULL)

如果 cursor 为 NULL 会发生什么？ cursor->value 被访问，即 Undefined Behavior (因为不允许访问 NULL)。这值得一个段错误。

更好的做法是:

while (cursor != NULL && cursor->value != X)

或更短:

while (cursor && cursor->value != X)

从 gdb 中调用 OP 的片段

Program received signal SIGSEGV, Segmentation fault.
0x000055555555543e in searchNode (root=0x0, X=1) at problem1.c:40
40      while(cursor->value != X || cursor != NULL)

(我第一眼没意识到)这对我来说听起来很合理。

根据 (root = 0x0)，searchNode() 似乎是为一棵空树调用的(root 是 NULL )。因此，tree *cursor = root; 使用 NULL 指针(以及上面的其余部分)初始化 cursor。