Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?
 
PerlMonks  

tree traversal types

by rvosa (Curate)
on Aug 08, 2005 at 19:28 UTC ( #481985=snippet: print w/replies, xml ) Need Help??
Description: 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);
    }
}
Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: snippet [id://481985]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (1)
As of 2021-12-09 02:10 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    R or B?



    Results (36 votes). Check out past polls.

    Notices?