Destructor for N-ary tree

[DemonGal711]

Ok, apparently my destructor isn't done yet and I'm not sure how to handle this. I have an n-ary tree that contains nodes that are built of data and a vector of pointers. Each pointer was initialized with new, so I need to delete them obviously. One friend said I was fine and another said no. So, can someone explain what I'm missing?

My destructor calls this function which should delete everything in that node.

void del(node* ptr)
	  { for (int y = 0; y < ptr->num; y++)
			{ del(ptr->children[y]); }
		delete ptr;
		ptr = NULL;
	  }

The for call just tells it only to go down the unique variables it points to, cause each node points to other nodes that contain words one letter off and I was trying to prevent losing a branch before the nodes under it were deleted. It should stop when it finds no unique values under it, thus leaving just a vector of pointers to other nodes one letter off, which are the pointers I need to delete.

Anyway, I would assume I need to add another for that deletes the pointers in the vector, but what should that look like? This is what I thought it would need but my compiler didn't like it Any help would be appreciated.

void del(node* ptr)
	  { for (int y = 0; y < ptr->num; y++)
			{ del(ptr->children[y]); }
		for (int x = 0; x < ptr->children.size(); x++)
			{ delete ptr->children[x];
			  ptr->children[x] = NULL; }
		delete ptr;
		ptr = NULL;
	  }

[ArkM]

1. Use code tag with the language specifier!!!
[code=c++] source

[/code]
2. Where is your class definition? Where is your problem destructor definition?
3. >but my compiler didn't like it
Yes, I don't like it too. Probably it's a wrong code.
Where are compiler diagnostic messages? See also #2...
4. It seems you didn't understand my post in the recent thread on this topic. As usually, the only job for the node destructor is to delete pointers in the branches vector. It starts a recursive destruction of all this branch. The branch vector member has its own destructor. It seems you are still mixing a class destructor role and an object memory deallocation via the delete operator.
5. If you call del(this) in a node destructor then you get recursive destructor entry on delete ptr .
6. You are trying to delete all nodes twice in the 2nd snippet...
...and so on...
Please, present your class definition if you want more helps.

[DemonGal711]

1. Well, considering this is the C++ forum, I didn't think the language specifiers were needed, but fine.
2. My ENTIRE class is listed at the bottom.
3. Well obviously it's wrong code. I was asking for help with the right code. Actually, now the compiler isn't having an issue, the program just crashes.
4. I tried to take what you suggested and implement it, obviously I was wrong, hence why I'm here again. Considering that every node and pointer in the node was created with 'new' I figured I needed to 'delete' every pointer and node as well, hence when del(root); is call, it tries to do that, starting with the lowest nodes on the tree and working up.
5. del() is only called by the destructor.
6. That's what I needed to know. I didn't know why it was dying and that helps clear it up. So, how do I avoid deleting a node when all I want is the pointers in the vector to die?

struct com          
    {  string data;   
       int num;       
    };

class MTree
{ private:
  struct node                      
      { node* parent;              // Holds the original node that pointed to this one
        vector <node*> children;   // Holds points to all the nodes that contain data one letter off
        string data;               // Holds the word for this node.
        int num;                   // Holds a number that indicates the unique number of nodes 
                                   //       it pointed to before connecting to words one letter away
        int level;                 // Indicated what level of the tree it's at, only used in print
      };
      
  struct trail
      { vector <string> vec;       
        int num;                   
      };

  node* root;                      

  public:
MTree() { root = NULL; }
  
  ~MTree () { del(root); }
    
  bool isEmpty() const { return root==NULL; }

  void del(node* ptr)
      { for (int y = 0; y < ptr->num; y++)
	        { del(ptr->children[y]); }
        delete ptr;
        ptr = NULL;
      }

  friend int compare (string on, string start)
      { int x, d = 0;                         // x is used in for loop, d is the difference between the words
        for (x = 0; x < start.length(); x++)
		     if (start[x] != on[x]) d++;
	    return d;
      }

  friend bool isInVec (vector <string> vec, string info)
      {  vector<string>::iterator it;       // Used to travel through the vector
         for (it = vec.begin(); it != vec.end(); it++)
             { if (info == *it) return true; }
         return false;
      }

  void buildTree (vector <string> vec, string one, string two)
      { insert(one);
        for(int x = 0; x < vec.size(); x++)
           if (!(compare(vec[x], one) == 0 || compare(vec[x], two) == 0))  insert(vec[x]);
        insert(two);
        connect(root);
      }

  void insert(string d)
      { node* t = new node;
        t->data = d;
        t->num = 0;
        t->level = 0;
        
        if(isEmpty()) root = t;
        else
           { node* curr = root;
             t->parent = inHelp (curr, d);
             if (t->parent != NULL)
                { t->level = t->parent->level+1;
                  t->parent->children.push_back(t);
                  t->parent->num++; }
             else delete t;
      }    }
      
