Re: Free STL compatible C++ tree container

Discussion in 'C++' started by TDH1978, Aug 9, 2012.

  1. TDH1978

    TDH1978 Guest

    On 2012-08-07 17:14:33 +0000, Leigh Johnston said:

    > I present a free to use/modify C++ "tree" container that is so named
    > because it can represent a general hierarchical collection of elements
    > using a tree-like structure. Examples of things which use such general
    > tree-like structures include file systems, XML elements in an XML
    > document or the items in a GUI tree control or menu. The C++ Standard
    > Library includes containers which use a binary (2-ary) search tree as
    > their underlying data structure (std::set, std::multiset, std::map and
    > std::multimap) but their interfaces are designed for accessing the
    > elements as an ordered sequence of elements with no hierarchy and do
    > not provide direct access to the underlying tree data structure; tree
    > on the other hand provides an interface for accessing the
    > (non-fixed-ary) tree directly allowing siblings to be iterated, parent
    > elements to be determined etc.


    Thank you for developing and sharing this code. I have one question.
    Trees are usually traversed in either pre-order, post-order, or
    in-order. During traversal, an action can be taken at each node (via
    callbacks, for example). Given your interface, how would I traverse an
    entire tree without having to write multiple nested loops?

    To give you an example of someone who has done similar stuff, with
    traversal iterators (supporting all three traversal methods):
    http://tree.phi-sci.com/
    http://tree.phi-sci.com/tree.pdf
    TDH1978, Aug 9, 2012
    #1
    1. Advertising

  2. TDH1978

    TDH1978 Guest

    On 2012-08-09 21:07:51 +0000, Leigh Johnston said:

    > There are currently two iterator types: pre-order (iterator) and
    > sibling (sibling_iterator); so to iterate the entire tree without
    > nested loops use the pre-order iterators but please note 'tree' is
    > *not* a search tree.


    Can you please tell me what you mean by "search" tree. Do you mean
    that your tree structure is not optimized for searching?
    TDH1978, Aug 9, 2012
    #2
    1. Advertising

  3. TDH1978

    TDH1978 Guest

    On 2012-08-09 21:27:47 +0000, Leigh Johnston said:

    > I mean it is an unordered container not an ordered container like
    > std::set which is implemented using a binary search tree.


    Understood. About twenty years ago, I had to write my own tree
    container. At the time, STL did not exist and RogueWave was the C++
    library king. RogueWave did not have a tree container but they did
    have dictionaries (similar to STL's map). To get around the slow tree
    search, I used my tree container in combination with a dictionary. The
    dictionary would contain the actual node payload and pointers to the
    nodes in the tree. The tree would contain the relationhip information
    (root, parents, children, siblings) and pointers back to the dictionary
    elements. The disadvantage of this approach was that the two
    structures had to be kept in sync (making inserts and deletes slower).

    I will try out your code in the next project that requires a tree
    container. If by then you have not added post-order and in-order
    traversal, I will add them myself and send you the patch via your
    website.
    TDH1978, Aug 9, 2012
    #3
  4. TDH1978

    Luca Risolia Guest

    On 09/08/2012 23:50, TDH1978 wrote:
    > I will try out your code in the next project that requires a tree
    > container. If by then you have not added post-order and in-order
    > traversal, I will add them myself and send you the patch via your website.


    If you are interested in another kind of tree or in a tree with an
    in-order iterator, sometime ago I implemented a SplayTree (an ordered
    container this time) offering an in-order Input, const_iterator. I used
    the SplayTree as a base for a simple HashMap based on linear hashing:

    http://www.linux-projects.org/listing/cpp_solutions/17.28/SplayTree.h
    Luca Risolia, Aug 10, 2012
    #4
  5. TDH1978 <> wrote:
    > I will try out your code in the next project that requires a tree
    > container. If by then you have not added post-order and in-order
    > traversal, I will add them myself and send you the patch via your website.


    How would you define in-order traversal on a unordered non-binary tree?

    /Tobi
    Tobias Müller, Aug 10, 2012
    #5
  6. TDH1978

    Melzzzzz Guest

    On Thu, 9 Aug 2012 17:21:25 -0400
    TDH1978 <> wrote:

    > On 2012-08-09 21:07:51 +0000, Leigh Johnston said:
    >
    > > There are currently two iterator types: pre-order (iterator) and
    > > sibling (sibling_iterator); so to iterate the entire tree without
    > > nested loops use the pre-order iterators but please note 'tree' is
    > > *not* a search tree.

    >
    > Can you please tell me what you mean by "search" tree. Do you mean
    > that your tree structure is not optimized for searching?
    >


    I think he means that tree is not sorted.
    Melzzzzz, Aug 10, 2012
    #6
  7. TDH1978

    TDH1978 Guest

    On 2012-08-10 06:05:28 +0000, Tobias Müller said:

    > How would you define in-order traversal on a unordered non-binary tree?


    It's awkward for non-binary trees. I used to use
    firstchild-parent-child-child-child...
    TDH1978, Aug 10, 2012
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    4
    Views:
    780
    Daniel T.
    Feb 16, 2006
  2. Nordlöw
    Replies:
    2
    Views:
    787
    Marcel Müller
    Apr 16, 2008
  3. Juha Nieminen
    Replies:
    0
    Views:
    381
    Juha Nieminen
    Aug 7, 2012
  4. Luca Risolia
    Replies:
    12
    Views:
    647
    Luca Risolia
    Aug 11, 2012
  5. Ansel
    Replies:
    1
    Views:
    391
    Juha Nieminen
    Aug 16, 2012
Loading...

Share This Page