BST递归插入时给叶子节点子节点赋新节点指针出现段错误问题

• 核心错误为非终止场景下的返回值不符合二叉搜索树递归插入的逻辑：当前代码所有分支最终都返回待插入的新节点node，递归回溯时会把上层父节点的左/右子节点指针全部错误覆盖为新插入的节点，直接破坏原有树的结构，导致大量节点丢失、指针非法访问，最终触发段错误。
  举个简单的复现场景：现有根节点10，右子节点为20，插入30时，递归到20的右子节点（空），返回30给20的右指针赋值是正确的，但20所在的递归层最终也返回30，会导致根节点10的右子节点被错误修改为30，节点20直接从树中丢失，后续遍历到该分支就会出现逻辑错误甚至崩溃。
• 补充小问题：base case的打印语句缺少换行符，可能导致输出混乱，但这不是触发段错误的原因。

仅需要修改非终止场景下的返回值为当前子树的原有根节点*root即可：

struct node * addNode(struct node ** root, struct node * node){
    //base case: 到达空节点位置，返回新节点作为当前子树的根
    if (*root == NULL){
        printf("reached with root with node key = %i\n", node->key);
        return node;
    }
    if ((node -> key) > ((*root)->key)){ //插入右子树
        printf("node key is : %i, tree's node key is: %i\n", (node -> key), ((*root)->key));
        (*root)->right = addNode(&((*root)->right), node);
    } else { //插入左子树
        printf("node key is : %i, tree's node key is: %i\n", (node -> key), ((*root)->key));
        (*root)->left = addNode(&((*root)->left), node);
    }
    // 非终止条件下返回当前子树的原有根节点
    return *root;
}

如果你不想通过返回值赋值的方式实现，也可以修改为无返回值的实现，逻辑更直观，不需要处理返回值覆盖的问题：

void addNode(struct node ** root, struct node * node){
    //base case: 直接修改传入的指针指向新节点
    if (*root == NULL){
        printf("reached with root with node key = %i\n", node->key);
        *root = node;
        return;
    }
    if ((node -> key) > ((*root)->key)){
        printf("node key is : %i, tree's node key is: %i\n", (node -> key), ((*root)->key));
        addNode(&((*root)->right), node);
    } else {
        printf("node key is : %i, tree's node key is: %i\n", (node -> key), ((*root)->key));
        addNode(&((*root)->left), node);
    }
}

测试时需要确认传入的node指针已经完成内存分配和字段初始化，避免node本身是野指针、key字段未初始化的问题。

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