将平面数据结构转换为树

Question

我有一个散列数组。数组中的每个元素都是分层树中的一个节点，并且具有父代身份的参考数据。我将在树中有成千上万的节点......基本上，一组未知的节点必须转换为JSON（如下所示），以便与http://bl.ocks.org/robschmuecker/7880033

一起使用更新：position_id是异端树中的节点。 placement_id是父级的position_id（邻接参考树）。

更新：下面是完整的AoH Data :: Dumper结果，其中嵌套集和邻接结果来自DBIx::Tree::NestedSet（自定义）的修改版本。

$VAR1 = [ 
      { 
      'lft' => '673', 
      'id' => '109', 
      'date_created' => '2015-08-15', 
      'level' => '7', 
      'user_id' => '13', 
      'placement_id' => '11', 
      'position_id' => '13', 
      'status' => '1', 
      'structure_id' => '1', 
      'rght' => '684' 
      }, 
      { 
      'placement_id' => '13', 
      'position_id' => '22', 
      'status' => '1', 
      'structure_id' => '1', 
      'rght' => '679', 
      'lft' => '674', 
      'date_created' => '2015-08-15', 
      'id' => '116', 
      'level' => '8', 
      'user_id' => '22' 
      }, 
      { 
      'user_id' => '101', 
      'level' => '9', 
      'id' => '200', 
      'date_created' => '2015-08-15', 
      'lft' => '675', 
      'rght' => '676', 
      'structure_id' => '1', 
      'status' => '1', 
      'position_id' => '101', 
      'placement_id' => '22' 
      }, 
      { 
      'date_created' => '2015-08-15', 
      'id' => '201', 
      'level' => '9', 
      'user_id' => '374', 
      'lft' => '677', 
      'structure_id' => '1', 
      'rght' => '678', 
      'placement_id' => '22', 
      'position_id' => '374', 
      'status' => '1' 
      }, 
      { 
      'lft' => '680', 
      'user_id' => '95', 
      'level' => '8', 
      'id' => '117', 
      'date_created' => '2015-08-15', 
      'status' => '1', 
      'position_id' => '95', 
      'placement_id' => '13', 
      'rght' => '681', 
      'structure_id' => '1' 
      } 
     ]; 

这是我们的目标，在这个例子中，我需要结束：

{ 
    "name": "13", 
    "children": [ 
     { 
      "name": "22", 
      "children": [ 
       { 
        "name": "101" 
       }, 
       { 
        "name": "374" 
       } 
      ] 
     }, 
     { 
      "name": "95" 
     } 
    ] 
} 

你还可以看到我想来到这里的格式（减尺寸）： http://bl.ocks.org/robschmuecker/7880033#flare.json

我的失败方法包括循环遍历哈希数组的各种尝试，以创建一个递归哈希散列，然后可以与JSON Perl module一起使用来创建我需要的实际JSON。

Answer 1

my $data = [ 
    { position_id => 123, placement_id => undef }, 
    { position_id => 456, placement_id => 123 }, 
    { position_id => 789, placement_id => 123 }, 
    # ... 
]; 

my $roots; 
{ 
    my %recs_by_name; 
    my %children_by_parent_name; 
    for my $row (@$data) { 
     my $name  = $row->{position_id}; 
     my $parent_name = $row->{placement_id}; 

     my $rec = { 
     name => $name, 
     }; 

     push @{ $children_by_parent_name{$parent_name // 'root'} }, $rec; 
     $recs_by_name{$name} = $rec; 
    } 

    $roots = delete($children_by_parent_name{root}) || []; 

    for my $name (keys(%children_by_parent_name)) { 
     my $children = $children_by_parent_name{$name}; 
     if (my $rec = $recs_by_name{$name}) { 
     $rec->{children} = $children; 
     } else { 
     die("Parent $name doesn't exist.\n"); 
     push @$roots, @$children; 
     } 
    } 
} 

print(Dumper($roots)); 

经过测试。

您似乎有每个节点可用的深度（level）。如果您的数据按增加的深度排序，则可以使用较简单的代码。

Answer 2

虽然是@ikegami谁最终回答了导致解决方案的问题。我相信下面的改编增加了我发现有用的4个重要元素/说明，并且认为阅读这个问题和答案的其他人也会觉得有用。

1-清除从始发的AoH到所产生的HOH的所有键值对。请参阅while循环。

2-一个子节点计数器。

3-包合物和使用encode_json函数的从JSON

4-结果也与一个散列作为第一元件的阵列。新手（像我一样）可能会发现传递给encode_json的显式@ {$ roots} [0]是有帮助的。

起初我在我的问题中有一个类似的解决方案作为UPDATE发布，但被告诫说这是不好的礼节，并被指示发布答案。

@ ikegami的解决方案的核心值得信赖。

sub get_jsonTree { 
    my ($array_of_hashes_ref) = @_; 

    my $roots; 
    my %recs_by_name; 
    my %children_by_parent_name; 
    my %count; 
    for my $row (@$array_of_hashes_ref) { 
     my $name  = $row->{position_id}; 
     my $parent_name = $row->{placement_id}; 

     my $rec = { 
      name => $name, 
     }; 

     ## Added to loop through all key,value pairs and add them to $rec 
     while (my ($key, $value) = each(%$row)) { 
      $rec->{$key} = $value; 
     } 

     ##Added To Count Child Nodes 
     $count{$parent_name} = 0 if (!$count{$parent_name});   
     $rec->{'child_count'} = $count{$parent_name}; 
     $count{$parent_name}++; 

     push @{ $children_by_parent_name{$parent_name // 'root'} }, $rec; 
     $recs_by_name{$name} = $rec; 
    } 

    $roots = delete($children_by_parent_name{root}) || []; 

    for my $name (keys(%children_by_parent_name)) { 
     my $children = $children_by_parent_name{$name}; 
     if (my $rec = $recs_by_name{$name}) { 
      $rec->{children} = $children; 
     } else { 
      $util{'test'} .= "Parent $name doesn't exist.\n<BR>"; 
      push @$roots, @$children; 
     } 
    } 

    use JSON; 
    my $json_str = encode_json(@{$roots}[0]); 

    return $json_str; 
} 

my $array_of_hashes_ref = [ 
    { position_id => 123, placement_id => undef }, 
    { position_id => 456, placement_id => 123 }, 
    { position_id => 789, placement_id => 123 }, 
    # ... 
]; 

my $json_str = &get_jsonTree($array_of_hashes_ref);