Existe-t-il une implémentation d'arbre n-aire en Perl ?

Question

J'écris un script Perl et j'aimerais utiliser une structure de données arborescente n-aire.

Existe-t-il une bonne implémentation disponible sous forme de code source (plutôt que comme partie d'une bibliothèque Perl) ?

Answer 1

En ajoutant à ce que Matthew a déjà dit, il semble que les modules suivants conviendraient :

Arbre : Nary
Arbre : Simple
Arbre

Answer 2

Je ne comprends pas vraiment pourquoi vous voulez que ce soit une "source" plutôt qu'une bibliothèque Perl, mais vous pouvez télécharger la source de n'importe quel module CPAN.

Je ne l'ai pas utilisé, mais Arbre cherche à combler vos besoins.

Answer 3

En fonction de la raison pour laquelle vous avez besoin d'une arborescence, vous n'aurez peut-être pas besoin d'une implémentation prédéfinie.Perl les prend déjà en charge en utilisant des tableaux de arrayrefs.

Par exemple, une représentation simple de cet arbre

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

pourrait être représenté par le code Perl suivant :

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

Ici, la représentation de l'arbre est sous forme de paires imbriquées :d'abord l'élément (dans ce cas, la lettre), puis une référence de tableau anonyme représentant les enfants de cet élément.Noter que => est juste une virgule sophistiquée en Perl qui vous dispense d'avoir à mettre des guillemets autour du jeton à gauche de la virgule, à condition qu'il s'agisse d'un seul mot.Le code ci-dessus aurait également pu s'écrire ainsi :

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

Voici un simple accumulateur de profondeur d'abord de tous les éléments de l'arborescence :

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)

(Pour la largeur d'abord, changez la ligne unshift @queue, @$children à push @queue, @$children)

Ainsi, en fonction des opérations que vous souhaitez effectuer sur votre arborescence, le plus simple peut être simplement d'utiliser la prise en charge intégrée de Perl pour les tableaux et les références aux tableaux.