I have a tree that consists of several joined nodes, which are implemented as blessed hash references. Each node knows about its first child, its immediate parent, and its first sibling ({child_n}, {parent_n}, and {sibling_n} respectively). It's been pointed out to me that instead of using a singly-linked list for siblings I could have used an array ref, but I don't think that'll matter much, since order is important and so I only go through one way.
What I was wondering about is the best and most elegant way to do a postorder traversal of the tree. None of the solutions I've come up with are very elegant - I've used recursive _private_methods, recursive subroutine references, and a stack with a while { ... } continue { ... } loop, but nothing turns out very readable or convenient. Is there a better way?
Thanks in advance!
Not really. Traversing tree solutions (in any order) tend to be highly-recursive. Of course, any recursive solution can be implemented as an iterative solution, but recursion tends to be more natural for this particular problem.
As for arrayrefs vs. singly-linked list, I would venture that arrayrefs use less memory and will probably be faster. But if you have a working solution and speed/memory is acceptable, you might as well keep what you have.
----
send money to your kernel via the boot loader.. This and more wisdom available from Markov Hardburn.
One neat perl trick is the ability to push elements onto an array while you iterate over it. Note don't try to do anything but push unless you are feeling *very* lucky. For example you can 'recurse' the file structure with a handful of lines:
sub recurse_tree {
my @dirs = @_;
my @files;
for my $dir ( @dirs ) {
opendir DIR, $dir or error("Can't open $dir\n");
while ( my $file = readdir DIR ) {
next if $file eq '.' or $file eq '..';
next if -l "$dir/$file";
push @dirs, "$dir/$file" if -d "$dir/$file";
push @files, "$dir/$file" if -f "$dir/$file";
}
closedir DIR;
}
return \@dirs, \@files;
}
One of the intersting features of this algorithm is that it proceeds width first, rather than depth first as with most recursive algorithms.
cheers
tachyon
i am normally reluctant to suggest any reengineering of code presented, but i have personally saved so much time using Graph::Base, Graph::Directed and Graph::DFS that i feel compelled to sketch out the following:
use Graph::Directed;
use Graph::Base;
use Graph::DFS;
my $g = Graph::Directed->new();
growtree($g, $mydatastruct); # create the tree rooted in $g
my $search = Graph::DFS->new($g); # for the search...
while (my $vertex = $search->next_postorder()){
my $info = $g->get_attribute('myattrib',$vertex);
# do stuff with $info...
}
sub growtree{
my ($g, $mydatastruct) = @_;
my $data = # ...get stuff from $mydatastruct;
$g->set_attribute('myattrib',$g, $data);
my @newedges = # ...get new edges from $mydatastruct
$g->add_edge($g,$_) for @newedges;
my @newvertices = grep {! $g->has_vertex($_)} @newedges;
map { growtree($_,$mydatastruct) } @newvertices;
}
won't save you time immediately, but very handy in the
medium & long term.hope it helps;
-- in the world of the mules there are no rules --