Geek Answers Handbook

Algorithm for creating a multidimensional array

I am using PHP and I need help with a simple array task.

This is my sample array:

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

Array keys represent an ID (unique).
The values ​​are parentIDs , that is, the identifier of the parent "node". NULLmeans there is no parent identifier (i.e. the first dimension of the new array).

Now I need to create a new multidimensional array that has all the children under their parent identifiers. (Perhaps this sounds very confusing, sorry for the lack of descriptive abilities. Here is an example below that should make everything clearer)

, :

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

, () s, , , , , !

+5
2

.

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 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 , .

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

More articles:


All Articles