二叉树插入出现段错误：如何用双指针实现节点插入与内存分配？

核心错误分析 #

你的bst_insert函数触发段错误的根本原因是第一个判断条件逻辑错误：
你判断的是tree == NULL，但tree是传入的双指针本身，正常调用时它永远不会为NULL（调用时应该传&root这类指针的地址）。真正需要判断的是*tree == NULL——也就是当前要插入的位置对应的节点指针是否为空。

当插入第一个节点时，*tree是NULL，但你的代码跳过了内存分配逻辑，直接进入else if(key == (*tree)->key)，此时解引用(*tree)->key相当于访问空指针指向的内存，直接触发段错误。

修正后的代码 #

#include <stdio.h>
#include <stdlib.h>

typedef struct bst_node {
  char key;               
  int value;         
  struct bst_node *left; 
  struct bst_node *right; 
} bst_node_t;

void bst_insert(bst_node_t **tree, char key, int value) {
  // 判断当前节点位置是否为空，为空则插入新节点
  if (*tree == NULL) {
    // 为新节点分配内存，并赋值给*tree（修改调用者传入的指针变量）
    *tree = malloc(sizeof(bst_node_t));
    // 必须检查内存分配是否成功
    if (*tree == NULL) {
      perror("malloc failed");
      exit(EXIT_FAILURE);
    }
    (*tree)->key = key;
    (*tree)->value = value;
    (*tree)->left = NULL;
    (*tree)->right = NULL;
  }
  else if (key == (*tree)->key) {
    // 键已存在，更新对应的值
    (*tree)->value = value;
  }
  else if ((*tree)->key > key) {
    // 键小于当前节点，递归插入左子树
    bst_insert(&(*tree)->left, key, value);
  } else {
    // 键大于当前节点，递归插入右子树
    bst_insert(&(*tree)->right, key, value);
  }
}

双指针的正确使用要点 #

• 双指针的作用：让函数能够修改调用者传入的指针变量的值（比如初始化根节点，或者更新子节点的指针）。如果只用单指针，函数只能修改指针指向的内容，无法修改指针本身。
• 内存分配的正确姿势：分配新节点后，要把malloc返回的地址赋值给*tree，而不是tree。tree是函数的局部变量，修改它不会影响调用者的变量；*tree才是调用者传入的指针本身，修改它才能让调用者看到新分配的节点。
• 必做的错误检查：永远要检查malloc的返回值，如果内存分配失败，malloc会返回NULL，后续操作空指针会导致崩溃。

调用示例 #

int main() {
  // 初始化根节点为空
  bst_node_t *root = NULL;
  // 插入节点，传入根节点指针的地址
  bst_insert(&root, 'a', 10);
  bst_insert(&root, 'c', 30);
  bst_insert(&root, 'b', 20);
  
  // 后续可添加遍历、销毁等操作
  return 0;
}

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