c++ - Read access violation in tree structure

Question

I'm working on this assignment and I can't seem to stop this read access violation error. I am new to C++ and I think part of my issue is using pointers when they aren't necessary (I think), but I've also looked at this code and traced through it so many times with the debugger that I think I'm missing something obvious.

The assignment is to implement a Huffman encoder. To do this I have to create a HuffmanTree class and a HuffmanProcedure class, and I am provided with a (mostly) complete Heap class (minheap).

The HuffmanProcedure class has to use the Heap class to store and create HuffmanTrees until I have a Huffman code for every single lowercase letter.

When running the code, I get a read access violation error in the helper I wrote for my Tree destructor, treeRemovalHelper.

The specific error I get (using Visual Studio 2019 targeting C++11): Exception thrown: read access violation. root was 0xDDDDDDDD

Here's where the error is occurring:

// Destructor
HuffmanTree::~HuffmanTree() {
  if (rootPtr != nullptr) {
    rootPtr = treeRemovalHelper(rootPtr);
  } else {
    delete rootPtr;
  }
}

// Helper
HuffmanTree::Node* HuffmanTree::treeRemovalHelper(Node* root)
{
  if (root == nullptr) {
    return nullptr;
  }
  else {
      treeRemovalHelper(root->rightChild); // THIS IS WHERE I GET THE ERROR
      treeRemovalHelper(root->leftChild);
      delete root;
  }

  return nullptr;
}

Can you help point me in the right direction here?

I am happy to provide my full code, just in case it helps. I want to note that all of the code is mine, with the exception of some of the methods in the Heap class (which the instructor provided, and I have noted in the code).

Here are the three constructors for the HuffmanTree class:

HuffmanTree::HuffmanTree() : rootPtr(nullptr)  {}

HuffmanTree::HuffmanTree(const char letter, const int weight) {
  rootPtr = new Node{
    letter,
    weight,
    nullptr,
    nullptr
  };
}

HuffmanTree::HuffmanTree(HuffmanTree* smallestTree, HuffmanTree* secondSmallestTree)
{

  int mergedWeight = smallestTree->rootPtr->weight + secondSmallestTree->rootPtr->weight;

  char tempChar;

  if (smallestTree->rootPtr->letter < secondSmallestTree->rootPtr->letter) {
    tempChar = smallestTree->rootPtr->letter;
  } else {
    tempChar = secondSmallestTree->rootPtr->letter;
  }

  rootPtr = new Node{
    tempChar,
    mergedWeight,
    smallestTree->rootPtr,
    secondSmallestTree->rootPtr
  };
}

标签： c++pointersheap-memory

Answer 1

I found your problem: After you delete the root, remember to set it to nullptr.

// Helper
HuffmanTree::Node* HuffmanTree::treeRemovalHelper(Node* root)
{
  if (root == nullptr) {
    return nullptr;
  }
  else {
      treeRemovalHelper(root->rightChild); // THIS IS WHERE I GET THE ERROR
      treeRemovalHelper(root->leftChild);
      delete root;
      root = nullptr; -->> FIX
  }

  return nullptr;
}