Navigating Classes in a Tree Structure?

[Steve Edwards]

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

 

[Lionel B]

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

 

[Steve555]

Depth-first search:

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.

 

[kwikius]

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

 

[=?iso-8859-1?q?Erik_Wikstr=F6m?=]

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?

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.

 

[Lionel B]

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?

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.

 

[Jorgen Grahn]

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.

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

 

[Roland Pibinger]

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?

The following links may be helpful:
http://www.gamedev.net/reference/articles/article2192.asp
http://www.gamedev.net/reference/articles/article2233.asp
http://www.datasoftsolutions.net/tree_container_library/overview.php

 

[Jon Harrop]

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.

 

[Steve555]

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.

Many thanks to everyone for all the info and links. Eric, your code
worked well, thank you.