Beatnik has asked for the wisdom of the Perl Monks concerning the following question:

Hey,
I'm building a tree (again), which kinda consists out of double linked lists...
Structure simplified: 
Root: First = 1; Last = 5; Next = ; Previous = ;
1: First = 11; Last = 15; Next = 2; Previous = ;
2: First = 21; Last = 25; Next = 3; Previous = 1;
...
554: First = ; Last = ; Next = 555 ; Previous = 553;
555: First = ; Last = ; Next = ; Previous = 554;

[download]
This is what I currently use to get all child nodes starting from one specific point (being root or not)... again simplified : 
push(@Children,$root->child_nodes); # could be push(@Children,$start_n
+ode_id); too, any starting point...
while(@Children)
{ $node = shift @Children;
  print $node,"->";
  my $Node = Node->new($node);
  my $next = $Node->first;
  while ($next)
  { print $next,",";
    my $Child = Node->new($next);
    push(@Children,$next);
    $next = $Child->next();
  }
 print "\n";
}

[download]
Output is something similar to: 
1->11,12,13,14,15,
2->21,25,
3->31,35,
4->41,45,
5->51,55,
11->111,112,113,114,115
12->
13->
14->
15->
...

[download]
I'm not building a tree perse, the order in which I get child nodes is not important. I dont need to store all child node data, just the actual node IDs. There could be alot of child nodes, resources could get quite limited.

Are there any specific theories on running up a tree?

Greetz
Beatnik
... Quidquid perl dictum sit, altum viditur.

Replies are listed 'Best First'.
Re: Growing exotic trees
by blue_cowdawg (Monsignor) on May 27, 2001 at 05:49 UTC

        Are there any specific theories on running up a tree?

    You bet there are. You will need to do some research to find them. I was going to quote some for you from my Knuth book but decided that would be a bit much.

    I would also suggest looking around in your nearest Barnes & Noble or other favorite books store for a copy of (I think this is the title) Algorithms in Perl or Perl 5 How-To.

    Peter L. BergholdSchooner Technology Consulting, Inc.
    Peter@Berghold.Netwww.berghold.net
[reply]
      Let me rephrase :)

      Are there any specific theories on running up trees like that?

      Mastering Algorithms with Perl discusses linked lists (single, double, circular), binary trees (B-Trees & plain binary trees), heaps (binary & janus). None of these structures are exactly what I need/have... It's kinda like a combination of a double linked list and a 2-3 tree (but without the balancing, sorting, limited nodes, etc).
      The algorithm I described above works fine (altho I didn't stress test)... I'm just looking for a few pointers on how this could be more effective.
      As for the Knuth note: I have it on my wishlist, doubt I'll get em before X-mas.

      I got a flow online here, Dia XML is here

      Greetz
      Beatnik
      ... Quidquid perl dictum sit, altum viditur.
[reply]

Back to Seekers of Perl Wisdom