다차원 배열을 만들기위한 알고리즘

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를 (고유) 나타낸다.
값은 parentID, 즉 상위 "노드"의 ID입니다. NULL은 parentID가 없음 (즉, 새 배열의 첫 번째 차원)을 의미합니다.

이제 모든 상위 요소가 상위 ID 아래에있는 새로운 다차원 배열을 만들어야합니다. (이것은 아마도 매우 혼란스럽고, 설명 할 능력이 없다는 것에 유감스럽게 생각합니다. 아래에 예가 있습니다. 더 명확하게해야합니다)

"sorting"함수 나 예제와 같은 새로운 배열이 어떻게 생겼는지 이 전화를 적용했다 :

 
$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 ]); 
    } 
}