Segmentation error, why?

[thestraycat27]

Here's a code I used to describe the class of binary trees with char elements.

struct node
{
  char d;
  node *ls;
  node *rs;
};
/////
class btree
{
    public:
        btree();
        ~btree();
        void destroy_tree();
        btree leftson();
        btree rightson();
        node *root;
        void display();
        
    private:
        bool empty();
        void destroy_tree(node *leaf);

};


btree::~btree()
{
  destroy_tree();
}

void btree::destroy_tree(node *leaf)
{
  if(leaf!=NULL)
  {
    destroy_tree(leaf->ls);
    destroy_tree(leaf->rs);
    delete leaf;
  }
}

void btree::destroy_tree()
{
  destroy_tree(root);
}

After a compilation, it terminates the program informing me of a segmentation fault in destroy_tree(leaf->ls); (bolded). It didn't even use the destructor on actual objects. Can anyone explain to me where this segmentation fault is and how to fix it?

Thanks in advance!

[ne555]

Post your test code.
You'll need to define a copy constructor and an assignment operator for btree

Edit: I suppose that you are initializing `ls' and `rs' to NULL, ¿right?

[thestraycat27]

The constructor is

btree::btree()
{
  root=NULL;
}

Since root is the only variable in btree, it does define a tree. This empty tree has no nodes, so ls and rs are undefined for it.

[ne555]

I was talking about node::{ls,rs}

[thestraycat27]

So what's wrong with them? The problem is not with an infinite object, it doesn't want to recognize this method of destroying a binary tree.

Yes, whenever an element has no children, its ls and rs are defined as NULL.

[Disch]

I'm pretty sure ne555's first reply may have nailed the issue:

You'll need to define a copy constructor and an assignment operator for btree

If you are using the leftson/rightson functions, you are destroying your tree and that will cause your segmentation fault.

What's happening is you are shallow-copying the btree object, which means all its pointers are being copied (but not the data they point to!). So you'll have multiple pointers pointing to the same data. When one btree is destroyed, it will cleanup/destroy all the data, leaving the remaining btree with a bunch of bad pointers. Then when the other btree is destroyed it will attempt to delete those pointers again resulting in a segmentation fault because it's trying to delete a bad pointer.


Basically... what's happening is this:

// a smaller, simpler example of what's going on in your program:

struct Example
{
  int* ptr;

  ~Example()
  {
    delete ptr;   // delete's ptr whenever the Example object dies
  }
};

int main()
{
  {
    Example a;
    a.ptr = new int;   // assign a.ptr so it's valid

    {  // new scope
      Example b = a;  // b is a copy of a
        //  this is like saying b.ptr = a.ptr ... both pointers point to the same int

    }  // exit scope, b goes out of scope, is destroyed.  Calling b's destructor
    //  at this point, b.ptr is deleted (the allocated int is freed).  However a.ptr still
    //  points to it!  This means a.ptr is now a bad pointer because it points to an
    //  int that no longer exists

  }  // exit scope.  Now 'a' goes out of scope.  Meaning a's destructor is called.
  //  which attempts to delete a.ptr.  However a.ptr is a bad pointer now... which means
  //  this will likely segfault.
}

Your program is doing the same thing... only with nodes instead of ints.


Your solution is to make the btree class properly copyable... or to outright FORBID copying.

Forbidding is much easier:

class btree
{
  // .. normal stuff here


  // add this to forbid copying of the btree class:
private:
  btree(const btree&);  // do not give this function a body
  btree& operator = (const btree&);  // do not give this function a body
};

Adding those two routines as private/bodyless functions will prevent any code that attempts to create a copy of the btree class from compiling. This will likely cause several errors in your code (notably with leftson/rightson which return copies), so you will have to fix all those so they do not create copies anymore.


OR, you can implement a deep copy for the copy constructor / assignment operator. But I'm too lazy to give you an example of how to do that.