用C语言搜索BST元素函数
我想这一定是个简单的问题，但我不知道出了什么问题。
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);
}据我所知，当我引用空指针时，切分错误大多会出现，但我不认为搜索函数是错误的。我想我在插入函数或初始化树根时出错了，但我不知道出了什么问题。
回答 2
Stack Overflow用户
发布于 2018-10-16 13: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。
Stack Overflow用户
发布于 2018-10-16 14: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;
}
}因此，当您第一次调用它时，它将为您填充root。第二次，它将传入指向root->right的指针，这将成为insert函数中的新root，因为它是NULL，因此将创建它。然后为了完整起见，它更新了parent链接。
https://stackoverflow.com/questions/52836635
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号