C++二叉搜索树指针操作引发段错误，寻求修复方案

问题描述 #

我有C语言开发经验，目前尝试用C++实现基础二叉搜索树（BST），以下是我的代码实现，但运行时触发Segmentation Fault，排查发现访问bst.head_和调用搜索函数时出错：

BinaryTreeNode类定义 #

#include <iostream>
#include <string>

class BinaryTreeNode {
public:
    int data_;
    BinaryTreeNode *left_;
    BinaryTreeNode *right_;

    BinaryTreeNode(int d, BinaryTreeNode *l, BinaryTreeNode *r) : data_{ d }, left_{ l }, right_{ r } {}
    BinaryTreeNode(int d, BinaryTreeNode *l) : data_{ d }, left_{ l }, right_{ nullptr } {}
    BinaryTreeNode(int d) : data_{ d }, left_{ nullptr }, right_{ nullptr } {}
};

BST类定义及实现 #

class BST {
public:
    BinaryTreeNode *head_;
    void BST_Insert(BinaryTreeNode *&head, int data);
    BinaryTreeNode *BST_Search(BinaryTreeNode *root, int key);
};

void BST::BST_Insert(BinaryTreeNode *&head, int data) {
    if (head == nullptr) {
        head = new BinaryTreeNode(data);
        return;
    }
    if (data > head->data_)
        BST_Insert(head->right_, data);
    else
        BST_Insert(head->left_, data);
    return;
}

BinaryTreeNode* BST::BST_Search(BinaryTreeNode *root, int key) {
    if (root == nullptr || root->data_ == key)
        return root;
    if (key > root->data_)
        return BST_Search(root->right_, key);
    else
        return BST_Search(root->left_, key);
}

main函数 #

int main() {
    BST bst;
    bst.BST_Insert(bst.head_, 3);
    bst.BST_Insert(bst.head_, 5);
    bst.BST_Insert(bst.head_, 1);
    bst.BST_Insert(bst.head_, 2);
    BinaryTreeNode *oldptr = bst.head_;
    BinaryTreeNode *found_1 = bst.BST_Search(bst.head_, 1);
    return 0;
}

问题原因 #

核心问题是BST类的head_指针未初始化：当创建BST bst;局部对象时，head_作为未初始化的指针，其值是随机的野指针。第一次调用BST_Insert时，函数判断head == nullptr会失败（野指针值不等于nullptr），进而尝试访问head->data_，直接触发非法内存访问，引发段错误。后续的oldptr = bst.head_和搜索函数调用只是表象，实际错误在第一次Insert时就已发生。

修复方案 #

• 给BST类添加构造函数，初始化head_：给BST类添加无参构造函数，将head_初始化为nullptr，确保树的初始状态是空树：

  class BST {
  public:
      BinaryTreeNode *head_;
      // 添加构造函数
      BST() : head_(nullptr) {}
      void BST_Insert(BinaryTreeNode *&head, int data);
      BinaryTreeNode *BST_Search(BinaryTreeNode *root, int key);
  };
  

• 优化Insert函数（可选，更符合面向对象设计）：将Insert函数改为直接操作类成员head_，无需外部传递指针，避免传参错误：

  // 修改BST类的Insert声明
  void BST_Insert(int data);
  
  // 实现修改为
  void BST::BST_Insert(int data) {
      // 内部递归辅助函数
      auto insertHelper = [this](auto&& self, BinaryTreeNode*& node, int val) -> void {
          if (node == nullptr) {
              node = new BinaryTreeNode(val);
              return;
          }
          if (val > node->data_) {
              self(self, node->right_, val);
          } else {
              self(self, node->left_, val);
          }
      };
      insertHelper(insertHelper, head_, data);
  }
  
  // main函数调用改为
  bst.BST_Insert(3);
  bst.BST_Insert(5);
  bst.BST_Insert(1);
  bst.BST_Insert(2);
  

• 添加析构函数避免内存泄漏（建议）：为BST类添加析构函数，递归释放所有节点内存：

  class BST {
  public:
      BinaryTreeNode *head_;
      BST() : head_(nullptr) {}
      // 析构函数
      ~BST() {
          auto deleteHelper = [this](auto&& self, BinaryTreeNode* node) -> void {
              if (node == nullptr) return;
              self(self, node->left_);
              self(self, node->right_);
              delete node;
          };
          deleteHelper(deleteHelper, head_);
          head_ = nullptr;
      }
      void BST_Insert(int data);
      BinaryTreeNode *BST_Search(BinaryTreeNode *root, int key);
  };
  

修复后完整代码示例 #

#include <iostream>
#include <string>

class BinaryTreeNode {
public:
    int data_;
    BinaryTreeNode *left_;
    BinaryTreeNode *right_;

    BinaryTreeNode(int d, BinaryTreeNode *l, BinaryTreeNode *r) : data_{ d }, left_{ l }, right_{ r } {}
    BinaryTreeNode(int d, BinaryTreeNode *l) : data_{ d }, left_{ l }, right_{ nullptr } {}
    BinaryTreeNode(int d) : data_{ d }, left_{ nullptr }, right_{ nullptr } {}
};

class BST {
public:
    BinaryTreeNode *head_;
    BST() : head_(nullptr) {}
    
    ~BST() {
        auto deleteHelper = [this](auto&& self, BinaryTreeNode* node) -> void {
            if (node == nullptr) return;
            self(self, node->left_);
            self(self, node->right_);
            delete node;
        };
        deleteHelper(deleteHelper, head_);
        head_ = nullptr;
    }

    void BST_Insert(int data) {
        auto insertHelper = [this](auto&& self, BinaryTreeNode*& node, int val) -> void {
            if (node == nullptr) {
                node = new BinaryTreeNode(val);
                return;
            }
            if (val > node->data_) {
                self(self, node->right_, val);
            } else {
                self(self, node->left_, val);
            }
        };
        insertHelper(insertHelper, head_, data);
    }

    BinaryTreeNode *BST_Search(BinaryTreeNode *root, int key) {
        if (root == nullptr || root->data_ == key)
            return root;
        if (key > root->data_)
            return BST_Search(root->right_, key);
        else
            return BST_Search(root->left_, key);
    }
};

int main() {
    BST bst;
    bst.BST_Insert(3);
    bst.BST_Insert(5);
    bst.BST_Insert(1);
    bst.BST_Insert(2);
    
    BinaryTreeNode *oldptr = bst.head_;
    if (oldptr) {
        std::cout << "Root node data: " << oldptr->data_ << std::endl;
    }
    
    BinaryTreeNode *found_1 = bst.BST_Search(bst.head_, 1);
    if (found_1) {
        std::cout << "Found node data: " << found_1->data_ << std::endl;
    }
    
    return 0;
}

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