用于创建多维数组的算法

I'm using PHP and I need help with a seemingly simple task with an array.

我正在使用PHP,我需要一个看似简单的数组任务的帮助。

This is my example 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'
);

The keys of the array represent the IDs (unique).
The values are the parentIDs, i.e. the ID of the parent "node". NULL means that there is no parentID (i.e. 1st dimension of the new array).

数组的键表示ID(唯一)。值是parentID,即父“节点”的ID。 NULL表示没有parentID(即新数组的第一维)。

Now, I need to create a new, multi-dimensional array that has all the child elements under their parent IDs. (This probably sounds very confusing, sorry for my lack of descriptive abilities. There's an example below, which should make things clearer)

现在,我需要创建一个新的多维数组,其父元素下包含所有子元素。 (这可能听起来很混乱,抱歉我缺乏描述性能力。下面有一个例子,应该让事情更清楚)

Here's what the new array of my example would look like after the "sorting" function, or whatever you call this, was applied:

这是我的示例的新数组在“排序”函数之后的样子,或者你称之为的任何内容,都应用了:

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

I know all the empty array()s are probably not a very clean and elegant solution but unfortunately this is the way I need it to be!

我知道所有空数组()都可能不是一个非常干净和优雅的解决方案,但遗憾的是这就是我需要它的方式!

2 个解决方案

#1

This recursive function will add the given datum to the correct parent, and should be called once for each element in your starting array.

这个递归函数会将给定的数据添加到正确的父级,并且应该为起始数组中的每个元素调用一次。

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;

}

The comments are quite verbose, in the hope that you can understand what is going on. I'd encourage you to do a bit of reading on recursive functions to get your head around it.

评论非常冗长,希望你能理解发生了什么。我鼓励你对递归函数进行一些阅读,以便了解它。

This is how it would be used:

这是如何使用它:

$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 now has the correct finishing array, as indicated in the question.

$ final现在有正确的整理数组,如问题所示。

#2

Two pass foreach does the trick. This will link all child to their parents recursively.

两次传球都可以解决问题。这将递归地将所有孩子与父母联系起来。

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

#1