By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
445,897 Members | 1,969 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 445,897 IT Pros & Developers. It's quick & easy.

Structuring a tree

P: n/a
Hash: SHA1

I am developing an application which needs to structure its data using a
tree. Each node in the tree is derived from an abstract base class
called Base. There are a number of derived classes, let's call them A,
B, C and so on. There are constraints on the children each of these
classes can have. Here are some examples:

1. Children of nodes of type A must be of type B;
2. Nodes of type C cannot have more than one child;
3. Nodes of type D must have exactly 3 child nodes of type A, B, C.
4. Nodes of type E cannot have children of type B.
5. Nodes of type F cannot have children at all.

My question is, what is the best approach to represent such complex
parent/child relationships? The "classic" way to implement trees in C++:

class Node {
std::list<Node *> child_list;

Node ();
void add_child (Node * new_child);
std::list<Node *> get_children ();

// Virtual methods useful to my program would follow here

does not allow me to implement such constraints.

Maurizio Tomasi.
Version: GnuPG v1.4.2 (GNU/Linux)
Comment: Using GnuPG with SUSE -

Jun 19 '06 #1
Share this Question
Share on Google+
1 Reply

P: n/a
What about:

class Node {
std::list<Node *> child_list;
Node* parent;
virtual ~Node();
virtual bool is_valid() { return true; }
virtual bool can_add( Node * new_child ) { return true; }
virtual void add_child( Node * new_child )
if ( new_child->is_valid() && can_add( new_child ) )
new_child->parent = this;
std::list<Node *> get_children ();

class A : public Node {
// ...
virtual bool can_add( Node * new_child )
{ return dynamic_cast<B*>( new_child ) != 0; }
class C : public Node {
// ...
virtual bool can_add( Node * new_child )
{ return child_list.empty(); }
class F : public Node {
// ...
virtual bool can_add( Node * new_child )
{ return false; }
// and so on...

-- Dmytro

Jun 20 '06 #2

This discussion thread is closed

Replies have been disabled for this discussion.