CODEWITHSUNDEEP
c++recursiontree
user3870016
user3870016

Reputation: 1

Recursive function to destroy general tree c++

This is what I have so far for my DestroyTree function that gets call in the SkillTree desctructor:

void SkillTree::DestroyTree(Node*& root)
{

  if(root)
  {
      for(int i = 0; i < child_max && root && root->child[i]; ++i)
      {
          if(root)
          {
              DestroyTree(root->child[i]);
              delete root;
              root = NULL;
          }
      }

  }

}

I am slightly embarrassed for all the checks on root, but I was just trying to get it to work.

Also here is part my class definition if it is helpfull...

class SkillTree
{
  public:
    SkillTree(void);
    ~SkillTree(void);   

  protected:
    struct Node
    {
       Node() : max(DEFAULT_CHILD_MAX), child(new Node*[DEFAULT_CHILD_MAX])
        {
            for(int i = 0; i < max; ++i)
                child[i] = NULL;
        }

       ~Node()
       {
           for(int i = 0; i < max; ++i)
               delete child[i];

           child = NULL;
       }

       int max;
       Skill data;
       Node** child;    //a dynamic array of child pointers
    };

    void DestroyTree(Node*& root);

    int child_max;
    const static int DEFAULT_CHILD_MAX = 3;
    char* title;
    Node* root;
};

I don'e think the left most node is getting deleted along with other children besides the first of three. I know I have a memory leak, so I am hoping that if I get this fixed then my memory leak problem will be fixed as well.

Upvotes: 0

Views: 1133

Answers (3)

Don Reba
Don Reba

Reputation: 14031

The DestroyTree function should look like this:

void SkillTree::DestroyTree()
{
    if (root)
    {
        delete root;
        root = NULL;
    }
}

and the Node destructor like this:

Node::~Node()
{
    for (size_t i = 0; i < max; ++i)
    {
        if (child[i])
            delete child[i];
    }
    delete [] child;
}

It's a bit long to list the reason for every change. If anything is unclear, feel free to ask!

Upvotes: 1

SNce
SNce

Reputation: 2553

You should be using delete[] child; in Node's desctructor rather than deleting individual children. This is because child was constructed with new[]. Not doing so results in undefined behaviour.

Upvotes: 0

Some programmer dude
Some programmer dude

Reputation: 409166

You have a problem in that no matter how many children the root node have, it will only iterate (and recurse) once.

The reason? You delete and reset the root pointer inside the loop, and have the root pointer being a condition for the loop.

You should only have the initial check for root being non-null, and then delete/reset it after the loop.

Upvotes: 0

Related Questions