c++ - 二叉搜索树分割错误

Question

该程序旨在从输入文件中获取字符串，按字母顺序对它们进行排序以生成签名，然后将签名作为 key 插入 BST 节点。然后将创建签名的单词存储在链接到 key 的字符串 vector 中。之后签名相同的任何单词都会被推回同一个 vector ，依此类推。我遇到了段错误，将在下面显示确切位置。

BST.h

#ifndef BST_H
#define BST_H
#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Node;

class BST {
  private:
   class Node {
     public:
      string key;
      Node *left, *right;
      vector<string> data;
     Node(string k, Node *l, Node *r, vector<string> d) : key{k}, left{l}, right{r}, data{d} {};
   };
   Node *root;
   void traverse(void (*f)(const string& key, vector<string>& value), Node* root);
  public:
   BST();
   ~BST();
   Node* find(Node* root, const string& key);
   void insert(Node *&root, const string& key);
   vector<string>& operator[](const string& key);
   void traverse(void (*f)(const string& key, vector<string>& value));
};

#endif

BST.cc

#include "BST.h"

BST::BST()
{
   root = nullptr;
}

BST::~BST()
{
   delete root;
}

BST::Node* BST::find(Node* root, const string& key)
{
   if(!root) return nullptr;
   if(root->key == key) return root;
   else if(root->key > key) return BST::find(root->left, key);
   else return BST::find(root->right, key);
}

void BST::insert(Node *&root,const string& key)
{
   if(!root)
   {
      vector<string> data;
      root=new Node(key, nullptr, nullptr, data);
   }
   else if(root->key >= key) BST::insert(root->left, key);
   else BST::insert(root->right, key);
}

vector<string>& BST::operator[](const string& key)
{
   Node* temp=BST::find(root, key);
   if(temp!=nullptr)
   {
      return temp->data;
   }
   else
   {
      BST::insert(root, key);
      return (BST::find(root, key))->data;
   }
}

以下2个成员函数是导致段错误的原因

void BST::traverse(void (*f)(const string& key, vector<string>& value))
{
   Node* tRoot=root;
   if(tRoot)
      traverse(*f, tRoot);
}


void BST::traverse(void (*f)(const string& key, vector<string>& value), Node* root)
{
   string& key=root->key;
   vector<string> value(root->data);
   if(root)
   {
      traverse(*f, root->left);
      f(key, value);
      traverse(*f, root->right);
   }
}

主程序

#include "BST.h"
#include <algorithm>
#include <fstream>

using namespace std;

// Computes the signature of the string, which is the original string                                                                                                                                                                                                         
// arranged in alphabetical order.                                                                                                                                                                                                                                            
//                                                                                                                                                                                                                                                                            
// Assumes that the string w consists of only upper case letters.                                                                                                                                                                                                             
string signature(const string& w);

// prints all the anagrams in the BST                                                                                                                                                                                                                                         
void printAnagrams(const string& key, vector<string>& value);

int main(void)
{
  string w, s;
  BST signatureList;
  vector<string> temp;
  ifstream myfile;
  myfile.open("words.txt");

  //read all words                                                                                                                                                                                                                                                            
  while(getline(myfile, w)) {
     // compute signature and store it into the list                                                                                                                                                                                                                          
     s = signature(w);
     temp = signatureList[s];
     temp.push_back(w);
  }

  myfile.close();

  // print the results
  //this call specifically gives the seg fault                                                                                                                                                                                                                                                 
   signatureList.traverse(*printAnagrams);

  return 0;
}

// Computes the signature of the string, which is the original string                                                                                                                                                                                                         
// arranged in alphabetical order.                                                                                                                                                                                                                                            
//                                                                                                                                                                                                                                                                            
// Assumes that the string w consists of only upper case letters.                                                                                                                                                                                                             
string signature(const string& w)
{
  string s = w;
  sort(s.begin(), s.end());
  return s;
}

// prints all the anagrams in the BST                                                                                                                                                                                                                                        
void printAnagrams(const string& key, vector<string>& value)
{
   cout << key << endl;
   for(string s : value)
       cout << s << ' ';
   cout << endl;
}

感谢您的帮助，无法让 valgrind 处理这个问题。据我所知，没有与我的问题明确相关的问题，如果不是这样，我深表歉意。

Answer 1

您在 traverse 中检查 NULL 为时已晚。 将变量初始化移到条件语句中，或完全消除它们:

void BST::traverse(void (*f)(const string&, vector<string>&), Node* root)
{
   if(root)
   {
      traverse(f, root->left);
      f(root->key, root->data);
      traverse(f, root->right);
   }
}