將一系列父子關係轉換成樹？

我非常卡住。我想我需要寫一個遞歸方法，但是我不知道如何......！將一系列父子關係轉換成樹？

我想將一個父子關係數組轉換爲一個分層樹，我稍後會向用戶顯示。

這是輸入數據的一個例子，我可能有：

$input = array(
    array(
      'itemGroupID' => 1, 
      'childItemGroupID' => 2 
     ), 
    array(
      'itemGroupID' => 1, 
      'childItemGroupID' => 3 
     ), 
    array(
      'itemGroupID' => 1, 
      'childItemGroupID' => 4 
     ), 
    array(
      'itemGroupID' => 1, 
      'childItemGroupID' => 212 
     ), 
    array(
      'itemGroupID' => 1, 
      'childItemGroupID' => 339 
     ), 
    array(
      'itemGroupID' => 1, 
      'childItemGroupID' => 336 
     ), 
    array(
      'itemGroupID' => 1, 
      'childItemGroupID' => 6 
     ), 
    array(
      'itemGroupID' => 1, 
      'childItemGroupID' => 5 
     ), 
    array(
      'itemGroupID' => 6, 
      'childItemGroupID' => 8 
     ), 
    array(
      'itemGroupID' => 6, 
      'childItemGroupID' => 9 
     ), 
    array(
      'itemGroupID' => 6, 
      'childItemGroupID' => 10 
     ), 
    array(
      'itemGroupID' => 6, 
      'childItemGroupID' => 11 
     ), 
    array(
      'itemGroupID' => 6, 
      'childItemGroupID' => 12 
     ), 
    array(
      'itemGroupID' => 6, 
      'childItemGroupID' => 13 
     ), 
    array(
      'itemGroupID' => 6, 
      'childItemGroupID' => 74 
     ), 
    array(
      'itemGroupID' => 9, 
      'childItemGroupID' => 15 
     ), 
    array(
      'itemGroupID' => 10, 
      'childItemGroupID' => 16 
     ), 
    array(
      'itemGroupID' => 11, 
      'childItemGroupID' => 17 
     ), 
    array(
      'itemGroupID' => 12, 
      'childItemGroupID' => 18 
     ), 
    array(
      'itemGroupID' => 13, 
      'childItemGroupID' => 19 
     ), 
    array(
      'itemGroupID' => 74, 
      'childItemGroupID' => 75 
     ) 
);

我希望找回數據，如格式：

$output = array(
    array(
     'itemGroupID' => 1, 
     'children' => array(
       array(
        'itemGroupID' => 2     
      ), 
       array(
        'itemGroupID' => 3     
      ), 
       array(
        'itemGroupID' => 4     
      ), 
       array(
        'itemGroupID' => 212     
      ), 
       array(
        'itemGroupID' => 339     
      ), 
       array(
        'itemGroupID' => 336     
      ), 
       array(
        'itemGroupID' => 6, 
        'children' => array(
         array(
          'itemGroupID' => 8     
        ), 
         array(
          'itemGroupID' => 9, 
          'children' => array(
           array(
            'itemGroupID' => 15 
          ) 
         )     
        ), 
         array(
          'itemGroupID' => 10, 
          'children' => array(
           array(
            'itemGroupID' => 16 
          ) 
         )     
        ), 
         array(
          'itemGroupID' => 11, 
          'children' => array(
           array(
            'itemGroupID' => 17 
          ) 
         )     
        ), 
         array(
          'itemGroupID' => 12, 
          'children' => array(
           array(
            'itemGroupID' => 18 
          ) 
         )     
        ), 
         array(
          'itemGroupID' => 13, 
          'children' => array(
           array(
            'itemGroupID' => 19 
          ) 
         )     
        ), 
         array(
          'itemGroupID' => 74, 
          'children' => array(
           array(
            'itemGroupID' => 75 
          ) 
         )     
        )      
       )    
      ), 
       array(
        'itemGroupID' => 5     
      ) 
     ) 
    ) 
);

我設法寫一些代碼，會告訴我是從根開始的。（因爲我擔心如果你從第一個節點遞歸，可能會發現這是從鏈的中間向下...）

順便說一下，我輸出的元素可以用來獲取起始點索引，用於每個分級鏈。

private function _arraySearch($arr, $callback) 
{ 
    foreach ($arr as $key => $item) { 
     if ($callback($item)) { 
      return $key; 
     } 
    } 
    return false; 
} 

