perl - Perl に n-ary ツリーの実装はありますか?

Question

Perl スクリプトを作成していて、n 分木のデータ構造を使用したいと考えています。

(Perl ライブラリの一部ではなく) ソース コードとして利用できる優れた実装はありますか?

Answer 1

マシューがすでに言ったことに加えて、次のモジュールが適切であるように見えます:

ツリー::Nary
ツリー::単純な
ツリー

Answer 2

perl ライブラリではなく「ソース」にしたい理由がよくわかりませんが、どの CPAN モジュールのソースもダウンロードできます。

私はそれを使用していませんが、Treeはあなたの要件を満たすように見えます。

Answer 3

ツリー構造が必要な目的によっては、事前に構築された実装は必要ない場合があります。Perl はすでに、arrayref の配列を使用してそれらをサポートしています。

たとえば、このツリーの単純な表現

             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 の組み込みサポートを使用するのが最も簡単な場合があります。