问用C语言搜索BST元素函数
EN

Stack Overflow用户

提问于 2018-10-16 05:30:50

回答 2查看 62关注 0票数 1

我想这一定是个简单的问题，但我不知道出了什么问题。

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

据我所知，当我引用空指针时，切分错误大多会出现，但我不认为搜索函数是错误的。我想我在插入函数或初始化树根时出错了，但我不知道出了什么问题。

pointers

binary-search-tree

校园云服务器 2H2G30元起

云+校园是针对学生用户推出的扶持计划，2核2G云服务器30元起，1核1G云数据库4元起，并享受免费体验6个月云开发

回答 2

Stack Overflow用户

回答已采纳

发布于 2018-10-16 05:39:27

出于好奇，我查了一下密码。

我不认为搜索功能是错误的

我不这样认为!

请看这一行代码：

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

如果cursor是NULL，会发生什么?访问cursor->value，即Undefined Behavior (因为不允许访问NULL )。这值得一次Segmentation fault。

最好是：

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。

票数 1

Stack Overflow用户

发布于 2018-10-16 06:26:47

insert函数的问题在于它无法更新root的值。返回新的叶节点，但这对跟踪root可能没有多大用处。

要更改root，必须传入指向它的指针，例如：

insert(&root, 10);

然后你可以像这样改变你的功能。它沿着树遍历，传入指向当前节点的左或右分支的指针，直到它发现该节点还不存在，然后创建它。

tree *insert(tree **root, int X)
{
    if(*root == NULL)
    {
        *root = (tree *)malloc(sizeof(tree));
        (*root)->value = X;
        (*root)->left = (*root)->right = (*root)->parent = NULL;
        return(*root);
    }
    else
    {
        tree *ret;
        if(X >= (*root)->value)
        {
            ret=insert(&(*root)->right, X);
            (*root)->right->parent=*root;
        }
        else
        {
            ret=insert(&(*root)->left, X);
            (*root)->left->parent=*root;
        }
        return ret;
    }
}