Esiste un'implementazione dell'albero n-ario in Perl?

Question

Sto scrivendo uno script Perl e vorrei utilizzare una struttura dati ad albero n-ario.

Esiste una buona implementazione disponibile come codice sorgente (piuttosto che come parte di una libreria Perl)?

Answer 1

In aggiunta a quanto già detto da Matthew, sembra che i seguenti moduli sarebbero adatti:

Albero::Nary
Albero::Semplice
Albero

Answer 2

Non capisco davvero perché vuoi che sia "sorgente" piuttosto che come libreria Perl, ma puoi scaricare il sorgente per qualsiasi modulo CPAN.

Non l'ho usato, ma Albero sembra soddisfare le tue esigenze.

Answer 3

A seconda dello scopo per cui hai bisogno di una struttura ad albero, potresti non aver bisogno di alcuna implementazione predefinita.Perl li supporta già utilizzando array di arrayrefs.

Ad esempio, una semplice rappresentazione di questo albero

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

potrebbe essere rappresentato dal seguente codice Perl:

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

Qui, la rappresentazione dell'albero è come coppie nidificate:prima l'elemento (in questo caso, la lettera), poi un riferimento all'array anonimo che rappresenta i figli di quell'elemento.Notare che => è solo una virgola elegante in Perl che ti esonera dal dover mettere le virgolette attorno al token a sinistra della virgola, a condizione che sia una singola parola.Il codice di cui sopra potrebbe anche essere stato scritto così:

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

Ecco un semplice accumulatore di profondità di tutti gli elementi nell'albero:

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)

(Prima per l'ampiezza, cambia la riga unshift @queue, @$children A push @queue, @$children)

Quindi, a seconda delle operazioni che desideri eseguire sul tuo albero, la cosa più semplice potrebbe essere semplicemente quella di utilizzare il supporto integrato di Perl per gli array e i riferimenti agli array.