🔒 Locked

Tree node and leaf

Started by tordyvel Jul 28, 2006 at 11:29 PM 1 replies 600+ views

Original Post

Jul 28, 2006 at 11:29 PM

Hi there! I want to make a tree structure where only the leaf has data but can't figure out a cool way to do it. The tutorials I've found use some kind of node ID like: class CTree { public: struct _Node { bool isLeaf; Data *data; _Node *children; } Node; private: Node *root; // and so on }; But mixing the leaf data and children nodes is a bit ugly. Is there no cleaner way?

ju2wheels

Jul 29, 2006 at 1:11 AM

For as many examples as Ive seen thats how its commonly done.

Might I add that you not forget to add a constructor for the node that initializes those pointers to 0/null. You can use this distinction later on by testing the data pointer to see if you have an internal node or a leaf node (since internal nodes will have null data pointers and leaf nodes will point to actual data).

snk_kid

Jul 29, 2006 at 3:16 AM

Quote:
Original post by tordyvel
But mixing the leaf data and children nodes is a bit ugly. Is there no cleaner way?

Yes there are 2 "cleaner way"s:

1. Use the composite design pattern.

2. Use tagged unions to emulate variants/algebraic data types, i suggest you do not attempt to write your own use a library in particular boost::variant. Look at the section on recursive variant types.

Each have their tradeoffs you need to think about but by default variants should be the first choice.

[Edited by - snk_kid on July 29, 2006 11:16:29 AM]

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.