使用id和parent_id结构递归ordenate数组

Question

所以,我得到了这个数组(从数据库中收集数据):

Array
(
    [0] => Array
        (
            [id] => 1
            [parent_id] => 0
        )

    [1] => Array
        (
            [id] => 2
            [parent_id] => 0
        )

    [2] => Array
        (
            [id] => 3
            [parent_id] => 2
        )

    [3] => Array
        (
            [id] => 4
            [parent_id] => 2
        )

    [4] => Array
        (
            [id] => 5
            [parent_id] => 4
        )
)

我正在尝试创建和排序这样的数组:

Array
(
    [1] => Array
        (
            [parent_id] => 0
        )

    [2] => Array
        (
            [parent_id] => 0
            [children] => Array
            (
                [3] => Array
                    (
                        [parent_id] => 2
                    )

                [4] => Array
                    (
                        [parent_id] => 2
                        [children] => Array
                        (
                            [5] => Array
                                (
                                    [parent_id] => 4
                                )
                        )
                    )
            )
        )
)

我尝试使用以下代码:

function placeInParent(&$newList, $item)
{
    if (isset($newList[$item['parent_id']]))
    {
        $newList[$item['parent_id']]['children'][$item['id']] = $item;
        return true;
    }

    foreach ($newList as $newItem)
    {
        if (isset($newItem['children']))
        {
            if (placeInParent($newItem['children'], $item))
            {
                return true;
            }
        }
    }
    return false;
}

$oldList = (first array above)

$newList = array();

foreach ($oldList as $item)
{
    if ($item['parent_id'] == 0)
    {
        $newList[$item['id']] = $item;
    }
    else
    {
        placeInParent($newList, $item);
    }
}

但问题是我只得到阵列的前2级!最后一个丢失..我的有序数组如下:

Array
(
    [1] => Array
        (
            [parent_id] => 0
        )

    [2] => Array
        (
            [parent_id] => 0
            [children] => Array
                (
                    [3] => Array
                        (
                            [parent_id] => 2
                        )

                    [4] => Array
                        (
                            [parent_id] => 2
                        )
                )
        )
)

我无法得到我搞砸的地方:\帮助？

Answer 1

你可以在没有递归的情况下借助引用树内节点的索引来做到这一点:

$arr = array(
    array('id'=>1, 'parent_id'=>0),
    array('id'=>2, 'parent_id'=>0),
    array('id'=>3, 'parent_id'=>2),
    array('id'=>4, 'parent_id'=>2),
    array('id'=>5, 'parent_id'=>4),
);

// array to build the final hierarchy
$tree = array(
    'children' => array(),
    'path'     => array()
);

// index array that references the inserted nodes
$index = array(0=>&$tree);

foreach ($arr as $key => $val) {
    // pick the parent node inside the tree by using the index
    $parent = &$index[$val['parent_id']];
    // append node to be inserted to the children array
    $node = array(
        'parent_id' => $val['parent_id'],
        'path'      => $parent['path'] + array($val['id'])
    );
    $parent['children'][$val['id']] = $node;
    // insert/update reference to recently inserted node inside the tree
    $index[$val['id']] = &$parent['children'][$val['id']];
}

您正在寻找的最终阵列是$tree['children'].