多次元配列を作成するためのアルゴリズム

Question

私はPHPを使用していますし、配列で一見簡単な作業で助けが必要です。

これは私の例の配列です：

$arr = array(
    0 => NULL, 
    1 => NULL, 
    2 => NULL, 
    3 => NULL, 
    8 => '2', 
    9 => '2', 
    10 => '2', 
    11 => '2', 
    12 => '3', 
    13 => '3', 
    14 => '8', 
    15 => '8', 
    16 => '14', 
    17 => '14', 
    18 => '14' 
); 

配列のキーは、IDが（ユニーク）を表します。
値は親ID、つまり親「ノード」のIDです。 NULLは、parentID（新しい配列の第1次元）が存在しないことを意味します。

ここで、すべての子要素が親IDの下にある新しい多次元配列を作成する必要があります。

私の例の新しい配列は、「並べ替え」機能の後にどのように見えるのでしょうか、それとも何かが何であるかは、ここでは分かりません。これを呼び出す、適用した：

 
$arr = array(
0 => array(), 
1 => array(), 
2 => array(
    8 => array(
     14 => array(
      16 => array(), 
      17 => array(), 
      18 => array() 
), 
     15 => array() 
), 
    9 => array(), 
    10 => array(), 
    11 => array() 
), 
3 => array(
    12 => array(), 
    13 => array() 
) 
); 

私はすべての空の配列（）のは、おそらく非常にきれいでエレガントな解決策ではありませんが、残念ながら、これは私はそれがために必要な方法です知っています！

Answer 1

この再帰関数は、正しい親に与えられた基準を追加して、あなたの出発配列の各要素に対して一度呼び出す必要があります。

function add_branch(&$tree, $datum, $parent) { 

    // First we have the base cases: 
    // If the parent is NULL then we don't need to look for the parent 
    if ($parent == NULL) { 
     $tree[$datum] = array(); 
     return true; 
    } 

    // If the array we've been given is empty, we return false, no parent found in this branch 
    if (! count($tree)) { 
     return false; 
    } 


    // We loop through each element at this level of the tree... 
    foreach($tree as $key => $val) { 

     // If we find the parent datum... 
     if ($key == $parent) { 

      // We add the new array in and we're done. 
      $tree[$key][$datum] = array(); 
      return true; 
     } 

     // Otherwise, check all the child arrays 
     else { 

      // Now we check to see if the parent can be found in the curent branch 
      // If a recursive call found a parent, we're done 
      if (add_branch($tree[$key], $datum, $parent)) { 
       return true; 
      } 
     } 
    } 

    // If none of the recursive calls found the parent, there's no match in this branch 
    return false; 

} 

コメントは、あなたが何が起こっているのかを理解できるように、非常に冗長です。私はあなたの周りにあなたの頭を取得するために再帰的な関数の読書を少し行うことをお勧めしたいと思います。

これは、それが使用される方法です：質問に示されているように

$arr = array(
0 => NULL, 
1 => NULL, 
2 => NULL, 
3 => NULL, 
8 => '2', 
9 => '2', 
10 => '2', 
11 => '2', 
12 => '3', 
13 => '3', 
14 => '8', 
15 => '8', 
16 => '14', 
17 => '14', 
18 => '14' 
); 


$final = array(); 

foreach ($arr as $datum => $parent) { 
    add_branch($final, $datum, $parent); 
} 

$finalは今、正しい仕上げアレイを有します。

Answer 2

2回foreachがトリックを行います。これにより、すべての子が再帰的に親にリンクされます。

//$array is the input 

//The tree starts out as a flat array of the nodes 
$tree = array_combine(
    array_keys($array), 
    array_fill(0, count($array), array()) 
); 

//link children to parents (by reference) 
foreach($tree as $key => &$row) { 
    if(! is_null($array[$key])) { 
     $tree[ $array[$key] ][ $key ] =& $row; 
    } 
} 

//remove non-root nodes 
foreach(array_keys($tree) as $key) { 
    if(! is_null($array[$key])) { 
     unset($tree[ $key ]); 
    } 
}