CODEWITHSUNDEEP
c++pointerserror-handlingtree
MrDinkleburg
MrDinkleburg

Reputation: 109

C++ Binary Tree Implementation - Deleting Pointer Causes

I am working on a pretty basic binary tree implementation in C++, but I am currently having a problem that deleting a pointer to the root node crashes the program. In Dev-C++ debug mode the error returned is: "Program received signal SIGTRAP, Trace/breakpoint trap", but when I check with "info breakpoints", it says there are no breakpoints or watchpoints. I'm pretty confused about this and have been spending a lot of time checking if I have used and declared all the pointers correctly, any help would greatly be appreciated!

#include <iostream>
#include <vector>

using namespace std;


class Node {
  public: 
    int key;
    Node * left_child = NULL;
    Node * right_child = NULL;  
};


class Tree {

  public:

      int num_nodes;
      vector<Node> nodes;

   int read() {

    cin >> num_nodes;   
    nodes.resize(num_nodes); 
    int input_key, input_left, input_right, root_node = 0;

    for (int i = 0; i < num_nodes; i++) {

      cin >> input_key >> input_left >> input_right;
      if(input_key >= nodes.size()) {
        nodes.resize(input_key+1);
      }
      if(i==0) {
        root_node = input_key;
      }


      nodes[input_key].key = input_key;
      if(input_left >= 0) {
        nodes[input_key].left_child = &nodes[input_left];   
      } 

      if(input_right >= 0) {
        nodes[input_key].right_child = &nodes[input_right]; 
      }
    }
    return root_node;
  }
};


int main() {

    Tree t;
    int root_index = 0;
    root_index = t.read();

    Node * root_ptr = new Node;
    root_ptr = &(t.nodes[root_index]);
    delete root_ptr; //when I take this line out, it works

}

Sample Input (no output expected):

3
4 2 5
2 -1 -1
2 -1 -1

Upvotes: 0

Views: 134

Answers (1)

Sean F
Sean F

Reputation: 4605

Firstly, this line is useless: 

Node * root_ptr = new Node;

You immediately reassign root_ptr to something else. So the line does nothing but allocate memory. You then assign root_ptr as follows:

 &(t.nodes[root_index]);

The variable t you declared on the stack. You end up getting a pointer to a vector element, an element you never allocated yourself. If you did not allocate it yourself, you cannot delete it. Any allocation by the vector will be handled by the vector, and the vector itself is a stack-allocated, so you cannot delete it.

That is why the delete line crashes.

Additionally, you say it is a simple binary tree implementation, but it is not. You have a vector in there, and you have a strange way of assigning the tree elements, so you've created some kind of hybrid data structure.

Upvotes: 1

Related Questions