As I was working on a paper on data structures for trees I came across the problem of explaining various tree traversal types. In the attached code I (am hoping to..) demonstrate:
#!/usr/bin/perl
use strict;
use warnings;
use Bio::Phylo::Parsers;
# the single quoted string is a parenthetical
# tree description in "Newick" format. This
# format can be visualized using, among other
# programs, TreeView:
# http://taxonomy.zoology.gla.ac.uk/rod/rod.html
my $treestring = '(((A,B)n1,C)n2,D)n3;';
my $parser = new Bio::Phylo::Parsers;
my $tree = $parser->parse(
-format => 'newick',
-string => $treestring
)->first;
my $root = $tree->get_root;
print qq{###########PRE-ORDER########\n};
&pre_order($root);
print qq{###########IN-ORDER#########\n};
&in_order($root);
print qq{##########POST-ORDER########\n};
&post_order($root);
print qq{##########DEPTH FIRST#######\n};
&depth_first($root);
print qq{#########BREADTH FIRST######\n};
&breadth_first($root);
sub pre_order {
my $node = shift;
print $node->get_name, "\n";
my $fd = $node->get_first_daughter;
my $ld = $node->get_last_daughter;
&pre_order($fd) if $fd;
&pre_order($ld) if $ld;
}
sub in_order {
my $node = shift;
my $fd = $node->get_first_daughter;
my $ld = $node->get_last_daughter;
&in_order($fd) if $fd;
print $node->get_name, "\n";
&in_order($ld) if $ld;
}
sub post_order {
my $node = shift;
my $fd = $node->get_first_daughter;
my $ld = $node->get_last_daughter;
&post_order($fd) if $fd;
&post_order($ld) if $ld;
print $node->get_name, "\n";
}
sub depth_first {
my $node = shift;
print $node->get_name, "\n";
my $fd = $node->get_first_daughter;
my $ns = $node->get_next_sister;
if ( $fd ) {
&depth_first($fd);
}
if ( $ns ) {
&depth_first($ns);
}
}
sub breadth_first {
my $node = shift;
print $node->get_name, "\n";
my $fd = $node->get_first_daughter;
my $ns = $node->get_next_sister;
if ( $ns ) {
&breadth_first($ns);
}
if ( $fd ) {
&breadth_first($fd);
}
}