PHP构建树，但是数组中有多个父级

我花了好几天的时间寻找答案，并试图自己解决问题，但我做不到。

我有一个PHP数组中的数据，其中键parent_id是一个数组。我发现了如何建造一棵树，但前提是它只有一个父母！但在我的情况下，它有多个父级，并且必须嵌套在每个父级之下。

这里有一个例子：

父母

array( 'id' => 1, 'name' => 'Parent 1', 'parent_id' => array() );

array( 'id' => 2, 'name' => 'Parent 2', 'parent_id' => array() );

儿童

array( 'id' => 3, 'name' => 'Child 1', 'parent_id' => array(1, 2) );

我希望这棵树是这样建的：

array( 'id' => 1, 'name' => 'Parent 1', 'parent_id' => array(), 'children' => array( array( 'id' => 3, 'name' => 'Child 1', 'parent_id' => array(1, 2) ) ), ); array( 'id' => 2, 'name' => 'Parent 2', 'parent_id' => array(), 'children' => array( array( 'id' => 3, 'name' => 'Child 1', 'parent_id' => array(1, 2) ) ), );

你能建议一个可能对我有帮助的工作功能吗？提前谢谢。

已编辑(演示(

@Jeff Lambert是对的。我所做的是循环遍历元素，如果有元素有父元素，我会将其ID添加到新创建的键children中。。这样我就可以随时取回它。

function build_tree(array $elements)
{
    $indexed = array();
    foreach($elements as $element)
    {
        $element = (array) $element;
        $indexed[$element['id']] = $element;
    }
    $elements = $indexed;
    unset($indexed, $element);
    foreach($elements as $id => $element)
    {
        if ( ! empty($element['parent_id']))
        {
            foreach($element['parent_id'] as $parent)
            {
                if (isset($elements[$parent]))
                {
                    $elements[$parent]['children'][] = $element['id'];
                }
            }
        }
    }
    return $elements;
}

然后我只需要创建一个小函数来检索元素的详细信息，比如：

function get_element($id, $return = NULL)
{
    // Check the element inside the array
    if (isset($elements[$id])
    {
        // In case I want to return a single value
        if ($return !== NULL and isset($elements[$id][$return])
        {
            return $elements[$id][$return];
        }
        return $elements[$id];
    }
    return FALSE; // Or NULL, as you wish
}

更新

如果你想/需要嵌套节点(例如，一个父节点可以有一个或多个子节点，同时又是另一个父的子节点(，那么最简单的方法就是为节点指定引用。

我已经拼凑了一个快速演示，它几乎与我最初的方法相同，只是它使用引用而不是按值分配。代码如下：

function buildTree(array $data)
{
    $data = array_column($data, null, 'id');
    //reference to each node in loop
    foreach ($data as &$node) {
        if (!$node['parent_id']) {
            //record has no parents - null or empty array
            continue; //skip
        }
        foreach ($node['parent_id'] as $id) {
            if (!isset($data[$id])) { // make sure parent exists
                throw new RuntimeException(
                    sprintf(
                        'Child id %d is orphaned, no parent %d found',
                        $node['id'], $id
                    )
                );
            }
            if (!isset($data[$id]['children']) {
                $data[$id]['children'] = array();
            }
            $data[$id]['children'][] = &$node; //assign a reference to the child node
        }
    }
    return $data;
}

这里需要双重引用，因为如果不使用foreach ($data as &$node)，$node变量将是原始节点的副本。为副本指定引用对你没有任何好处。事实上，它会产生错误的结果。

同样，如果没有从循环中为&$node分配引用，则不会获得整个树中子节点的完整列表
这不是最容易解释的事情，但最终结果不言自明：使用这里的引用可以在一个函数调用中完整地构建树。

我会这么做。首先，我会使用id作为数组键，这样我就可以更容易地找到每个孩子的父母：

$parents = array_column($parents, null, 'id');

如果您使用的是旧版本的PHP，并且无法升级，这相当于编写：

$indexed = array();
foreach ($parents as $parent) {
    $indexed[$parent['id']] = $parent;
}
$parents = $indexed;

现在对孩子们进行迭代，并将他们分配给他们的父母：

foreach ($children as $child) {
    foreach ($child['parent_id'] as $id) {
        if (!isset($parents[$id]['children']) {
            $parents[$id]['children'] = array();//ensure the children key exists
        }
        $parents[$id]['children'][] = $child;//append child to parent
    }
}

如果$parents和$children是两个独立的数组，或者两个记录都在一个大数组中，这并不重要。

因此，如果父级和子级位于不同的数组中，则函数如下所示：

function buildTree(array $parents, array $children)
{
    $parents = array_column($parents, null, 'id');
    foreach ($children as $child) {
        foreach ($child['parent_id'] as $id) {
            if (!isset($parents[$id])) { // make sure parent exists
                throw new RuntimeException(
                    sprintf(
                        'Child id %d is orphaned, no parent %d found',
                        $child['id'], $id
                    )
                );
            }
            if (!isset($parents[$id]['children']) {
                $parents[$id]['children'] = array();
            }
            $parents[$id]['children'][] = $child;
        }
    }
    return $parents;
}

如果所有数据都在一个数组中，那么函数看起来几乎相同：

function buildTree(array $data)
{
    $data = array_column($data, null, 'id');
    foreach ($data as $node) {
        if (!$node['parent_id']) {
            //record has no parents - null or empty array
            continue; //skip
        }
        foreach ($node['parent_id'] as $id) {
            if (!isset($data[$id])) { // make sure parent exists
                throw new RuntimeException(
                    sprintf(
                        'Child id %d is orphaned, no parent %d found',
                        $node['id'], $id
                    )
                );
            }
            if (!isset($data[$id]['children']) {
                $data[$id]['children'] = array();
            }
            $data[$id]['children'][] = $node;
        }
    }
    return $data;
}

这就是它正确工作的方式。

 $arr = array(
      array('id'=>100, 'parentid'=>0, 'name'=>'a'),
      array('id'=>101, 'parentid'=>100, 'name'=>'a'),
      array('id'=>102, 'parentid'=>101, 'name'=>'a'),
      array('id'=>103, 'parentid'=>101, 'name'=>'a'),
    );
    $new = array();
    foreach ($arr as $a){
        $new[$a['parentid']][] = $a;
    }
    $tree = createTree($new, array($arr[0]));
    print_r($tree);
    function createTree(&$list, $parent){
        $tree = array();
        foreach ($parent as $k=>$l){
            if(isset($list[$l['id']])){
                $l['children'] = createTree($list, $list[$l['id']]);
            }
            $tree[] = $l;
        } 
        return $tree;
    }

使用in_array函数的解决方案：

// $parents and $children are arrays of 'parents' and 'children' items respectively
$tree = [];
foreach ($parents as $p) {
    $treeItem = $p + ['children' => []];
    foreach ($children as $c) {
        if (in_array($p['id'], $c['parent_id']))
            $treeItem['children'][] = $c;
    }
    $tree[] = $treeItem;
}
print_r($tree);

DEMO链接

每个节点可以有多个父节点的树不是树，而是图。表示图的一种方法是通过邻接列表。

事实上，您将每个节点的"子节点"存储在该节点索引中，而您不应该这样做，因为每个节点将与它所连接的其他节点重复相同的次数。每个节点都应该在结构的顶层表示，并包含对它们碰巧连接到的其他节点的引用，在您的情况下是'parent_id'索引。我将分离出节点的实际定义，并在单独的结构中声明每个节点连接到的其他节点。

以下是定义节点的方法：

array(
    0 => array(
        'id'        => 1,
        'name'      => 'Parent 1',
    ),
    1 => array(
        'id'        => 2,
        'name'      => 'Parent 2',
    ),
    2 => array(
        'id'        => 3,
        'name'      => 'Child 1',
    ),
)

然后是一个单独的数组，看起来像这样，用于定义节点之间的连接：

array(
    // These indices match the node indices above, and the values are the list of 
    // node indices each node has a connection to.
    0 => array(2),
    1 => array(2),
    2 => array(0, 1),
)

然后应该很容易找到并实现您可能需要的任何类型的遍历算法。

$data = [
        ['id' => 1, 'parent' => []],
        ['id' => 2, 'parent' => [1]],
        ['id' => 3, 'parent' => [2,4]],
        ['id' => 4, 'parent' => []]
    ];
$result = [];
foreach ($data as $item) {
    if(!count($item['parent'])) {
        makeTree($result, $item, $data);
    }
}
print_r($result);
function makeTree(&$result, $item, $data) {
    $result['children'][$item['id']]['data'] = $item;
    if(haveChildren($item['id'], $data)) {
        foreach(children($item['id'], $data) as $child) {
            makeTree($result['children'][$item['id']], $child, $data);
        }
    }
}
function children($id, $data){
    $result = [];
    foreach($data as $item) {
        if(in_array($id, $item['parent'])) {
            $result[] = $item;
        }
    }
    return $result;
}
function haveChildren($id, $data) {
    foreach($data as $item) {
        if(in_array($id, $item['parent'])) {
            return true;
        }
    }
}

更新

相关内容

最新更新

热门标签：