Nandor
#include <vector>
#include <string>
using namespace std;
// data and the arrows
template < class T > struct Tnode_
{
T data;
vector < Tnode_ > ch;
Tnode_ *parentp;
};
// a Tnode is a pointer to a Tnode_ with member functions
template < class T > struct Tnode
{
Tnode_ < T > *p;
// get the data value of the node
T get ()
{
return p->data;
}
// set the data value of the node
void set (T a)
{
p->data = a;
}
// the n-th child node
Tnode child (int n)
{
Tnode node2;
node2.p = &p->ch[n];
return node2;
}
// add a child node
void add_child ()
{
Tnode_ < T > node_;
node_.parentp = p;
p->ch.push_back (node_);
}
// number of children
int Nchildren ()
{
return p->ch.size ();
}
// the first child node
Tnode begin ()
{
Tnode node2;
node2.p = &p->ch.front ();
return node2;
}
// the last child node
Tnode end ()
{
Tnode node2;
node2.p = &p->ch.back ();
return node2;
}
// the parent node
Tnode parent ()
{
Tnode node2;
node2.p = p->parentp;
return node2;
}
T *operator & ()
{
return &p->data;
}
};
// make a tree head and set node to this head
template < class T > void
make_head (Tnode < T > &node)
{
node.p = new Tnode_ < T >;
node.p->parentp = NULL;
}
// print the tree
template < class T > void
travel (Tnode < T > node, int level)
{
for (int i = 0; i < level; i++)
cout << " :";
cout << ". ";
cout << node.get () << "\n";
for (int i = 0; i < node.Nchildren (); i++)
travel (node.child (i), level + 1);
}
main ()
{
Tnode < string > head, node;
make_head (head);
node = head;
node.set ("one");
node.add_child ();
node.add_child ();
node = node.end ();
node.set ("three");
node = node.parent ();
node = node.begin ();
node.set ("two");
node.add_child ();
node.add_child ();
node.add_child ();
node = node.begin ();
node.set ("apple");
node = node.parent ();
node = node.end ();
node.set ("peach");
node = node.parent ();
node = node.child (1);
node.set ("banana");
node.add_child ();
node = node.begin ();
node.set ("cherry");
travel (head, 0);
cout << "\n";
cout << node.get () << "\n";
*&node = "CHERRY";
cout << *&node << "\n";
}
This code is technically illegal. You are storing a vector of Tnode_
inside another Tnode_. This means you are using Tnode_ before it has
been fully defined. You only get away with this because the
implementation of vector you have happens to use pointers.
It is also a dangerous implemenation since later in the code you return
pointers to the child nodes in the vector. But adding a child node could
cause the vector to be reallocated and your pointers would no longer be
valid.
The normal way to do this is to store pointers in the vector, like this
template < class T > struct Tnode_
{
T data;
vector < Tnode_* > ch;
Tnode_ *parentp;
};
You should rewrite your code using the above. It solves both problems I
mentioned above.
The answer to your question is that, no in your old code there is no
memory leak when you pop_back(), but that code is dangerous and illegal.
In my version there would be a memory leak, so you'll have to deal with
it by deleteing before you pop_back().
John
// ntree.hh
#include <vector>
#include <string>
using namespace std;
// data and the arrows
template < class T > struct Tnode_
{
T data;
vector < Tnode_ * >ch;
Tnode_ *parentp;
};
// a Tnode is a pointer to a Tnode_ with member functions
template < class T > struct Tnode
{
Tnode_ < T > *p;
// is this node the head of the tree?
bool ishead ()
{
return NULL == p->parentp;
}
// get the data value of the node
T get ()
{
return p->data;
}
// set the data value of the node
void set (T a)
{
p->data = a;
}
// the n-th child node
Tnode child (int n)
{
Tnode node2;
node2.p = p->ch[n];
return node2;
}
// add a child node
void add_child ()
{
Tnode_<T> * chp;
chp = new Tnode_ < T >;
chp->parentp = p;
p->ch.push_back (chp);
}
// number of children
int Nchildren ()
{
return p->ch.size ();
}
// the first child node
Tnode begin ()
{
Tnode node2;
node2.p = p->ch.front ();
return node2;
}
// the last child node
Tnode end ()
{
Tnode node2;
node2.p = p->ch.back ();
return node2;
}
// the parent node
Tnode parent ()
{
Tnode node2;
node2.p = p->parentp;
return node2;
}
T *operator & ()
{
return &p->data;
}
};
// make a tree head and set node to this head
template < class T > void
make_head (Tnode < T > &node)
{
node.p = new Tnode_ < T >;
node.p->parentp = NULL;
}
// print the tree
template < class T > void
travel (Tnode < T > node, int level)
{
for (int i = 0; i < level; i++)
cout << " :";
cout << ". ";
cout << node.get () << "\n";
for (int i = 0; i < node.Nchildren (); i++)
travel (node.child (i), level + 1);
}
// cut a child
template < class T > void
cut_child (Tnode < T > node, int n)
{
Tnode<T> childnode = node.child (n);
while (childnode.Nchildren () > 0) {
cut_child (childnode, 0);
}
delete node.p->ch[n];
node.p->ch.erase (node.p->ch.begin () + n);
}
// ntree.C
#include "ntree.hh"
node.add_child ();
node.add_child ();
travel (head, 0);
cout << "-----------\n";
cout << node.get () << "\n";
*&node = "CHERRY";
cout << *&node << "\n";
while (! node.ishead()) {
node=node.parent();
cout << node.get() << "\n";
}
cout << "-----------\n";
cut_child(head,0);
travel(head, 0);
You can make things somewhat simpler by using smart pointers instead of
raw pointers as you are doing. Are you familiar with smart pointers?
They handle the freeing of allocated memory automatically using
reference counting.
I don't think there is any simpler way to implement a tree. One
alternative is to implement a n-ary tree using a binary tree.
template <class T>
struct Node
{
T value;
Node* left;
Node* right;
Node* parent;
};
The left link points to the first child, the right link points to the
next sibling. The parent link points to the parent node in binary tree
terms not n-ary tree terms. See below for how to get the n-ary tree
parent node.
Then you can write functions like this
Node* Node::get_first_child()
{
return left;
}
Node* Node::get_next_child()
{
return right;
}
// loop though all children
Node* child = parent->get_first_child()
while (child)
{
// do something
child = child->get_next_child();
}
bool Node::is_first_child()
{
return parent == 0 || parent->left == this;
}
bool Node::get_parent()
{
Node* x = this;
while (!x->is_first_child())
x = x->parent;
return x ? x->parent : 0;
}
I like this idea, but I don't know if it is simpler than your method,
which is the straightforward implementation.
john
No I don't know what they are. How could they simplify the branch cut?
I would not have to go through the nodes to delete them one by one?