Is there an n-ary tree implementation in Perl?

Question

I'm writing a Perl script and would like to use a n-ary tree data structure.

Is there a good implementation that is available as source code (rather than part of a Perl library) ?

Answer 1

I don't really understand why you want it was "source" rather than as a perl library, but you can download the source for any CPAN module.

I haven't used it, but Tree looks to fill your requirements.

Answer 2

Adding to what Matthew already said, it looks like the following modules would be suitable:

Tree::Nary
Tree::Simple
Tree

Answer 3

Depending on what you need a tree structure for, you might not need any pre-built implementation. Perl already supports them using arrays of arrayrefs.

For example, a simple representation of this tree

             t
           /   \
          a     d
         / \   / \
        b   c e   f

could be represented by the following Perl code:

$tree = [ t => [ a => [ b => [], c => [] ]
                 d => [ e => [], f => [] ] ] ];

Here, the tree's representation is as nested pairs: first the element (in this case, the letter), then an anonymous array reference representing the children of that element. Note that => is just a fancy comma in Perl that exempts you having to put quotes around the the token to the left of the comma, provided it is a single word. The above code could also have been written thus:

$tree = [ 't', [ 'a' , [ 'b' , [], 'c' , [] ]
                 'd' , [ 'e' , [], 'f' , [] ] ] ];

Here's a simple depth-first accumulator of all the elements in the tree:

sub elements {
    my $tree = shift;

    my @elements;
    my @queue = @$tree;
    while (@queue) {
        my $element  = shift @queue;
        my $children = shift @queue;
        push @elements, $element;
        unshift @queue, @$children;
    }

    return @elements;
}

@elements = elements($tree)     # qw(t a b c d e f)

(For breadth first, change the line unshift @queue, @$children to push @queue, @$children)

So, depending on what operations you want to perform on your tree, the simplest thing might be just to use Perl's built-in support for arrays and array references.