二叉搜索树析构函数：free() 无效指针

Question

对于我当前的编程任务，我必须构建一个二叉搜索树并使用它按字母顺序从文件中插入单词，以制作索引列表。程序完整并正确输出；该程序的主要部分运行良好。但是当程序完成并调用析构函数时，它会崩溃并显示 error in ./concordancebst : free(): invalid pointer。我不知道问题出在哪里，我的析构函数看起来可以正常工作，在线查看代码似乎也应该可以正常工作。我可能可以通过使用 std::unique_ptr 来解决这个问题，但从程序的范围来看它似乎有点矫枉过正（从我们没有涵盖智能指针的意义上来说也是矫枉过正，我们在class 涉及动态内存已通过手动处理allocating/deallocating)。

BST.h

#ifndef BST_H
#define BST_H
#include <string>

class BST {
public:
   BST() { root = nullptr; }
   ~BST();

   void insert(const std::string word);
   int getCount(const std::string word);
   int length();

   friend std::ostream& operator << (std::ostream &out_s, BST b);
private:
   struct Node {
      std::string word;
      int count;
      Node *left;
      Node *right;
      Node() { word = ""; count = 0; left = nullptr; right = nullptr;}
      ~Node();
   };
   Node *root;

   void RInsert(Node* &t, std::string word);
   int countNodes(Node *p);
   void print(Node *p, std::ostream &out_s);
};
#endif

BST.cpp

#include "BST.h"
#include <string>
#include <iostream>
#include <iomanip>

BST::Node::~Node() {
   delete left;
   delete right;
}

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

int BST::countNodes(Node *p) {
   if(p == nullptr)
      return 0;
   else
      return countNodes(p->left) + countNodes(p->right) + 1;
}

int BST::getCount(const std::string word) {
   Node *p = root;
   while(true) {
      if(p == nullptr)
         return 0;
      else if(word.compare(p->word) < 0)
         p = p->left;
      else if(word.compare(p->word) == 0)
         return p->count;
      else
         p = p->right;
   }
}

int BST::length() {
   return countNodes(root);
}

void BST::RInsert(Node* &t, std::string word) {
   if(t == nullptr) {
      t = new Node;
      t->word = word;
      t->left = nullptr;
      t->right = nullptr;
      t->count++;
   }
   else if(word.compare(t->word) == 0)
      t->count++;
   else if(word.compare(t->word) < 0)
      RInsert(t->left, word);
   else //word.compare(t->word > 0)
      RInsert(t->right, word);
}

void BST::insert(const std::string word) {
   RInsert(root, word);
}

void BST::print(Node *p, std::ostream &out_s) {
   if(p != nullptr) {
      print(p->left, out_s);
      out_s << std::setw(13) << p->word << std::setw(10) << p->count <<  std::endl;
      print(p->right, out_s);
   }
}

std::ostream &operator << (std::ostream &out_s, BST b) {
   out_s << std::setw(13) << "Word" << std::setw(10) << "Count" << std::endl;
   out_s << "---------------------------------------------" << std::endl;
   b.print(b.root, out_s);
   out_s << "---------------------------------------------" << std::endl;
   out_s << "The file contains " << b.length() << " distinct words." << std::endl;

   return out_s;
}

Answer 1

std::ostream &operator << (std::ostream &out_s, BST b)
                                       Pass by value^. b is copied.

由于BST没有拷贝构造函数，调用默认的拷贝构造函数，不进行深拷贝。 b 包含源 BST 指针的副本，当 b 在 return 上从函数中销毁时，它会占用源的所有 Node陪它到坟墓。

修复是双重的：

最直接，按引用传递。

std::ostream &operator << (std::ostream &out_s, BST & b)

间接地，此代码违反了 Rule of Three。 BST 和 BST::Node 需要安全使用复制构造函数和赋值运算符。

编辑

一个最小的测试用例应该是这样的：

#include <iostream>
#include "BST.h"

int main()
{
    BST t;

    t.insert("A");

    std::cout << t << std::endl;
    return 0;
}

二叉搜索树析构函数：free() 无效指针

Binary search tree destructor: free() invalid pointer

c++

c++11

binary-search-tree

destructor

编辑