  node* inHelp (node* ptr, string on)
  	  { if (compare(ptr->data, on) == 1) return ptr;
	    else 
		   { int x = 0;        // Keeps track of which child they've gone too
		     node* now = NULL;
		     while (now == NULL && x < ptr->children.size())
			   	   { now = inHelp (ptr->children[x++], on); } 
		     return now;
      }    }

  void connect (node* ptr) 
      { if (ptr != NULL)
           { if (ptr != root) conHelp(ptr, root); // The root should be good already
		     int x = 0;                           // Helps prevent traveling the tree multiple times
             while (x < ptr->num)                 // ptr->num is the unique # of nodes this node points to
		           { connect(ptr->children[x++]); }
      }    }

  void conHelp (node* ptr, node* other)
	  { int comp = compare(ptr->data, other->data);
	    if (comp != 0)
	       { if (comp == 1)
	            { isInTree(ptr, other);
	              isInTree(other, ptr); }
             int x = 0;                            // Helps prevent traveling the tree multiple times
		     while (x < other->num)
                   { conHelp(ptr, other->children[x++]);}
     }     }
	 
  void isInTree (node* from, node* to)
      { bool there = false;                             // Indicated where the node is already in tree to prevent double pointers
        for (int x = 0; x < from->children.size(); x++)
            if (from->children[x] == to) there = true;
        if (there == false && from->data != root->data && to->data != root->data)
           { node *t = new node;
             t = to;
             from->children.push_back(t); }
      }

  void wordLadder(string word1, string word2)
      { if (find(word2, root) == NULL) cout << "No solution.\n";
        else
           { trail test;             // The correct path is stored here.
             vector <string> now;
             test.num = 0;
             test = path(root, word2, 0, test, now);
             for (int x = test.vec.size()-1; x >= 0; x--)
                 cout << test.vec[x] << endl;
      }    }

  node* find (string w, node* ptr)
     { if (ptr->data == w) return ptr;
       else 
          { int x = 0;                  // Helps prevent traveling the tree multiple times
            node* now = NULL;
		    while (now == NULL && x < ptr->num)
			      { now = find(w, ptr->children[x++]); } 
		    return now;
     }    }

  trail path (node* ptr, string w2, int count, trail test, vector <string> prev)
     { trail now;                 // Indicated what is the shortest path after going through that part of the tree.
       if (ptr->data == w2) 
          { now.num = count;
            now.vec.push_back(ptr->data);
            return now; }
       else 
          { if (++count < test.num || test.num == 0)
               { for (int x = 0; x < ptr->children.size(); x++)
                     { if (isInVec(prev, ptr->data) == false || prev[prev.size()-1] == ptr->data)
                          { if (isInVec(prev, ptr->data) == false) prev.push_back(ptr->data); 
                            now = path(ptr->children[x], w2, count, test, prev);
                            now.vec.push_back(ptr->data);
                            if (now.num < test.num || test.num == 0)
                               { test.num = now.num;
                                 test.vec = now.vec; 
		       }     }    }    }
            return test;    
     }    }
};

[r.stiltskin]

Well, maybe I'm too tired to think this all the way through, but it seems like the children can have children which have children ... so your del would have to recurse all the way down through the tree.

