Tree::Simple::traverse() 没有访问树的根 - 错误或功能？

Question

如果我尝试以下代码，

#!/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";

输出

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

显示根“a”未被访问。我对树遍历的理解是所有节点都应该被访问。我是错的还是在某些情况下不访问根目录是有意义的？

附录：

Tree::Simple::traverse() 的实现如下：

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

对于第一个节点（根），$func/$post 没有被调用，因此没有对其进行访问。

如果你用它重写 traverse() ，

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
}

它就会按我的预期工作。

Answer 1

我最近一直在使用 Tree::Simple 包，我认为观察到的行为与文档一致。例如，考虑“getDepth”函数。在文档中它说：

获取深度
返回一个数字，表示调用者在范围内的深度
Tree::Simple 对象的层次结构。

注意：ROOT 树的深度为 -1。这是因为 Tree::Simple
假设树的根通常不包含数据，而只是
包含数据的分支的锚点。这可能不直观
在所有情况下，所以我在这里提到它。

由此看来，在我看来，您需要“锚”，而“锚”不得包含数据。换句话说，你的树应该是这样的：

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

然后，'anchor' 的深度为 -1，'a' 的深度为 0，'b'、'c'、'd' 的深度为 1。

希望这样有帮助。

Answer 2

你是对的。根应该包含在树遍历中。如果您尝试中序遍历，这一点尤其明显，因为（考虑到您的根有两个子节点）根应该位于两个子节点之间。谷歌一下，你会发现到处都是同样的行为。我什至检查了我的算法书。

我会确保我拥有该模块的最新版本，并将其报告为错误。

Answer 3

所以，我同意这里所有的海报，这可能有点令人困惑。然而，该模块已经很成熟，并且目前正在许多地方/代码库中使用，因此我不会接受像改变 \&traverse 工作方式这样的激进行为改变。

也就是说，我当时的观点（现在仍然如此）认为，遍历（使用 \&traverse 方法实现）和访问之间是有区别的。如果您查看 Tree::Simple::Visitor 模块，您将能够通过相应地设置 \&includeTrunk 方法来完成您所追求的目标。此外，该模块中还有许多其他访问者实现，您可能会发现它们很有用。

我还鼓励您查看 Forest 模块，这是一个现代重写使用 Moose 的 Tree::Simple 。它也有一个以这种方式运行的 \&traverse 方法，但它还有一个 \&fmap_cont 方法，该方法更强大。此外 Forest 支持不可变（纯）树以及用于序列化/的默认读取器/写入器类反序列化你的树、索引你的树、JSON 序列化等等。