Navigating Classes in a Tree Structure?

Discussion in 'C++' started by Steve Edwards, Jan 19, 2007.

  1. Hi,

    I have a class which contains a single ptr to another instance which is
    considered its parent, and an array of ptrs to its children

    class Nodes{

    ....

    Nodes *mSuper;
    vector<<Nodes*> *mChildren;

    }


    Eventually I end up with a structure with one node at the top (with no
    parents) and many leaf nodes at the bottom with no children.

    I'm guessing this would be called a tree structure?... either way I
    assume it's a very common structure.

    Given the top node, what is the most efficient way to calculate the
    final depth of the tree? (i.e. how many ptr links from the most deeply
    nested leaf, to the top) I've got in a right old mess trying to keep
    track of globals that note my position in the tree.


    If , as I suspect, this is a common device, what terms could I search
    for to look for code examples for working with these structures?

    Many thanks

    Steve
     
    Steve Edwards, Jan 19, 2007
    #1
    1. Advertising

  2. Steve Edwards

    Lionel B Guest

    On Fri, 19 Jan 2007 09:06:09 +0000, Steve Edwards wrote:

    > Hi,
    >
    > I have a class which contains a single ptr to another instance which is
    > considered its parent, and an array of ptrs to its children
    >
    > class Nodes{
    >
    > ...
    >
    > Nodes *mSuper;
    > vector<<Nodes*> *mChildren;
    >
    > }
    >
    >
    > Eventually I end up with a structure with one node at the top (with no
    > parents) and many leaf nodes at the bottom with no children.
    >
    > I'm guessing this would be called a tree structure?... either way I
    > assume it's a very common structure.
    >
    > Given the top node, what is the most efficient way to calculate the
    > final depth of the tree? (i.e. how many ptr links from the most deeply
    > nested leaf, to the top) I've got in a right old mess trying to keep
    > track of globals that note my position in the tree.
    >
    >
    > If , as I suspect, this is a common device, what terms could I search
    > for to look for code examples for working with these structures?


    Depth-first search:

    http://en.wikipedia.org/wiki/Depth_first_search

    --
    Lionel B
     
    Lionel B, Jan 19, 2007
    #2
    1. Advertising

  3. Steve Edwards

    Steve555 Guest

    Lionel B wrote:
    > On Fri, 19 Jan 2007 09:06:09 +0000, Steve Edwards wrote:
    >
    > > Hi,
    > >
    > > I have a class which contains a single ptr to another instance which is
    > > considered its parent, and an array of ptrs to its children
    > >
    > > class Nodes{
    > >
    > > ...
    > >
    > > Nodes *mSuper;
    > > vector<<Nodes*> *mChildren;
    > >
    > > }
    > >
    > >
    > > Eventually I end up with a structure with one node at the top (with no
    > > parents) and many leaf nodes at the bottom with no children.
    > >
    > > I'm guessing this would be called a tree structure?... either way I
    > > assume it's a very common structure.
    > >
    > > Given the top node, what is the most efficient way to calculate the
    > > final depth of the tree? (i.e. how many ptr links from the most deeply
    > > nested leaf, to the top) I've got in a right old mess trying to keep
    > > track of globals that note my position in the tree.
    > >
    > >
    > > If , as I suspect, this is a common device, what terms could I search
    > > for to look for code examples for working with these structures?

    >
    > Depth-first search:
    >
    > http://en.wikipedia.org/wiki/Depth_first_search
    >
    > --
    > Lionel B


    Thanks, that's opened up a whole area to explore. As yet I haven't
    found code for determining the maximum depth; I know how to recursively
    search through each branch until I hit leaf nodes, but keeping track of
    the depth seems tricky.
     
    Steve555, Jan 19, 2007
    #3
  4. Steve Edwards

    kwikius Guest

    Steve555 wrote:
    > Lionel B wrote:


    > Thanks, that's opened up a whole area to explore. As yet I haven't
    > found code for determining the maximum depth; I know how to recursively
    > search through each branch until I hit leaf nodes, but keeping track of
    > the depth seems tricky.


    For future information. Generic tree traversal isnt specifically
    related to discussion of the C++ language and therefore discussion and
    queries is more appropriate posted to another group such as
    comp.programming

    regards
    Andy Little
     
    kwikius, Jan 19, 2007
    #4
  5. On Jan 19, 10:06 am, Steve Edwards <> wrote:
    > Hi,
    >
    > I have a class which contains a single ptr to another instance which is
    > considered its parent, and an array of ptrs to its children
    >
    > class Nodes{
    >
    > ...
    >
    > Nodes *mSuper;
    > vector<<Nodes*> *mChildren;
    >
    > }


    You might want to make that 'vector<Nodes*> mChildren;', it will make
    memory-management less complicated.

    > Eventually I end up with a structure with one node at the top (with no
    > parents) and many leaf nodes at the bottom with no children.
    >
    > I'm guessing this would be called a tree structure?... either way I
    > assume it's a very common structure.
    >
    > Given the top node, what is the most efficient way to calculate the
    > final depth of the tree? (i.e. how many ptr links from the most deeply
    > nested leaf, to the top) I've got in a right old mess trying to keep
    > track of globals that note my position in the tree.
    >
    > If , as I suspect, this is a common device, what terms could I search
    > for to look for code examples for working with these structures?


    If you know the max number of children that a node can have and the
    number of elements total you should be able to calculate a lower bound,
    if NC is the max number of children and NT is the total number of
    children the lower bound should be the NC'th logarithm of NT. An upper
    bound would be NT.

    If you have no rules for how the tree can be built you'll have to
    search the tree, you can use a recursive function for that.

    int getDepth(Node& n)
    {
    if (mChildren.empty())
    return 1;

    int max = 0;
    for (int i = 0; i < mChildren.size(); ++i)
    max = std::max(max, getDepth(mChildren);
    return max + 1;
    }

    I have not tested this but with a pen and a bit of paper you should be
    able to check if it works or not.

    --
    Erik Wikström
     
    =?iso-8859-1?q?Erik_Wikstr=F6m?=, Jan 19, 2007
    #5
  6. Steve Edwards

    Lionel B Guest

    On Fri, 19 Jan 2007 04:01:34 -0800, Erik Wikström
    wrote:

    > On Jan 19, 10:06 am, Steve Edwards <> wrote:
    >> Hi,
    >>
    >> I have a class which contains a single ptr to another instance which is
    >> considered its parent, and an array of ptrs to its children
    >>
    >> class Nodes{
    >>
    >> ...
    >>
    >> Nodes *mSuper;
    >> vector<<Nodes*> *mChildren;
    >>
    >> }

    >
    > You might want to make that 'vector<Nodes*> mChildren;', it will make
    > memory-management less complicated.
    >
    >> Eventually I end up with a structure with one node at the top (with no
    >> parents) and many leaf nodes at the bottom with no children.
    >>
    >> I'm guessing this would be called a tree structure?... either way I
    >> assume it's a very common structure.
    >>
    >> Given the top node, what is the most efficient way to calculate the
    >> final depth of the tree? (i.e. how many ptr links from the most deeply
    >> nested leaf, to the top) I've got in a right old mess trying to keep
    >> track of globals that note my position in the tree.
    >>
    >> If , as I suspect, this is a common device, what terms could I search
    >> for to look for code examples for working with these structures?

    >
    > If you know the max number of children that a node can have and the
    > number of elements total you should be able to calculate a lower bound,
    > if NC is the max number of children and NT is the total number of
    > children the lower bound should be the NC'th logarithm of NT. An upper
    > bound would be NT.
    >
    > If you have no rules for how the tree can be built you'll have to
    > search the tree, you can use a recursive function for that.
    >
    > int getDepth(Node& n)
    > {
    > if (mChildren.empty())
    > return 1;
    >
    > int max = 0;
    > for (int i = 0; i < mChildren.size(); ++i)
    > max = std::max(max, getDepth(mChildren);
    > return max + 1;
    > }
    >
    > I have not tested this but with a pen and a bit of paper you should be
    > able to check if it works or not.


    Haven't tested this either, but note that it is essentially depth-first
    search. The crucial point about depth-first search is that it utilises a
    stack to keep track of the search path - and the current depth during
    search is just the current size of the stack. Note that in Erik's example
    above there is indeed a stack: the runtime function call stack.

    On a practical note, using the runtime call stack as above may be
    inefficient or problematic if you have a really big tree; in particular
    you might run into some (system-dependent) function call stack size limit.
    In which case, it might be better to implement your own stack using, say,
    std::stack or std::vector.

    --
    Lionel B
     
    Lionel B, Jan 19, 2007
    #6
  7. Steve Edwards

    Jorgen Grahn Guest

    On 19 Jan 2007 02:41:30 -0800, Steve555 <> wrote:
    >
    > Lionel B wrote:

    ....
    >> http://en.wikipedia.org/wiki/Depth_first_search

    ....
    > Thanks, that's opened up a whole area to explore. As yet I haven't
    > found code for determining the maximum depth; I know how to recursively
    > search through each branch until I hit leaf nodes, but keeping track of
    > the depth seems tricky.


    The recursive definition is quite trivial:

    - the depth of a leaf that is a leaf is 1 (or 0? Whatever.)
    - the depth of another node is 1 + max(the set of its children's depths)
    - the depth of a tree is the depth of its root node.

    /Jorgen

    --
    // Jorgen Grahn <grahn@ Ph'nglui mglw'nafh Cthulhu
    \X/ snipabacken.dyndns.org> R'lyeh wgah'nagl fhtagn!
     
    Jorgen Grahn, Jan 19, 2007
    #7
  8. Roland Pibinger, Jan 19, 2007
    #8
  9. Steve Edwards

    Jon Harrop Guest

    Steve Edwards wrote:
    > Given the top node, what is the most efficient way to calculate the
    > final depth of the tree? (i.e. how many ptr links from the most deeply
    > nested leaf, to the top) I've got in a right old mess trying to keep
    > track of globals that note my position in the tree.


    He is a simple program to compute a symbolic derivative:

    http://www.codecodex.com/wiki/index.php?title=Derivative

    The symbolic expression is stored as a tree. The easiest way to write this
    kind of C++ is to prototype it in a language with better support for these
    kinds of data structures, i.e. a language with GC and pattern matching.

    Adding pointers from nodes to non-child nodes (e.g. parents) is an
    optimisation. So don't do it first. Get a first working version that only
    has children in each node.

    --
    Dr Jon D Harrop, Flying Frog Consultancy
    Objective CAML for Scientists
    http://www.ffconsultancy.com/products/ocaml_for_scientists/index.html?usenet
     
    Jon Harrop, Jan 20, 2007
    #9
  10. Steve Edwards

    Steve555 Guest

    Jon Harrop wrote:
    > Steve Edwards wrote:
    > > Given the top node, what is the most efficient way to calculate the
    > > final depth of the tree? (i.e. how many ptr links from the most deeply
    > > nested leaf, to the top) I've got in a right old mess trying to keep
    > > track of globals that note my position in the tree.

    >
    > He is a simple program to compute a symbolic derivative:
    >
    > http://www.codecodex.com/wiki/index.php?title=Derivative
    >
    > The symbolic expression is stored as a tree. The easiest way to write this
    > kind of C++ is to prototype it in a language with better support for these
    > kinds of data structures, i.e. a language with GC and pattern matching.
    >
    > Adding pointers from nodes to non-child nodes (e.g. parents) is an
    > optimisation. So don't do it first. Get a first working version that only
    > has children in each node.
    >
    > --
    > Dr Jon D Harrop, Flying Frog Consultancy
    > Objective CAML for Scientists
    > http://www.ffconsultancy.com/products/ocaml_for_scientists/index.html?usenet


    Many thanks to everyone for all the info and links. Eric, your code
    worked well, thank you.
     
    Steve555, Jan 23, 2007
    #10
    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. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,198
  2. sharan
    Replies:
    4
    Views:
    705
    CBFalconer
    Oct 30, 2007
  3. sharan
    Replies:
    2
    Views:
    859
    SM Ryan
    Oct 31, 2007
  4. sharan
    Replies:
    1
    Views:
    708
    CBFalconer
    Oct 30, 2007
  5. anne001
    Replies:
    1
    Views:
    252
Loading...

Share This Page