Есть ли в Perl n-арная реализация дерева?
Вопрос
Я пишу скрипт на Perl и хотел бы использовать структуру данных n-ary tree.
Есть ли хорошая реализация, доступная как исходный код (а не как часть библиотеки Perl)?
Решение
В дополнение к тому, что уже сказал Мэтью, похоже, что подойдут следующие модули:
Другие советы
Я не совсем понимаю, почему вы хотите, чтобы это был " источник " а не в виде библиотеки perl, но вы можете скачать исходный код для любого модуля CPAN. Р>
Я не использовал его, но Tree выглядит, чтобы удовлетворить ваши требования.
В зависимости от того, для чего вам нужна древовидная структура, вам может не потребоваться какая-либо предварительно созданная реализация. 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 поддержку массивов и ссылок на массивы.