Building Tree for list of nodes in level order
Author Message
Building Tree for list of nodes in level order

I have list of nodes in level order and I want to reproduce the tree
from the list of nodes. For example, the list {1, 2, 3, 4, 5, 6, 7)
should produce the tree:
L1  L2  L3  L4
1
2
3
4
5
6
7

The number of children a particular node can have is given, but as the
example shows the number of children can be different for each node.
Any information that will help would be much appreciated. Thanks.

Bryan Smith
--

Sat, 07 May 2005 15:24:43 GMT
Building Tree for list of nodes in level order

Quote:

> I have list of nodes in level order and I want to reproduce the tree
> from the list of nodes. For example, the list {1, 2, 3, 4, 5, 6, 7)
> should produce the tree:
> L1  L2  L3  L4
> 1
>     2
>         3
>         4
>             5
>     6
>         7

> The number of children a particular node can have is given, but as the
> example shows the number of children can be different for each node.

Maybe I'm missing something, but I don't think that with the given
constraints the problem can be solved. For example another legal (though
somewhat unbalanced) tree which can be created from this list is

L1 L2 L3 L4 L5 L6 L7
1
2
3
4
5
6
7
--

Sun, 08 May 2005 05:28:06 GMT
Building Tree for list of nodes in level order
It was late when I posted this message and I messed up the tree.
The tree should look like this:
L1  L2  L3  L4
1
2
4
5
7
3
6

Quote:
> I have list of nodes in level order and I want to reproduce the tree
> from the list of nodes. For example, the list {1, 2, 3, 4, 5, 6, 7)
> should produce the tree:
> L1  L2  L3  L4
> 1
>     2
>         3
>         4
>             5
>     6
>         7

> The number of children a particular node can have is given, but as the
> example shows the number of children can be different for each node.
> Any information that will help would be much appreciated. Thanks.

>                      Bryan Smith

--

Sun, 08 May 2005 05:28:49 GMT
Building Tree for list of nodes in level order

Quote:

> It was late when I posted this message and I messed up the tree.
> The tree should look like this:
> L1  L2  L3  L4
>  1
>      2
>          4
>          5
>              7
>      3
>          6

The only rules so far seem to be that element n+1 must be at the same depth or
deeper than element n. That's not enough. What are the rules for branching?
Why does it not go:

2
/
1   4
\ /
3   6
\ / \
5   7

for instance?

-Ed
--

Mon, 09 May 2005 15:48:54 GMT
Building Tree for list of nodes in level order

Quote:

> Maybe I'm missing something, but I don't think that with the given
> constraints the problem can be solved.

That's right; the list he gave is ambiguous.  However, he also
indicated that information about the number of children was
available for each node.  So the actual input must be two
lists.  I can't see how this is supposed to be a hard problem.
--

Mon, 09 May 2005 15:49:18 GMT
Building Tree for list of nodes in level order

Quote:

> I have list of nodes in level order and I want to reproduce the tree
> from the list of nodes. For example, the list {1, 2, 3, 4, 5, 6, 7)
> should produce the tree:
> L1  L2  L3  L4
> 1
>     2
>         3
>         4
>             5
>     6
>         7

Hmmm, that doesn't appear to be in level order.  Level order might
produce

L1  L2  L3  L4
1
2
3
4
5
6
7

or it might product some other arrangement, depending on how many nodes
you place at each level.

Your ordering might be depth-first, left to right.

Quote:
> The number of children a particular node can have is given, but as the
> example shows the number of children can be different for each node.
> Any information that will help would be much appreciated. Thanks.

This means to me that the shape of the tree is know exactly from the
beginning, but not the value of each of the nodes.  If the order is
depth-first, left to right, then start at the top, traverse the tree in
the same order, and fill each node with the value from the list before
moving to the next one in order.

[ about comp.lang.c++.moderated. First time posters: do this! ]
--

Mon, 09 May 2005 15:49:25 GMT
Building Tree for list of nodes in level order

Quote:

> > Maybe I'm missing something, but I don't think that with the given
> > constraints the problem can be solved.

> That's right; the list he gave is ambiguous.  However, he also
> indicated that information about the number of children was
> available for each node.  So the actual input must be two
> lists.  I can't see how this is supposed to be a hard problem.

> The number of children a particular node can have is given,

which, since he didn't give a second input list, I understood as a
single global attribute applying to all nodes.

So either I fell victim to a subtlety of the English language, or he did
:-)
--

Wed, 11 May 2005 07:15:33 GMT
Building Tree for list of nodes in level order
On 19 Nov 2002 07:24:43 GMT, there came a drop of sanity from

Quote:
>I have list of nodes in level order and I want to reproduce the tree
>from the list of nodes. For example, the list {1, 2, 3, 4, 5, 6, 7)
>should produce the tree:
>L1  L2  L3  L4
>1
>    2
>        3
>        4
>            5
>    6
>        7

>The number of children a particular node can have is given, but as the
>example shows the number of children can be different for each node.
>Any information that will help would be much appreciated. Thanks.

>                     Bryan Smith

Not sure if I Uderstood you right, but I wrote something about
"Genetic Trees" a couple of months ago, it can be found at
http://www.geocities.com/polterguy1000
Might maybe be of interest to you...
--
"FOOT-AND-MOUTH BELIEVED TO BE FIRST VIRUS
UNABLE TO SPREAD THROUGH MICROSOFT OUTLOOK"
--

Wed, 11 May 2005 07:15:51 GMT

 Page 1 of 1 [ 8 post ]

Relevant Pages