Thuật toán để tạo mảng đa chiều

Question

Tôi đang sử dụng PHP và tôi cần trợ giúp với nhiệm vụ dường như đơn giản với một mảng.

Đây là ví dụ mảng của tôi:

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

Các phím của mảng đại diện cho ID (duy nhất).
Các giá trị là parentID, tức là ID của nút "mẹ". NULL có nghĩa là không có parentID (tức là thứ nguyên thứ nhất của mảng mới).

Bây giờ, tôi cần tạo một mảng đa chiều mới có tất cả các phần tử con theo ID cha mẹ của chúng. (Điều này nghe có vẻ rất khó hiểu, xin lỗi vì thiếu khả năng mô tả của tôi. Có một ví dụ bên dưới, điều này sẽ làm cho mọi việc rõ ràng hơn)

Đây là mảng mới của ví dụ sau khi sắp xếp "" chức năng bạn gọi là này, đã được áp dụng:

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

Tôi biết tất cả các mảng trống() có lẽ không phải là giải pháp rất sạch sẽ và thanh lịch nhưng tiếc là đây là cách tôi cần!

Answer 1

Hàm đệ quy này sẽ thêm dữ liệu đã cho cho cha mẹ chính xác và phải được gọi một lần cho mỗi phần tử trong mảng bắt đầu của bạn.

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; 

} 

Nhận xét khá dài dòng, với hy vọng bạn có thể hiểu điều gì đang diễn ra. Tôi khuyến khích bạn đọc một chút về các hàm đệ quy để thu hút đầu xung quanh nó.

Đây là cách nó sẽ được sử dụng:

$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 hiện nay có các mảng kết thúc đúng, như được chỉ ra trong câu hỏi.

Answer 2

Hai lần bỏ qua thực hiện thủ thuật. Điều này sẽ liên kết tất cả trẻ em với cha mẹ đệ quy.

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