計算項深度從平面陣列僅具有一個父項目ID

我有一個扁平陣列：計算項深度從平面陣列僅具有一個父項目ID

Array 
    (
    [] => Array 
     (
      [id] => 346788 
      [parent_id] => 0 
      [item_title] => 'title Here' 
      [item_description] => 'some text' 
     ) 

    [] => Array 
     (
      [id] => 12346 
      [parent_id] => 0 
      [item_title] => 'title Here' 
      [item_description] => 'some text' 
     ) 

    [] => Array 
     (
      [id] => 56745 
      [parent_id] => 12346 
      [item_title] => 'title Here' 
      [item_description] => 'some text' 
     ) 

    [] => Array 
     (
      [id] => 3564 
      [parent_id] => 12346 
      [item_title] => 'title Here' 
      [item_description] => 'some text' 
     ) 

    [] => Array 
     (
      [id] => 2345234 
      [parent_id] => 56745 
      [item_title] => 'title Here' 
      [item_description] => 'some text' 
     ) 

    [] => Array 
     (
      [id] => 433546 
      [parent_id] => 56745 
      [item_title] => 'title Here' 
      [item_description] => 'some text' 
     ) 
)

具有每個項目的ID作爲鍵/值對，以及父項的ID。首先需要發生的事情是扁平數組需要轉換爲分層數組，同時保留每個數組項的其他所有信息。技巧部分是我需要知道陣列中該項目的深度爲0級別。因此父爲0的第一個孩子將是1，等等等等，並將它存儲在最終陣列中：

function build_tree(array &$elements, $parentId = 0, $depth = 0) { 

    $branch = array(); 

    foreach ($elements as &$element) { 

     if ($element['parent_id'] == $parentId) { 
      $children = build_tree($elements, $element['id'], $depth + 1); 
      if ($children) { 
       $element['children'] = $children; 
      } 
      $branch[$element['id']] = $element; 
      $branch[$element['id']]['depth'] = $depth; 
      unset($element); 
     } 
    } 
    return $branch; 
}

第二，我還需要一個額外的功能，可從原來的扁平陣列計算的深度：

function calculate_depth($item_id, array $array) { 

    return $item_depth; 
}

來源

2016-02-10 dpegasusm

爲什麼不從build_tree（）獲得深度？ – Yurich

@Yurich我正在修改別人的軟件，並且更容易將它構建爲兩部分，然後重新構建整個事物以利用新的樹結構。 – dpegasusm

我你沒有訪問樹，你需要什麼無論如何都會涉及到陣列的一個完整的掃描，所以我會用一個HashMap：

$map = array(); 
foreach ($elements as $e) 
    $map[$e['itemID']] = array(
    'parent' => $e['parentID'], 
    'depth' => null 
);

因此，要獲得一個深度你會掃描這個父母現在圖，這需要一定的時間成正比的深度：

function depth(&$map, $id) { 
    $depth = 0; 
    $the_id = $id; 
    while ($map[$id]['parent']) { 
     if ($map[$id]['depth'] !== null) { 
     $depth += $map[$id]['depth']; 
     break; 
     } 
     $id = $map[$id]['parent']; 
     $depth++; 
    } 
    $map[$the_id]['depth'] = $depth; 
    return $depth; 
}

在上述一加入少量的緩存機制的代碼，以使所有的深度的計算仍然會採取線性時間。

來源

2016-02-10 22:35:56 Octane

計算項深度從平面陣列僅具有一個父項目ID

回答

相關問題