将平面数据结构转换为树

Question

我有一个哈希数组。数组中的每个元素都是层次结构树中的一个节点，并且具有父元素的引用数据。我将在树中有成千上万的节点……实际上，必须将一组未知的节点转换为JSON(如下所示)以使用http://bl.ocks.org/robschmuecker/7880033

UPDATE: position_id是异端树中的一个节点。Placement_id是父节点的position_id(邻接引用树)。

更新:这里是完整的AoH数据::转储结果与嵌套集和邻接结果从一个修改版本的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'
          }
        ];

THIS IS THE GOAL，对于这个例子，我需要以:

结尾

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

你也可以看到我试图在这里到达的格式(减去大小):http://bl.ocks.org/robschmuecker/7880033 flare.json

我失败的方法包括各种遍历哈希数组的尝试，以创建哈希的递归哈希，然后可以与JSON Perl模块一起使用，以创建我需要的实际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的所有键、值对的添加。

2-子节点计数器。

3-包含和使用JSON中的encode_json函数

4-结果也是一个以Hash作为第一个元素的Array。新手(像我一样)可能会发现显式的@{$roots}[0]传递给encode_json很有帮助。

起初，我在我的问题中发布了一个类似的改编解决方案作为更新，但被告诫说这是不礼貌的，并指示发布一个答案。

@ikegami’s是解决方案的核心。

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);