private function _findRootsOfItemGroupTree($activeItemGroupChildren) 
{ 
    $searchArray = $activeItemGroupChildren; 
    $roots = array(); 
    foreach ($activeItemGroupChildren as $itemGroupChild) { 
     $parentItemGroupID = $itemGroupChild['itemGroupID']; 

     $found = array_filter($searchArray, function ($element) use ($parentItemGroupID) { 
      return $element['childItemGroupID'] == $parentItemGroupID; 
     }); 

     $rootItemGroupID = $parentItemGroupID; 
     if (count($found) == 0 
      && $this->_arraySearch($roots, 
       function ($element) use ($rootItemGroupID) { 
        return $element['itemGroupID'] == $rootItemGroupID; 
       }) === false) { 

      $roots[] = $itemGroupChild; 
     } 
    } 
    return $roots; 
}

但是，我現在需要使用這些信息來創建一個新的關聯數組。我無法弄清楚如何。（我會在幾分鐘後發佈一些工作..）

想法？

注意：假設這個結構中沒有遞歸循環，即使它們在技術上可能存在。

來源

2012-05-25 olive

你有沒有解決問題了嗎？ – mpratt

我最終寫了自己的解決方案，但我會接受你的作品！ – olive

如果我正確理解你的問題，這應該工作。請注意我如何在函數內部調用orderMe函數使其遞歸。

function orderMe($input, $parentId) 
{ 
    $return = array($parentId => array('itemGroupID' => $parentId)); 
    $childs = array(); 
    foreach ($input as $i) 
    { 
     if ($i['itemGroupID'] == $parentId) 
     { 
      $return[$i['itemGroupID']]['children'][$i['childItemGroupID']] = array('itemGroupID' => $i['childItemGroupID']); 
      $childs[] = $i['childItemGroupID']; 
     } 

     if (in_array($i['childItemGroupID'], $childs)) 
     { 
      $allChilds = orderMe($input, $i['childItemGroupID']); 
      if (!empty($allChilds[$i['childItemGroupID']]['children'])) 
       $return[$i['itemGroupID']]['children'][$i['childItemGroupID']] = $allChilds; 
     } 
    } 

    return $return; 
} 

print_r(orderMe($input, 1));

輸出：

array (
    1 => 
    array (
    'itemGroupID' => 1, 
    'children' => 
    array (
     2 => 
     array (
     'itemGroupID' => 2, 
    ), 
     3 => 
     array (
     'itemGroupID' => 3, 
    ), 
     4 => 
     array (
     'itemGroupID' => 4, 
    ), 
     212 => 
     array (
     'itemGroupID' => 212, 
    ), 
     339 => 
     array (
     'itemGroupID' => 339, 
    ), 
     336 => 
     array (
     'itemGroupID' => 336, 
    ), 
     6 => 
     array (
     6 => 
     array (
      'itemGroupID' => 6, 
      'children' => 
      array (
      8 => 
      array (
       'itemGroupID' => 8, 
      ), 
      9 => 
      array (
       9 => 
       array (
       'itemGroupID' => 9, 
       'children' => 
       array (
        15 => 
        array (
        'itemGroupID' => 15, 
       ), 
       ), 
      ), 
      ), 
      10 => 
      array (
       10 => 
       array (
       'itemGroupID' => 10, 
       'children' => 
       array (
        16 => 
        array (
        'itemGroupID' => 16, 
       ), 
       ), 
      ), 
      ), 
      11 => 
      array (
       11 => 
       array (
       'itemGroupID' => 11, 
       'children' => 
       array (
        17 => 
        array (
        'itemGroupID' => 17, 
       ), 
       ), 
      ), 
      ), 
      12 => 
      array (
       12 => 
       array (
       'itemGroupID' => 12, 
       'children' => 
       array (
        18 => 
        array (
        'itemGroupID' => 18, 
       ), 
       ), 
      ), 
      ), 
      13 => 
      array (
       13 => 
       array (
       'itemGroupID' => 13, 
       'children' => 
       array (
        19 => 
        array (
        'itemGroupID' => 19, 
       ), 
       ), 
      ), 
      ), 
      74 => 
      array (
       74 => 
       array (
       'itemGroupID' => 74, 
       'children' => 
       array (
        75 => 
        array (
        'itemGroupID' => 75, 
       ), 
       ), 
      ), 
      ), 
     ), 
     ), 
    ), 
     5 => 
     array (
     'itemGroupID' => 5, 
    ), 
    ), 
), 
)

來源

2012-05-25 17:06:55 mpratt

將一系列父子關係轉換成樹？

回答

相關問題