An easier solution I think is to put a destructor in the node structure itself. (You know, I assume, that a struct is essentially the same as a class except that it's members are public by default.) So just put a ~node() with code that runs through its own vector of children deleting each one. As each child is deleted it will call its own destructor, and so on...

[DemonGal711]

The whole thing I was trying to do was create a tree and then add pointers to nodes so that they point to other nodes that have a word one letter off.

Example: cat would point to bat and sat, bat would point to cat and sat, etc... The whole that is that in the original tree, cat is the root, and it's two unique children are bat and sat. Both bat and sat have no unique children cause there are only three words and all are in the tree. Then the tree connects all the nodes, thus bat <-> sat giving them each a pointer to the other node

What I need is get rid of that pointer, then delete that node, and then go up, check the other unique children until there are none left, then delete the last node. This is where I'm having issues cause apparently it's deleting the node it points to, not the pointer.

for (int x = 0; x < ptr->children.size(); x++)
			{ delete ptr->children[x];   //deletes the node that this points to, not pointer apparently
			  ptr->children[x] = NULL; }

I'm just hoping there is a way I can amend my del function without redoing the whole code.

[ArkM]

>Well, considering this is the C++ forum, I didn't think the language specifiers were needed, but fine.
Thank you. Pay attention that the forum engine adds line numbers (for references) and makes some code formatting (easy to read) only for proper code tags with the language specifiers...

>Well obviously it's wrong code. I was asking for help with the right code.
That's exactly why the class definition needed ;)

Add node class (struct) constructor and destructor:

struct node                      
{
    node():parent(0),num(0),level(0) {}
    ~node() {
        for (size_t i = 0; i < children.size(); ++i)
            delete children[i];
            // That's all you need to deallocate branches.
            // However (about another destructor actions):
            // I can't understand what's the parent member role.
            // See insert member: why it's not a parent_in_tree?
            // What's inHelp role?
            // In other words: think about parent ptr target
            // when this node dies...
        }
    ...
};

Now you can use a simple and natural delete nodepointer expression.
Remark: better use capitalized names for your classes (Node, for example).

Now MTree destructor and clear (all the tree) member functions (add them):

~MTree() { delete root; }
void clear() { delete root; root = 0; }

Alas, the class MTree design does not provide an user with a correct and convenient erase (the node with all its branches) member function. The MTree::del public member is wrong: you assign NULL value to the function parameter (called by value) so the original pointer to this erased node are intact and now points to nowhere.
Probably, you can use some workaround with

void MTree::del(node& ptr) {
    if (ptr) {
        delete ptr;
        ptr = 0;
    }
}

It seems your class MTree is a hybrid of N-tree abstraction and low-level approach in C (not C++) style (for example, look at public MTree member functions which return pointers to internal data structure node).

Yet another tip: don't include all MTree member function bodies in the class definition. It's so hard to see (and understand) the class interface (member function signatures).

I'm afraid that there are tons of another errors in this code ;(...

[DemonGal711]

I tried what you suggested and it seemed to give me an issue as well, though it's only something small. My program creates cycles essentially. I was trying to prevent hitting one with my code, but when the node tries to die, it sees the children and they try to die. A tree of cat, bat, hat cause it to loop and nothing dies. Any suggestions on how to work around it.

Could I possibly have my connect function use a different kind of pointer or something so that all my node destructor would have to do is delete the unique pointers it allocated. That would prevent cycles. I'm not sure if such a pointer exists that doesn't delete what it's pointing to when it dies, but that would work.

The purpose of parent was so once you find the proper value, you just read up the parents to the root and output the answer. It was giving me wrong answers though so I really didn't use it, but we need it so it's there... Really, it's only purpose is to tell you what was the original node above it.
Like, if I had a tree of cat, bat, cot, bot, cat would originally point to bat and cot, bat would point to bot, and cot would be by itself. After we connect the tree, cot and bot point to each other. Parent for bot just says that the original parent was bat (since cot could also lead down to it), but I never really used that.

I'd believe that I have a lot of issues. I've been driving myself crazy with this code for the past few weeks and when I would hit an error I would spent a few hours working on it and eventually solve it or bug my friends or the people here. I just got the code done earlier today and I still have a lot of work I need to do (outside of the coding) for the other things my teacher wants included in this project.

[DemonGal711]

Here's an odd idea, each node has unique pointers and extra pointers. The unique pointers were used to build the tree initially. The extra pointers were added during the connection process.

Basically, cat, bat, and hat are a tree. Cat is the root and bat and hat are the children of cat with nothing under either of them, thus cat has 2 unique pointers and 0 extra, bat and hat have 0 of unique and 0 extra each. Once run through my connector, bat and hat are connected to each other though, bring both their extra pointers up to 1. The issue would normally come when cat tried to destroy bat, which would try to destroy hat, which would try to destroy bat and etc...

I've heard people say it's not good to delete null pointers (cause it's normally a bug in the code or it can cause problems), but could I do something where I set these extra pointers either to null or some obscure value and have them delete then? That way, it would prevent the cycle cause bat had nothing under it before the connection, so it only has extra pointers. Same thing with hat. Then, cat would be the one deleting bat and hat (because they were originally it's children) and then cat would delete. Would that be a good way to handle this or am I possibly just setting up issues for myself later?

[r.stiltskin]

OK, when I posted last night I didn't realize that that you were talking about a graph with cycles, since you were calling it a tree with a root, parents and children (by definition, trees don't have cycles).

So, here's a solution.
Add another data member to the node: bool destroyed;
Add a default constructor to the node: node() : destroyed(false);
At the beginning of the node destructor, set destroyed = true, so now the node looks like

struct node {
  node* parent;
  vector <node*> children; 
  string data;
  int num;
  int level;
  bool destroyed;  // flag to signal that this node's destructor has been called

  node() : destroyed(false);  // default constructor
  ~node() {
    destroyed = true;
    for( int i = 0; i < children.size(); ++i )
      if( !children[i].destroyed )
        delete( children[i] );
  }
};

[ArkM]

1. Don't worry, you can "delete" null pointer safety: it's a legal noop.
2. It seems you have a mesh, not a tree. Try to distinct node owners (they allocate another nodes) and node referers (they refers to another nodes but did not allocate them). The node destructor deletes the 1st ones but clears (both sides of) links for 2nd kind of nodes.
3. It seems you have all these troubles because didn't design this data structure and its operations carefully. Now you are trying to solve some partial technical problems (with node destructor, for example). Better try to redesign the project (alas). It's impossible to get working solution on this vague basis...