Алгоритм создания многомерного массива

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

Ключи массива представляют собой идентификаторы (уникальные).
Значения: parentIDs , то есть идентификатор родительского "узла".NULL означает, что нет parentID (т.е. 1-го измерения нового массива).

Теперь мне нужно создать новый многомерный массив, в котором все дочерние элементы находятся под родительскими идентификаторами.(Возможно, это звучит очень запутанно, извините за отсутствие описательных способностей. Ниже приведен пример, который должен прояснить ситуацию)

Вот как будет выглядеть новый массив моего примера после функции «сортировки»,или как вы это называете, было применено:

$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

Два прохода 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 ] );
    }
}