將平面數據結構轉換爲樹

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