Tree :: Simple :: traverse () does not visit the root of the tree - error or function?

Question

if i try the following code

#!/usr/bin/env perl use Tree::Simple; # Tree: # a # _________ | ________ # / | \ # bcd # / \ # ef # \ # 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"; 

conclusion

 ------ 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 

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

Application:

The 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 is not called, so it is not available for visiting.

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.

Answer 1

I recently used the Tree :: Simple package, and I think the observed behavior is consistent with the documentation. Consider, for example, the getDepth function. The documentation says:

getDepth Returns a number representing the call depth within the tree hierarchy :: Simple objects.

NOTE. The ROOT tree has a depth of -1. This is due to the fact that Tree :: Simple assumes that the root of the tree usually does not contain data, but simply an anchor for branches containing data. This can be unintuitive in all cases, so I mention it here.

From this, it seems to me that you need to “bind”, which should not contain data. In other words, your tree should look like this:

 # Tree: # anchor # | # a # _________ | ________ # / | \ # bcd # / \ # ef # \ # g # 

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

Hope this helps.

Answer 2

You're right. The root must be included in the tree traversal. This is especially clear if you are trying to get around the order, because (given that your root has two children) the root must be between two children. Google this, you will see the same behavior everywhere. I even checked my book on algorithms.

I would make sure that I have the latest version of the module and report it as an error.

Answer 3

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

However, it was my opinion at the time (and still is) that there is a difference between a crawl (implemented using the & traverse method) and a visit. If you look at the "Tree :: Simple :: Visitor" , you can accomplish what you need by setting the \ & includeTrunk method accordingly. In addition, there are a number of other visitor implementations in this module.

I also recommend that you take a look at the Forest module, which is a modern rewrite of Tree :: Simple that uses Moose . It also has a \ & traverse method that behaves this way, but it also has a \ & fmap_cont method, which is much more efficient. Additionally, Forest supports immutable (clean) trees, as well as default read / write classes for serializing / deserializing your trees, indexing your trees, JSON Serialization, and much more.