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]

Re: Navigating Classes in a Tree Structure?

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

[Steve555]

Re: Navigating Classes in a Tree Structure?


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.

[kwikius]

Re: Navigating Classes in a Tree Structure?


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.programmin g

regards
Andy Little

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

Re: Navigating Classes in a Tree Structure?

On Jan 19, 10:06 am, Steve Edwards <g...@lineone.n etwrote:

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*m Children;', 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.empt y())
return 1;

int max = 0;
for (int i = 0; i < mChildren.size( ); ++i)
max = std::max(max, getDepth(mChild ren[i]);
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

[Lionel B]

Re: Navigating Classes in a Tree Structure?

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

On Jan 19, 10:06 am, Steve Edwards <g...@lineone.n etwrote:

>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<<Node s* *mChildren;
>>
>}

>
You might want to make that 'vector<Nodes*m Children;', 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.empt y())
return 1;
>
int max = 0;
for (int i = 0; i < mChildren.size( ); ++i)
max = std::max(max, getDepth(mChild ren[i]);
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

[Jorgen Grahn]

Re: Navigating Classes in a Tree Structure?

On 19 Jan 2007 02:41:30 -0800, Steve555 <foursheds@btin ternet.comwrote :

>
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.dyn dns.org R'lyeh wgah'nagl fhtagn!

[Roland Pibinger]

Re: Navigating Classes in a Tree Structure?

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

>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]

Re: Navigating Classes in a Tree Structure?

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

[Steve555]

Re: Navigating Classes in a Tree Structure?


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/product...ex.html?usenet

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