Hello ,
How can I do a Breadth First search for a binary tree in perl ?
For the above code how can I go ahead and create a subroutine for Breadth First search ?
For a breadth first search , since I have to visit the left node first and then the right node and then repeat this process till I reach the very end , I fee its sort of tricky...
I have written a snippet below for "Depth First" search , but not able to think for a Breadth first search
sub depthFirst {
my ($tree) =@_;
return unless ($tree);
print $tree->{Value};
depthFirst($tree->{Left});
depthFirst($tree->{Right});
}
| [reply]
[d/l] |
For a breadth first search , since I have to visit the left node first and then the right node and then repeat this process till I reach the very end , I fee its sort of tricky...
Not really, it just doesn’t lend itself to a recursive solution as depth-first traversal does. For the general algorithm, see the Wikipedia entry Tree_traversal#Breadth-first_2. Translated into Perl code matching the code you’ve shown for sub depthFirst, above, it will look like this (untested):
sub breadthFirst
{
my ($tree) = @_;
return unless defined $tree;
my @queue = ($tree);
print $tree->{Value};
while (@queue)
{
my $node = shift @queue;
print $node->{Value};
push @queue, $node->{Left} if defined $node->{Left};
push @queue, $node->{Right} if defined $node->{Right};
}
}
Hope that helps,
| [reply]
[d/l]
[select] |