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
-----BEGIN PGP SIGNED MESSAGE-----
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;

public:
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.

Cheers,
Maurizio Tomasi.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)
Comment: Using GnuPG with SUSE - http://enigmail.mozdev.org

iD8DBQFEjtwof5EaQtfBD9oRAmdUAJ0V2OVgyczfEsWeLKdXSS uGjtDF4QCfRHNH
Xz+6WPfqjUr2xQmy+ePlaIk=
=ajOr
-----END PGP SIGNATURE-----
Jun 19 '06 #1
Share this Question
Share on Google+
1 Reply


P: n/a
What about:

class Node {
protected:
std::list<Node *> child_list;
Node* parent;
Node();
public:
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 ) )
{
child_list.push_back(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.