生成树哈希以正确的路径

Question

我有一个散列变量作为树:

%data = {
'node' => {
'RN:4' => {
'next' => {
'1' => {
'RN:23' => {
'next' => {
'1' => {
'RN:29' => {
'end' => 1
}
},
'2' => {
'RN:32' => {
'next' => {
'1' => {
'RN:30' => {
'end' = 1
}
}
}
}
}
}

我想把这棵树转换成正确的路径，像这样:

1, RN:4 >> RN:23 >> RN:29
2, RN:4 >> RN:23 >> RN:32 >> RN:30

我尝试了一些递归代码，但总是得到错误的路径。请帮帮我!

Answer 1

这个数据结构太复杂了。散列被用作数组，如果不使用id作为键会更容易。如果一个节点看起来像这样会更好:

{
id => ...,
children => [ ... ]
}

结构将变成

[
{
id => 'RN:4',
children => [
{
id => 'RN:23',
children => [
{
id => 'RN:29',
children => []
},
{
id => 'RN:32',
children => [
{
id => 'RN:30',
children => []
}
]
}
]
}
]
}
]

你需要所有祖先的id，所以我们传递一个祖先的长列表作为参数。

use 5.016;
sub print_paths {
my $i = 0;
my $helper = sub {
my $node = $_[-1];
my $children = $node->{children};
if (@$children) {
__SUB__->(@_, $_) for @$children;
} else {
say $i, ", ", join(" >> ", map { $_->{id} } @_);
}   
};
$helper->(@_);
}
print_paths($_) for @$roots;

---

上面假设端点是没有子节点的节点。如果你的父母能生孩子，你就有机会。只需将end => 1添加到终端节点，并使用以下内容作为访问者的核心:

if (@$children) {
__SUB__->(@_, $_) for @$children;
}
if ($node->{end}) {
say $i, ", ", join(" >> ", map { $_->{id} } @_);
}   

---

对于您的格式，它更棘手(也更昂贵)。

• $node->{id}替换为(keys(%$node))[0]
• $node->{children}替换为$node->{$id}{next}。
• $node->{end}被$node->{$id}{end}取代
• for my $child (@$children)被for (my $j=1; my $child = $children->{$j}; ++$j)取代

use 5.016;
sub print_paths {
my $i = 0;
my $helper = sub {
my $node = $_[-1];
my $id = (keys(%$node))[0];
my $children = $node->{$id}{next};
if ($children) {
for (my $j=1; my $child = $children->{$j}; ++$j) {
__SUB__->(@_, $child) for @$children;
}
}
if ($node->{$id}{end}) {
say $i, ", ", join(" >> ", map { (keys(%$node))[0] } @_);
}   
};
$helper->(@_);
}
print_paths($data->{node});