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

Для первого узла (root) $ 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. В документации сказано:

getDepth Возвращает число, представляющее глубину инвоканта в пределах иерархия дерева :: Простые объекты.

ПРИМЕЧАНИЕ. Дерево ROOT имеет глубину -1. Это потому что Tree :: Simple предполагает, что корень дерева обычно не содержит данных, а просто якорь для веток, содержащих данные. Это может быть не интуитивно во всех случаях, поэтому я упоминаю об этом здесь.

Исходя из этого, мне кажется, что вам нужен и «якорь», который не должен содержать данных. Другими словами, ваше дерево должно выглядеть так:

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

Тогда «якорь» будет глубиной -1, «a» будет глубиной 0, а «b», «c», «d» будет глубиной 1.

Надеюсь, это поможет.

Answer 2

Вы правы.Корень должен быть включен в обход дерева.Это особенно очевидно, если вы попытаетесь выполнить обход по порядку, поскольку (учитывая, что у вашего корня есть два дочерних элемента) корень должен находиться между двумя дочерними элементами.Google это, вы увидите везде одинаковое поведение.Я даже проверил свою книгу по алгоритмам.

Я бы позаботился о том, чтобы у меня была самая новая версия модуля, и сообщил об этом как об ошибке.

Answer 3

Итак, я согласен со всеми постерами здесь, что это может немного запутать. Тем не менее, модуль хорошо зарекомендовал себя и в настоящее время используется во многих местах / основах кода, поэтому радикальное изменение поведения, такое как изменение работы \ & traverse, - это не то, что я бы развлекал.

Тем не менее, в то время, по моему мнению (и до сих пор так оно и было), существует разница между обходом (реализованным методом \ & traverse) и посещением. Если вы посмотрите на модуль Tree :: Simple :: Visitor , вы сможете достичь именно того, что вам нужно, установив соответствующий метод \ & includeTrunk. Кроме того, в этом модуле есть ряд других реализаций посетителей, которые могут оказаться полезными.

Я бы также посоветовал вам взглянуть на модуль Forest , который является современной переписью Tree :: Simple, использующей Moose . У него тоже есть метод \ & traverse, который ведет себя таким образом, но у него также есть метод \ & fmap_cont, который гораздо более мощный. Кроме того, Forest поддерживает неизменные (чистые) деревья, а также классы чтения / записи по умолчанию для сериализации / десериализации ваших деревьев, индексации деревьев, сериализации JSON и т. Д.