Есть ли в Perl n-арная реализация дерева?

Question

Я пишу скрипт на Perl и хотел бы использовать n-арную структуру данных дерева.

Есть ли хорошая реализация, доступная как исходный код (а не как часть библиотеки Perl)?

Answer 1

В дополнение к тому, что уже сказал Мэтью, похоже, что подойдут следующие модули:

Дерево :: Nary
Дерево :: Simple
дерево

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 поддержку массивов и ссылок на массивы.