C语言实现二叉树时出现Segmentation Fault问题求助

我是C语言新手，在实现二叉搜索树插入时遇到问题。运行代码时先打印"yes"，随后触发段错误。我听说可以用双指针解决这个问题，想确认是否可行，以及具体怎么实现（我对双指针不太熟悉）。

注1：假设fscanf和输入文件的打开、使用均正常。
注2：输入文件内容如下：

i 10
i 20
i 30
i 40
i 50
i 60
i 70
i 80
i 90
i 99
i 15
i 14
i 12
i 25
i 28
i 95
i 35
i 38
i 11
i 23
i 22

以下是我的代码：

二叉树实现代码 #

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

typedef struct BSTnode{
  int key;
  int subtree_size;
  struct BSTnode* left;
  struct BSTnode* right;
} TreeNode;

TreeNode* newNode(int value){
  TreeNode *node = malloc(sizeof(TreeNode));
  node->key = value;
  node->left = NULL;
  node->right = NULL;
  node->subtree_size = 1;
  return node;
}

TreeNode* insert(TreeNode* root, TreeNode* to_insert){
  if(root == NULL){
    root = newNode(to_insert->key);
  }
  else if(to_insert->key> root->key){
    if(root->right == NULL){
      root->right = to_insert;
      return root;
    }
    else{
      root->right = insert(root->right, to_insert);
    }
  }
  else if(to_insert->key< root->key){
    if(root->left == NULL){
      root->left = to_insert;
      return root;
    }
    root->left = insert(root->left, to_insert);

  }

  root->subtree_size = 1 + (root->left? root->left->subtree_size: 0) + (root->right? root->right->subtree_size: 0);
  return root;
}

int find(TreeNode* root, int value){
  if(root == NULL || root->key == value){
    return root->key;
  }
  else if(value > root->key){
    return find(root->right, value);
  }
  else{
    return find(root->left, value);
  }
}

main函数代码 #

int main (int argc, char* argv[]){
  FILE* input;

  input = fopen(argv[1], "r");

  char oper;
  int num;

  TreeNode* root = NULL;
  
  while(fscanf(input, "%c", &oper) != EOF){
    if(oper == 'i'){
      fscanf(input, " %d", &num);
      TreeNode* to_insert = newNode(num);
      insert(root, to_insert);
      //printf("operation: %c, num: %d\n", oper, num);
    }
    if(oper == 'r'){
//do some other thing
    }
  }
  if(root == NULL){
    printf("yes\n");
  }
  printf("size: %d\n", root->subtree_size);
  printf("left size: %d\n", root->left->subtree_size);
  printf("right size: %d\n", root->right->subtree_size);
  fclose(input);
}

问题原因与双指针解决方案 #

问题根源 #

核心问题是**main中调用insert时未接收返回值，也未通过指针的指针修改root本身**。C语言是值传递，函数参数是原变量的副本：当root初始为NULL时，insert内部创建的新节点只会赋值给函数内的局部root参数，不会影响main里的root变量。因此main中的root始终是NULL，后续访问root->subtree_size必然触发段错误。

双指针方案的可行性 #

完全可行。双指针（即指针的指针TreeNode**）可以让函数直接修改外部的指针变量，而非修改副本。

具体实现步骤 #

1. 修改insert函数的参数与逻辑：
   • 将第一个参数改为TreeNode** root（指向指针的指针）
   • 内部访问原指针时用*root替代原来的root
   • 直接修改*root的值来更新根节点
   • 移除多余的节点创建逻辑（原代码会重复创建节点导致内存泄漏）

修改后的insert函数：

void insert(TreeNode** root, TreeNode* to_insert){
  if(*root == NULL){
    // 直接修改外部的root指针，指向传入的新节点
    *root = to_insert;
  }
  else if(to_insert->key > (*root)->key){
    insert(&((*root)->right), to_insert);
  }
  else if(to_insert->key < (*root)->key){
    insert(&((*root)->left), to_insert);
  }
  // 若key相等，可自行添加处理逻辑（比如忽略或更新）

  // 更新当前节点的子树大小
  (*root)->subtree_size = 1 + 
                          ((*root)->left ? (*root)->left->subtree_size : 0) + 
                          ((*root)->right ? (*root)->right->subtree_size : 0);
}

2. 修改main中的调用方式：
   传入root的地址，而非root本身：

if(oper == 'i'){
  fscanf(input, " %d", &num);
  TreeNode* to_insert = newNode(num);
  insert(&root, to_insert); // 传入指针的地址
}

额外问题修复 #

• find函数空指针访问问题：原函数在root == NULL时返回root->key会触发段错误，可修改为返回指针更安全：

TreeNode* find(TreeNode* root, int value){
  if(root == NULL || root->key == value){
    return root;
  }
  else if(value > root->key){
    return find(root->right, value);
  }
  else{
    return find(root->left, value);
  }
}

• main中打印逻辑的空指针判断：访问子节点前需先判断是否为空，避免段错误：

if(root == NULL){
  printf("yes\n");
  fclose(input);
  return 0; // 直接退出，避免后续访问空指针
}
printf("size: %d\n", root->subtree_size);
// 打印左子树大小前判断是否存在
if(root->left){
  printf("left size: %d\n", root->left->subtree_size);
} else {
  printf("left size: 0\n");
}
// 打印右子树大小前判断是否存在
if(root->right){
  printf("right size: %d\n", root->right->subtree_size);
} else {
  printf("right size: 0\n");
}

内容的提问来源于stack exchange，提问作者The-coder-E