二叉搜索树（BST）插入操作触发Segmentation Fault（core dumped）问题排查求助

问题描述 #

我现在在实现一个二叉搜索树（BST），需要编写递归的find函数、insert函数和operator[]重载，整体用来完成BST的插入逻辑。但运行测试用例1时，出现了segmentation fault (core dumped)的错误，我不确定是递归find函数还是insert函数出了问题，希望能得到大家的反馈和帮助。

我的完整代码和测试用例如下：

#include <compare>
#include <cstddef>
#include <format>
#include <iostream>
#include <string>
#include <utility>


template<typename Key, typename Value>
struct BST
{
  using KeyValue_Pair = std::pair<Key const, Value>;

  struct Node
  {
    Node() = default;
    Node( KeyValue_Pair const & pair ) : _pair{ pair } {}

    KeyValue_Pair _pair = { Key{}, Value{} };

    Node * _left   = nullptr;
    Node * _right  = nullptr;
    Node * _parent = nullptr;
  };

  Node *      _root = nullptr;
  std::size_t _size = 0;


Node * find( Key const & key )
 {
   return find(key, _root);  // 委托给私有辅助函数
 }

Node* find(Key const& key, Node* current) {
    // 基准情况：未找到节点
    if (current == nullptr) {
        return nullptr;
    }

    // 匹配：找到目标节点
    if (key == current->_pair.first) {
        return current;
    }

    // 递归：搜索左或右子树
    if (key < current->_pair.first) {
        return find(key, current->_left);
    } else {
        return find(key, current->_right);
    }
}

Node * insert( KeyValue_Pair const & pair ) {
     Node * newNode = new Node( pair );
     if(_root == nullptr){
      _root = newNode;
      ++_size;
      return newNode;
    }
    Node * current = _root;
    Node * parent  = nullptr;

    while(current != nullptr){
      parent = current;
      auto comp   = std::compare_weak_order_fallback( pair.first, current->_pair.first );
      if( comp == 0 ) return current;
      else if(comp < 0 ) current = current->_left;
      current = current->_right;
    }
    auto comp = std::compare_weak_order_fallback( pair.first, current->_pair.first );
    if( comp < 0 ) parent->_left = newNode;
    else parent->_right = newNode;

    newNode->_parent = parent;
    ++_size;
    return newNode;
}

Value & operator[]( Key const & key )
{
  return insert( { key, Value{} } )->_pair.second;
}   

// 以下代码是原有代码
void print()
{
  auto count = 0uz;
  print( _root, count );
}

void print( Node * current, std::size_t & count )  // 中序遍历
{
  // 基准情况
  if( current == nullptr ) return;

  // 递归左子树
  print( current->_left, count );

  // 访问当前节点
  auto && [key, value] = current->_pair;
  std::cout << std::format( "{:3}:  {{{}, {}}}\n", ++count, key, value );

  // 递归右子树
  print( current->_right, count );
}

~BST() noexcept
{ clear(); }
};

int main()
{
  BST<unsigned int, std::string> myTree;

  std::cout << "Test Case 1:\n";                     //          50         //
  myTree[50] = "indeed";                             //        /   \        //
  myTree.insert( { 40, "Structures" } );             //       40    60      //
  myTree.insert( { 60, "very" } );                   //      / \   / \      //
  myTree.insert( { 30, "Lego" } );                   //     30 45 55  70    //
  myTree.insert( { 45, "are" } );
  myTree[55] = "truly";
  myTree[70] = "entertaining";
  myTree.print();
  std::cout << "------------------------------\n";
}

问题分析与修复 #

你的段错误问题完全来自insert函数的逻辑错误，递归find函数的逻辑是正确的，不需要修改。主要有两个核心问题：

1. While循环内的分支逻辑混乱

在insert的while循环中，你写了：

else if(comp < 0 ) current = current->_left;
current = current->_right;

这个逻辑完全错误：不管comp <0的条件是否满足，你都会执行current = current->_right，这会导致：

• 当comp <0时，current先被赋值为左子树，然后立刻被覆盖成右子树，完全打乱了搜索路径；
• 循环的终止条件和搜索逻辑彻底失效，最终循环结束时current会变成nullptr。

2. 循环结束后访问空指针的成员

当while循环退出时，current已经是nullptr，但你紧接着执行了：

auto comp = std::compare_weak_order_fallback( pair.first, current->_pair.first );

这里尝试访问空指针current的成员，直接触发了段错误。

修复后的insert函数 #

下面是修正后的insert函数，我标注了关键修复点：

Node * insert( KeyValue_Pair const & pair ) {
     Node * newNode = new Node( pair );
     if(_root == nullptr){
      _root = newNode;
      ++_size;
      return newNode;
    }
    Node * current = _root;
    Node * parent  = nullptr;

    while(current != nullptr){
      parent = current;
      auto comp   = std::compare_weak_order_fallback( pair.first, current->_pair.first );
      if( comp == 0 ) {
          // 键已存在，释放新创建的节点避免内存泄漏，返回已存在的节点
          delete newNode;
          return current;
      } else if(comp < 0 ) {
          current = current->_left;
      } else {
          // 只有当comp>0时，才去右子树
          current = current->_right;
      }
    }
    // 此时parent是最后一个非空节点，用它的键来比较决定插入位置
    auto comp = std::compare_weak_order_fallback( pair.first, parent->_pair.first );
    if( comp < 0 ) {
        parent->_left = newNode;
    } else {
        parent->_right = newNode;
    }

    newNode->_parent = parent;
    ++_size;
    return newNode;
}

关键修复点说明：

1. 修正循环分支逻辑：把current = current->_right放到else分支中，确保comp <0时走左子树，comp>0时走右子树，循环逻辑恢复正常。
2. 避免内存泄漏：当发现键已存在时，主动delete新创建的newNode，否则会造成内存泄漏。
3. 循环结束后使用parent而非current：循环结束时parent是最后一个遍历到的非空节点，用它的键来比较，彻底避免访问空指针。

额外建议 #

你的BST类中clear()函数未实现，析构函数调用clear()会导致未定义行为，建议补充实现clear()函数（可以用递归方式销毁所有节点）。

修复后运行测试用例1，应该可以正常输出预期的中序遍历结果，不会再出现段错误。

备注：内容来源于stack exchange，提问作者Cevapi Man69