c - BST 实现函数中的段错误

Question

这是我在二叉搜索树中插入项目的实现。

void insert(struct Node* root,int item){
if(root==NULL){
    root = newNode(item); // newNode is a function which creates new node, initialized it with item & return pointer of the new node.
}
if(item < root->item)
    insert(root->left,item);
else
    insert(root->right,item);
}

但我不知道为什么它会在驱动程序中调用以下代码时出现段错误？

struct Node* root = NULL;
insert(root,50);

Answer 1

您可能有无限递归。

然后通过初始调用 root将是一个空指针，这意味着您将创建一个新的根节点。然后我们去检查if(item < root->item)这将是错误的，导致程序执行 else条款和调用insert递归地。

如果newNode设置 left和 right指向 NULL 的指针，然后整个事情将重新开始，创建一个新节点并转到 else子句并递归调用自身。

解决方案是另一个 else ，如

if (root == NULL) {
    ...
} else if (item < root->item) {
    ...
} else {
    ...
}

如果您只是使用调试器 来捕获崩溃或单步执行代码，您会很快 发现问题。以后先用调试器捕捉崩溃，定位崩溃发生的时间和地点，检查函数调用栈。

---

如果另一方面newNode 不初始化 left和 right节点结构的指针，那么你将有undefined behavior ，这通常会导致崩溃。

动态分配函数，如malloc 不 初始化它分配的内存。内存的内容不确定。取消引用此类指针会导致所述 UB(未定义行为)。

这也可以在调试器的帮助下快速检测到。

---

如果您解决上述问题，最后导致崩溃的第三个可能原因是，当您将参数传递给 C 中的函数时，它是按值传递的。这意味着值被复制到参数中，并且函数内部的参数就像任何其他局部变量一样，一旦参数超出范围，对参数(赋值)的所有更改都会丢失函数返回。

这意味着在初次调用 insert 之后变量 root将仍然是一个空指针。

我的评论中提到了解决方案。