Existe-t-il une implémentation d'arborescence n-aire dans 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 en tant que code source (plutôt que comme partie d'une bibliothèque Perl)?

Answer 1

Ajoutant à ce que Matthieu a déjà dit, il semble que les modules suivants seraient appropriés:

Tree::Nary
Tree::Simple
Tree

Answer 2

Je ne comprends pas vraiment pourquoi vous voulez que ce soit "source" plutôt que comme une bibliothèque perl, mais vous pouvez télécharger la source pour n'importe quel module CPAN. Je ne l'ai pas utilisé, mais Tree cherche à combler vos besoins.

Answer 3

Selon ce que vous avez besoin d'une structure arborescente pour, vous ne pourriez pas besoin toute implémentation pré-construite. Perl les supporte déjà en utilisant des tableaux de arrayrefs.

Par exemple, une simple représentation 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 paires comme imbriqués: d'abord l'élément (dans ce cas, la lettre), puis une référence tableau anonyme représentant les enfants de cet élément. Notez que => est juste une virgule fantaisie 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 été écrit ainsi:

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

est ici d'un simple accumulateur première profondeur de tous les éléments de l'arbre:

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 en largeur d'abord, modifiez la ligne unshift @queue, @$children-push @queue, @$children Ainsi, en fonction des opérations que vous souhaitez effectuer sur votre arborescence, la plus simple consiste peut-être à utiliser la prise en charge intégrée de Perl pour les tableaux et les références de tableau.