[boost] Re: boost::tree advice?

From: Thorsten Ottosen (nesotto_at_[hidden])
Date: 2005-03-29 12:27:05

"David B. Held" <dheld_at_[hidden]> wrote in message 
news:d2b14r$ekf$1_at_sea.gmane.org...
| Dan Rosen wrote:

| > [...]
| > And in a general-purpose tree, it would be:
| >
| >   struct node {
| >     node* parent_;
| >     node* first_child_;
| >     node* last_child_;
| >     node* prev_sibling_;
| >     node* next_sibling_;
| >     T* value_;
| >   };
| >
| > Would you consider five pointers to be too much?
|
| Yes.  I don't see what's wrong with my original suggestion:
|
| template <int K = 2, int N = 1>
| struct node
| {
|     node* parent_;
|     node* child_[K];
|     T value_[N];
| };

There is an alternative that doesn't really need a node concept. It goes like 
this

template< class T >
class tree
{
    T data_;
     boost::optional< boost::ptr_vector<tree<T> > > children_;
    tree* parent_;
    ...
};

for n-ary trees, exchange ptr_vector<> with ptr_array<,N>.

-Thorsten