使树哈希到正确的路径

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;

上面假设末端是没有children的节点。如果你的两端可以有 children，你就有一个尝试。只需将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});

使树哈希到正确的路径

Making tree hash to correct path

tree

recursion

perl