C++类实现BST插入节点触发segfault段错误原因咨询

你的代码触发段错误的核心原因有两个，和是否传入root指针地址没有必然关系，返回值递归的写法本身是可行的，只是逻辑存在疏漏：

• 第一处致命问题：insertUtil函数中创建完新节点后没有及时返回，触发无限递归
  当递归到空指针位置r == NULL时，你虽然创建了新节点赋值给局部变量r，但没有直接return，而是继续执行后续的大小判断逻辑。此时新节点存储的值和待插入值x完全相等，判断x < r->data不成立就会走右分支递归，而新节点的右指针初始为NULL，会再次触发新节点创建，反复执行这个流程就会无限递归，最终栈溢出触发段错误。
• 第二处逻辑疏漏：insert方法调用insertUtil时没有接收返回值，且单独处理root为空的逻辑属于冗余代码
  你设计的insertUtil是通过返回值把当前层的节点指针回传给上一层，用来挂载新创建的节点。但你在insert中调用时没有接收返回值，虽然root非空时第一层返回的是root本身不会出问题，但这种写法不规范，一旦后续逻辑调整很容易出现节点挂载失败的内存泄漏、野指针问题。

修复方案 #

1. 首先确保newNode函数正确初始化新节点的左右指针为空，参考实现：

struct bstNode* newNode(int val) {
    struct bstNode* node = new bstNode;
    node->data = val;
    node->left = nullptr;
    node->right = nullptr;
    return node;
}

2. 修复insertUtil逻辑，新节点创建后直接返回，同时补充相等值的判断避免重复插入：

struct bstNode* Bst::insertUtil(int x, struct bstNode *r){
    if(r == NULL){
        r = newNode(x);
        return r; // 新节点创建后直接返回，终止当前层递归
    }
    if(x < r->data){
        r->left = insertUtil(x, r->left);
    } else if(x > r->data) { // 等值情况不做插入，避免重复节点
        r->right = insertUtil(x, r->right);
    }
    return r;
}

3. 简化insert方法，统一通过返回值更新root，不需要单独判断root为空的场景：

void Bst::insert(int x){
    root = insertUtil(x, root);
}

关于「传root地址就正常」的说明 #

你改成传二级指针（root地址）的写法后能正常运行，本质是因为这种写法下，你遇到空指针时会直接把新节点地址写入上一层指针的内存位置（比如父节点的left/right、root本身），写完通常会直接return，不会触发后续的无限递归，并不是因为传地址的写法天生比返回值写法更正确，两种写法都可以实现BST插入，只是你原来的返回值写法漏了关键的return语句。

内容的提问来源于stack exchange，提问作者segugio