$tree = [[], $key, []];

    sub traverse;
    sub traverse {
        return unless @{$_ [0]};
        traverse $_ [0] [0];
        print    $_ [0] [1];
        traverse $_ [0] [2];
    }
[download]

That's an in-order traversal. Your structure has the advantage that it can deal with any number of children, while the code above assumes 2 children for each non-empty node; as is common for binary trees.

Abigail

  sub parse {
     my @stack = @_;
     while (@stack) {
        my $node = pop @stack;
        print $node->{data};
        push @stack, @{$node->{children}};
     }
  }
[download]

-sam

sub traverse {
    my($node, $visitor) = @_;

    $visitor->pre_order($node);
    traverse($node->{left}, $visitor) if defined $node->{left};
    $visitor->in_order($node);
    traverse($node->{right}, $visitor) if defined $node->{right};
    $visitor->post_order($node);
}
[download]

This approach is rather expensive (in terms of excess method calls), and in terms of stack space, but is still useful on occassion.

You can probably get away without checking for the existance of @{$t->{children}}. Either that or change:

if(@{$t->{children}}){
[download]

with

if($#{$t->{children}} > 0){
[download]

or some other variant. Depends on how you create the node.

Must admit I've never noticed C like strcutures in Perl (such as trees and link-lists). Recently I've wondered why. Could be that there are, just I've never noticed...

!unlike

"The price if ignorance, which is of course that you must learn from those who know." Socrates (paraphrased)

You can probably get away without checking for the existance of @{$t->{children}}.

Eh, yer probably right.

But why would I want to do:

change:

if(@{$t->{children}}){

with

if($#{$t->{children}} > 0){
[download]

?

why would I want to do

You wouldn't. :-) I _think_ the issue the OP was refering to (but actually doesnt deal with) is the possibility that children is undef. Since the dereference is a fetch it wont be automagically created and the if ( @{...} ) will choke. Personally I would replace it and the for with the following

for my $child ( @{ $t->{children} || [] } ) {
}
[download]

Normally I dont put so much whitespace in my expressions, but I figured here it makes things clearer, When dereferencing, if $t->{children} is false then we use an empty anonymous array to iterate over. We dont have to check if there are elements, because if there are, we _will_ iterate over them, and if there are, well, we _wont_.

BTW, Its a good idea to become quite familiar with binary trees before you play with n-ary trees. It helps to solidy the concepts. A good learning exercise is to implement a Tie::Hash using a binary tree. (Say a sorted hash implemented using a binary tree?) Incidentally any tree structure can be represented using binary trees if necessary so it pays off to understand them well.

HTH


---
demerphq

_{<Elian> And I do take a kind of perverse pleasure in having an OO assembly language...}

Some of those data structures that you never notice, the reason that you never notice them being coded up in Perl is because they don't have to be coded up by hand; Perl has stuff that accomplishes the same thing without a lot of extra work. Linked lists are a perfect example. Nobody _needs_ to code up linked lists in Perl, because Perl isn't so primitive as C. Perl isn't Lisp, but it has more builtin list-processing stuff than C. C programmers find them using linked lists sometimes when they don't know the length of an array at compile time; we don't need that sort of kludge in Perl because arrays are dynamic in length. We also don't need them for most of the other things they're used for in C (e.g., inserting items in the middle), because again Perl already has enough power to do stuff like that without the extra help. Linked lists are also used to implement stacks sometimes, but Perl just uses arrays for that. That's what we have push and pop for, after all. Trees you will occasionally see in Perl, though; I think there are a CPAN module or two for working with them. But there is one major use of trees that you won't see much in Perl: they're often used for sorting and searching, and Perl programmers are more likely to use hashes for that, or the builtin sort primitive, or both together, or throw it all in a database and use DBI. But trees are generally useful, so you will see them used sometimes for other things, as well as directed and undirected graphs occasionally

Hmm, his code seems perfectly right to me. Your code skips the case where the children array may have only 1 element.



@bing = ("1");
print scalar @bing," ",$#bing,$/;
if ($#bing > 0) { # your conditional
 print "Would execute$/"; 
}
else {
 print "Wouldn't execute$/";
}

__END__

Results:
1 0
Wouldn't execute
[download]





antirice    
The first rule of Perl club is - use Perl
The ith rule of Perl club is - follow rule i - 1 for i > 1