Perl 中有 n 叉树实现吗？

Question

我正在编写一个 Perl 脚本，并且想使用 n 元树数据结构。

是否有一个好的实现可以作为源代码（而不是 Perl 库的一部分）提供？

Answer 1

添加到 Matthew 已经说过的内容中，看起来以下模块是合适的：

树::纳里
树::简单
树

Answer 2

我不太明白为什么你希望它是“源代码”而不是 Perl 库，但你可以下载任何 CPAN 模块的源代码。

我没用过，但是 树 看起来可以满足您的要求。

Answer 3

根据您需要树结构的目的，您可能不需要任何预先构建的实现。Perl 已经使用 arrayrefs 数组支持它们。

例如，这棵树的简单表示

             t
           /   \
          a     d
         / \   / \
        b   c e   f

可以用下面的 Perl 代码表示：

$tree = [ t => [ a => [ b => [], c => [] ]
                 d => [ e => [], f => [] ] ] ];

在这里，树的表示形式是嵌套对：首先是元素（在本例中为字母），然后是表示该元素子元素的匿名数组引用。注意 => 只是 Perl 中的一个奇特的逗号，如果它是一个单词，那么您就不必在逗号左侧的标记周围添加引号。上面的代码也可以这样写：

$tree = [ 't', [ 'a' , [ 'b' , [], 'c' , [] ]
                 'd' , [ 'e' , [], 'f' , [] ] ] ];

这是树中所有元素的简单深度优先累加器：

sub elements {
    my $tree = shift;

    my @elements;
    my @queue = @$tree;
    while (@queue) {
        my $element  = shift @queue;
        my $children = shift @queue;
        push @elements, $element;
        unshift @queue, @$children;
    }

    return @elements;
}

@elements = elements($tree)     # qw(t a b c d e f)

（对于广度优先，请更改行 unshift @queue, @$children 到 push @queue, @$children)

因此，根据您想要在树上执行的操作，最简单的事情可能就是使用 Perl 对数组和数组引用的内置支持。