in reply to Convert array to tree OR why variable changes arbitrarily

In order to complete your "tree building" I would suggest that you record in your recursion whether (return 1) or not (return 0) you have been able to insert the subtree successfully. If not you add it to the root of the tree. See the following modification of your code, employing poj's far more elegant solution to the reference problem: 

use strict;
use warnings;
use Data::Dumper;

my @arr = (
       'ng1',     ['ng1_1','ng1_2', 'ng1_3', 'ng1_4'],
       'ng2',     ['ng2_1','ng2_2', 'ng2_3', 'ng2_4'],
       'ng3',     ['ng3_1','ng3_2', 'ng3_3', 'ng3_4'],
       'ng1_1',   ['ng1_1_1','ng1_1_2', 'ng1_1_3', 'ng1_1_4'],
       'ng1_1_1', ['ng1_1_1_u1', 'ng1_1_1_u2', 'ng1_1_1_u3'],
       'ng2_1',   ['ng2_1_u1', 'ng2_1_u2', 'ng2_1_u3']
      );

my @tree;
for (my $i=0; $i < @arr; $i+=2){
  next if &buildTree(\@tree, $arr[$i], [ @{$arr[$i+1]} ] );
  push @tree, $arr[$i], [ @{$arr[$i+1]} ];
}
print Dumper \@tree;

sub buildTree{
  my ($tree, $parNg, $subNg) = @_;
  for my $treeElement (@{$tree}){
    if (ref $treeElement eq "ARRAY"){
      return 1 if &buildTree($treeElement, $parNg, $subNg);
    }else{
      if ($treeElement eq $parNg){
    my ($index) = grep { $tree->[$_] eq $treeElement } 0..scalar(@$tre
+e)-1;
    splice @{$tree}, $index + 1, 0, $subNg;
    return 1;
      }
    }
  }
  return 0;
}

[download]

Be aware that this only works when in your initial @arr structure, the higher order nodes appear before the lower order nodes if you understand what I mean. E.g. if n1_1 would appear before n1, you are in trouble.

UPDATE: I would also add a counter $index to the loop in sub buildTree to avoid the grep but that is more a matter of taste I guess.

Replies are listed 'Best First'.
Re^2: Convert array to tree OR why variable changes arbitrarily
by Anonymous Monk on May 31, 2013 at 00:52 UTC
    Thank you, this is elegant solution (a little bit complicated for late night but working :)). How did you mean keeping counter for $index? And also, I am aware that this will work only if @arr is "sorted", I will try to improve algorithm and if I lost then I will ask again :) Thank you.
[reply]

      Basically, you would be counting the $treeElements while iterating over them, so you have the correct $index always at hand. Looks a bit redundant, but I prefer it over grep. 

      sub buildTree{
  my ($tree, $parNg, $subNg) = @_;
  my $index = 0;
  for my $treeElement (@{$tree}){
    if (ref $treeElement eq "ARRAY"){
      return 1 if &buildTree($treeElement, $parNg, $subNg);
    } else {
      if ($treeElement eq $parNg){
    splice @{$tree}, $index + 1, 0, $subNg;
    return 1;
      }
    }
    $index++;
  }
  return 0;
}

      [download]
[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom