tree template

[nandor.sieben]

I'm working on a project analyzing a game and I am in need of a tree
template library. I found a few implementations on the web but all of
them were too complicated for me to understand. I wrote something on my
own. I used an STL vector to store children of a node. My major concern
is memory leak. I am not sure if doing a pop_back() to cut a tree
branch would result in memory leak. I would appreciate some advise on
this. Also is there a similarly simple but well tested implementation
out there?

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";

}

 

[John Harrison]

I'm working on a project analyzing a game and I am in need of a tree
template library. I found a few implementations on the web but all of
them were too complicated for me to understand. I wrote something on my
own. I used an STL vector to store children of a node. My major concern
is memory leak. I am not sure if doing a pop_back() to cut a tree
branch would result in memory leak. I would appreciate some advise on
this. Also is there a similarly simple but well tested implementation
out there?

Nandor

#include <vector>

#include <string>

using namespace std;

// data and the arrows

template < class T > struct Tnode_

{

T data;

vector < Tnode_ > ch;

Tnode_ *parentp;

};

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

 

[nandor.sieben]

Thank you for the advise, I didn't think of this problem. Here is the
second attempt using the suggested pointers. I have a feeling this made
the memory requirement a lot larger :-(. Is there a much simpler
implementation?

// 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"


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";
while (! node.ishead()) {
node=node.parent();
cout << node.get() << "\n";
}

cout << "-----------\n";
cut_child(head,0);
travel(head, 0);

 

[John Harrison]

Thank you for the advise, I didn't think of this problem. Here is the
second attempt using the suggested pointers. I have a feeling this made
the memory requirement a lot larger :-(. Is there a much simpler
implementation?

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

 

[nandor.sieben]

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.

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?