Unsorted Infinite Child Tree

[Travis]

I"m looking to find (or if I can't, make) a real simple tree with a
few characteristics
- no sorting, I want to insert a node and specify the parent
- infinite children

These characteristics should accurately reflect a menu tree. That's
what I'm going for.

The only real functionality I need is proper insertion (and as a
corrollary find). Deletion is not neccessary.

Any thoughts or points of reference? If anyone knows of such a
structure and it exists already, please link to it. Thanks.

 

[dasjotre]

I"m looking to find (or if I can't, make) a real simple tree with a
few characteristics
- no sorting, I want to insert a node and specify the parent
- infinite children

These characteristics should accurately reflect a menu tree. That's
what I'm going for.

The only real functionality I need is proper insertion (and as a
corrollary find). Deletion is not neccessary.

Any thoughts or points of reference? If anyone knows of such a
structure and it exists already, please link to it. Thanks.

I would use boost::graph. you can easily define that kind
of a tree with it. it also provides bunch of algorithms, like
breadth_first_search and depth_first_search. it doesn't provide
insert per se but it is easy to implement with add_vertex, add_edge.

regards

DS

 

[red floyd]

I"m looking to find (or if I can't, make) a real simple tree with a
few characteristics
- no sorting, I want to insert a node and specify the parent
- infinite children

I'm not sure what's out there, but if you need to roll your own, and you
need infinite children, I'd go with leftmost child/sibling.
Something like this (note: I'm just hacking this out, so...)

template<typename T>
struct Node
{
Node* lm_child;
Node* next_sibling;
T data;
Node(const T& val)
: lm_child(NULL), next_sibling(NULL), data(val) { }
// remaining methods and access control left as an
// exercise for the reader
};

 

[Travis]

Okay here's what I whipped up while waiting for a response. Haha.

http://cpp.sourceforge.net/?show=37716

Seems to work for my needs, just curious if anyone here looks at it
and says "oh dear God that's terrible".

It's basically just a tree of nodes with each node having a vector of
children. The find is probably the most inefficient part but it's
recursive so maybe that helps a bit.

Thanks.

 

[dasjotre]

Okay here's what I whipped up while waiting for a response. Haha.

http://cpp.sourceforge.net/?show=37716

Seems to work for my needs, just curious if anyone here looks at it
and says "oh dear God that's terrible".

I haven't looked at your code (sorry, I'm at work and I can't download
stuff easily).

It's basically just a tree of nodes with each node having a vector of
children.

you mean it is a node with vector of nodes.

The find is probably the most inefficient part but it's
recursive so maybe that helps a bit.

you got it completely wrong in assuming that recursion might
make your code more efficient. you should avoid recursion because
it is much more inefficient than loops. also, if you have deep
recursion
you can run out of stack space, stack size is fixed.

some algorithms look nicer when implemented with recursion but that
doesn't make them more efficient.

you can always replace recursion with a loop.

Thanks.

regards

DS