C++, How to delete a tree based data structure

Mallo · 2007-09-04 08:04:31

Hi everybody. I made a software based on quadtree data structure for robotics purpose. Some times ago I noted that when I try to delete the pointer to the quadtree appeared an heap error, so probably I'm a worse programmer than I've thought.

My question is:

Let me define a nutty tree data structure (sorry about syntax errors)

class Tree {

public:
Tree(int value) {data=value;}
~Tree();
amethod();
addchildrennumber(int);

private:
int data;
Tree *children[4];
}

How to define ~Tree()?
In the first time I wrote a simple:
~Tree() { delete children[];}
I think the root destruction could provoke a sort of chain effect. I know that it's probably wrong. What is the correct procedure? I know that usually you should destroy the lower node first but I don't realize how.

Thanks :\

Husio · 2007-09-04 09:31:24

No idea if it will work, but :

Tree::~Tree() {
for(int n=0; n<4;n++) {
if (children[n] != NULL) {
children[n].~Tree();
}
}
delete [] children[];
}

Last edited by Husio (2007-09-04 09:32:56)

STiAT · 2007-09-04 10:27:56

Hmh, should work.

I'd suggest to call delete on the children[n] pointer instead of just calling the destructor method.
By calling delete on a sub-tree item, will also invoke the destructor correctly, destroy the element and children[n] would be set NULL.

I'm not sure if your method isn't over-sensible. I'm not sure right now if delete[] wouldn't call delete on the sub-objects as well, or at least trigger the destructor, which would make the loop unnecessary.

I'd need to test this. Never held any pointers to sub elements in arrays, rather in lists, for completely dynamic structures.

@Mallo: By destroying the root node and calling the delete function on the childrens will internally destroy the subnodes first, since it's recursively called, and on the way backwards it will destroy the base nodes. It's no problem within that. The destructor is always called, before any other action is driven.

Yours,
STi

Allan · 2007-09-04 10:58:19

I'm not sure what exactly you are trying to clean-up in the destructor. From what I can make out here:

Tree* children[4];

This just creates an array of tree pointers. The is no use of new so no need to use delete. I assume you are not using new in the constructor because I really don't think you need to.

If you want to delete the child nodes when the destructor is called then you need a

for(int i = 0; i < 4; ++i)
delete children[i];

but you only really need this if you assign the memory somewhere in you class.

Also, I'm sure that calling delete on an array of pointers will not free the memory of the elements in the array. It just delete the pointer in the array, not the memory used by that pointer.

STiAT · 2007-09-04 11:22:45

Would also have been my first thought.

Thanks for clearing up the array destruction

Cerebral · 2007-09-04 13:33:01

Husio wrote:

No idea if it will work, but :
Tree::~Tree() {
for(int n=0; n<4;n++) {
if (children[n] != NULL) {
children[n].~Tree();
}
}
delete [] children[];
}

^^ This suggestion could corrupt the heap in so many ways it hurts. Don't do it! ^^

All you need is:

Tree::~Tree() {
 for(int n=0; n<4; n++) {
    delete children[n];
  }
}

as was suggested earlier by Allan.

Note! This is the way to do it ONLY if addchildrennumber(int); uses new Tree() to allocate your children (which is what I assume it does).

A good implementation for addChildrenNumber(int) and the destructor would be:

Tree::Tree() {
  for(int n=0; n<4; n++) {
    children[n] = NULL;  /* Need to initialize to NULL to prevent uninitialized pointer errors. */
  }
}

void Tree::removeChildren() {
 for(int n=0; n<4; n++) {
    delete children[n];
    children[n] = NULL; /* Reset to NULL, we've deleted, so we don't want to use the pointer again. */
  }
}

void Tree::addChildrenNumber(int num) {
  removeChildren();
  for(int n=0; n<num; n++) {
    children[n] = new Tree();
  }
}

Tree::~Tree() {
  removeChildren();
}

Then you have code reuse. :)

-edit- Also, you might want to define a static const int MAX_CHILDREN = 4; inside your class somewhere, then use MAX_CHILDREN instead of just the number 4 everywhere - that will add clarity to your code. -/edit-

Last edited by Cerebral (2007-09-04 13:37:49)

Mallo · 2007-09-04 19:04:31

Thanks, I'll try your advice .

Husio · 2007-09-05 12:28:32

shouldn't be Tree::~Tree() virtual? It might be stupid question, but I'm just learning C++.

Allan · 2007-09-05 12:46:14

No, it does not need to be virtual. You only need to consider virtual destructor when your class is a base class - i.e. other classes will be derived from it. This ensures that both the derived and base destructors get called when the derived object is deleted. For example:

#include <iostream>
using namespace std;

class Base
{
   public:
      Base(){ cout<<"Constructor: Base"<<endl;}
      ~Base(){ cout<<"Destructor : Base"<<endl;}
};
class Derived: public Base
{
   public:
      Derived(){ cout<<"Constructor: Derived"<<endl;}
      ~Derived(){ cout<<"Destructor : Derived"<<endl;}
};
int main()
{
   Base *Var = new Derived();
   delete Var;
}

When you compile that, you should see that only the base destructor get called. That is bad if the derived class assigned any memory...

Arch Linux

#1 2007-09-04 08:04:31

C++, How to delete a tree based data structure

#2 2007-09-04 09:31:24

Re: C++, How to delete a tree based data structure

#3 2007-09-04 10:27:56

Re: C++, How to delete a tree based data structure

#4 2007-09-04 10:58:19

Re: C++, How to delete a tree based data structure

#5 2007-09-04 11:22:45

Re: C++, How to delete a tree based data structure

#6 2007-09-04 13:33:01

Re: C++, How to delete a tree based data structure

#7 2007-09-04 19:04:31

Re: C++, How to delete a tree based data structure

#8 2007-09-05 12:28:32

Re: C++, How to delete a tree based data structure

#9 2007-09-05 12:46:14

Re: C++, How to delete a tree based data structure

Board footer