Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
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
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 drinking their drinks and smoking their pipes about the Monastery: (7)
As of 2020-06-01 13:23 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?