Re^5: How do I create a binary tree ?

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});

}
[download]

Comment on Re^5: How do I create a binary tree ? Download Code

Replies are listed 'Best First'.

Re^6: How do I create a binary tree?
by Athanasius (Archbishop) on Dec 22, 2015 at 06:44 UTC

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};
    }
}
[download]

Hope that helps,

Athanasius <°(((>< contra mundum Iustus alius egestas vitae, eros Piratica,

[reply]
[d/l]
[select]


Keep It Simple, Stupid
	PerlMonks