Tree::Simple::traverse() is not visiting root of tree - error or feature ?

if I try the following code

#!/usr/bin/env perl

use Tree::Simple;

# Tree:
#                   a
#         _________ | ________
#        /          |         \ 
#       b           c          d 
#                 /    \
#                e      f  
#                        \
#                         g
#

my $tree = Tree::Simple->new('a', Tree::Simple->ROOT);

$tree->addChildren( Tree::Simple->new('b'),
                    Tree::Simple->new('c'),
                    Tree::Simple->new('d'),
                  );

$tree->getChild(1)->addChildren (
                    Tree::Simple->new('e'),
                    Tree::Simple->new('f'),
);

$tree->getChild(1)->getChild(1)->addChildren (
                    Tree::Simple->new('g'),
);

$trav_func= sub {
    my $node = shift;
    printf "node : %s  leaf : %3s   root : %s\n",
           $node->getNodeValue, $node->isLeaf ? 'yes' : 'no',
           $node->isRoot ? 'yes' : 'no';
};


# traversal does not report the root - error ?
print "------ preorder : traverse( \$trav_func ) \n";
$tree->traverse( $trav_func );
print "\n";

print "------ postorder : traverse( sub{}, \$trav_func ) \n";
$tree->traverse( sub{}, $trav_func );
print "\n";

the output is

------ preorder : traverse( $trav_func ) 
node : b  leaf : yes   root : no
node : c  leaf :  no   root : no
node : e  leaf : yes   root : no
node : f  leaf :  no   root : no
node : g  leaf : yes   root : no
node : d  leaf : yes   root : no

------ postorder : traverse( sub{}, $trav_func ) 
node : b  leaf : yes   root : no
node : e  leaf : yes   root : no
node : g  leaf : yes   root : no
node : f  leaf :  no   root : no
node : c  leaf :  no   root : no
node : d  leaf : yes   root : no

showing that root 'a' is not visited. My understanding of tree traversal is that all nodes should be visited. Am I wrong or are there some cases where it makes sense not to visit the root ?

Appendix :

Tree::Simple::traverse() is implemented as :

sub traverse {
    my ($self, $func, $post) = @_;
    # ... some checks here not shown

    foreach my $child ($self->getAllChildren()) { 
 开发者_如何学运维       $func->($child);
        $child->traverse($func, $post);
        defined($post) && $post->($child);
    }
  }

For the first node (root) $func/$post are not called, so there is no visit for it.

If you override traverse() with

package My::Tree::Simple;

use parent 'Tree::Simple';

# the original code of Tree::Simple::traverse() 
# but $func() and $post() outside of foreach-loop
# allowing the root to be visited 

sub my_traverse {
    my ($self, $func, $post) = @_;
    (defined($func)) || die "Insufficient Arguments : Cannot traverse without traversal function";
    (ref($func) eq "CODE") || die "Incorrect Object Type : traversal function is not a function";
    (ref($post) eq "CODE") || die "Incorrect Object Type : post traversal function is not a function"
        if defined($post);

    $func->($self); # put outside of foreach

    foreach my $child ($self->getAllChildren()) {
        $child->my_traverse($func, $post);
    }

    defined($post) && $post->($self); # put outside of foreach
}

it works as I expected.

---

I've been recently using the Tree::Simple package and I think that the observed behavior is consistent with the documentation. Consider, for example, the 'getDepth' function. In the documentation it says:

getDepth Returns a number representing the invocant's depth within the hierarchy of Tree::Simple objects.

NOTE: A ROOT tree has the depth of -1. This be because Tree::Simple assumes that a tree's root will usually not contain data, but just be an anchor for the data-containing branches. This may not be intuitive in all cases, so I mention it here.

From this, it seems to me that you need and "anchor" that must not contain data. In other words, your tree should look like this:

# Tree:
#                 anchor
#                   | 
#                   a
#         _________ | ________
#        /          |         \ 
#       b           c          d 
#                 /    \
#                e      f  
#                        \
#                         g
#

Then, the 'anchor' will be depth -1, 'a' will be depth 0, and 'b', 'c', 'd' will be depth 1.

Hope this helps.

---

You are right. The root should be included in a tree traversal. This is especially clear if you try an inorder traversal, since (considering your root has two children) the root should be inbetween the two children. Google it, you'll see the same behavior everywhere. I even checked my book on algorithms.

I'd make sure i have the newest version of the module, and report it as an error.

---

So, I agree with all the posters here, that this can be a little confusing. However, the module is well establish and is currently being used in a number of places/codebases so a radical behavior change like changing how \&traverse works is not something I would entertain.

That said, it was my view at the time (and kind of still is), that there is a difference between traversal (implemented with the \&traverse method) and visitation. If you take a look at the Tree::Simple::Visitor module, you will be able to accomplish exactly what you are are after by setting the \&includeTrunk method accordingly. Additionally there are a number of other visitor implementations in that module that you might find useful.

I would also encourage you to take a look at the Forest module, which is a modern re-write of Tree::Simple that uses Moose . It too has a \&traverse method which behaves in this way, but it also has a \&fmap_cont method which is much more powerful. Additionally Forest has support for immutable (pure) trees as well as default reader/writer classes for serializing/deserializing your trees, indexing your trees, JSON serialization and more.