创建多维数组的算法

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（唯一）。 值是parentIDs，即父“节点”的ID。 NULL表示没有parentID（即新数组的第1维）。

现在，我需要创建一个新的多维数组，其中所有子元素都在其父ID下。 （这可能听起来非常令人困惑，对于我的描述能力不足感到抱歉。下面有一个例子，应该可以使事情更清楚）

在“排序”函数或称为此操作的任何其他函数应用后，此示例的新数组如下所示： $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() ) );

我知道所有空数组（array（））可能不是非常干净和优雅的解决方案，但不幸的是这是我需要的方式！

- user367217

---

请创建一个数组树，将数组列表转换为数组树。 - bcosca

实际上和我的问题有一点不同，我的格式也不同。 - user367217

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 现在具有正确的完成数组，如问题所示。

- BudgieInWA

Answer 2

双重循环可以解决问题。这将递归地将所有子元素链接到它们的父元素。

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

- Kendall Hopkins