CODEWITHSUNDEEP
perlrecursiontree
Mạch Điện Tử
Mạch Điện Tử

Reputation: 25

Making tree hash to correct path

I have a hash variable as a tree:

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

I want to convert this tree to correct paths like this:

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

I have tried some recursive code but alway get wrong path. Help me please !

Upvotes: 0

Views: 114

Answers (1)

ikegami
ikegami

Reputation: 386361

The data structure is wholly too complicated. Hashes are being used as arrays, and it would be easier if the id wasn't used as the key. It would be better if a node looked like this:

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

The structure would become

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

You need the id of all ancestors so we pass a long a list of the ancestors as the parameters.

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;

The above assumes the ends are the nodes with no children. If your ends can have children, you have a trie. Simply add end => 1 to the end nodes and use the following as the core of the visitor:

      if (@$children) {
         __SUB__->(@_, $_) for @$children;
      }

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

With your format, it's trickier (and more expensive).

  • $node->{id} is replaced with (keys(%$node))[0].
  • $node->{children} is replaced with $node->{$id}{next}.
  • $node->{end} is replaced with $node->{$id}{end}.
  • for my $child (@$children) is replaced with 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});

Upvotes: 1

Related Questions