logo标签列表

将一个PHP键值对数组转换为分层嵌套树形结构

phparraysalgorithmrecursioniterator
3
我有一个情况，我有一个包含约6,000个键/值对的数组结构。
该数组的结构如下：
Array
(
[0] => Array
    (
        [parent] => parentA
        [name] => child1
    )

[1] => Array
    (
        [parent] => parentB
        [name] => childC
    )

[2] => Array
    (
        [parent] => parentA
        [name] => child2
    )

[3] => Array
    (
        [parent] => parentC
        [name] => child3
    )
[4] => Array
    (
        [parent] => child1
        [name] => child4
    )

[5] => Array
    (
        [parent] => child4
        [name] => child5
    )

从这个数据源中，我正在尝试将输出转换为：
A) 一个数组，我可以在后续功能中使用
B) 表格显示，每一行都是一个完整的链，每一列都会深入一层。如果你想到页面导航，这就是一个面包屑导航显示，其中每个节点都在下一列中。
我一直在尝试几种方法：
1）使用这个stackoverflow问题中的递归函数： https://dev59.com/enE85IYBdhLWcg3wKwKD#2915920，但是我没有能够修改它以使其适用于我的数据，其中父项可以相同。在他们的$tree示例中，左侧（键）值始终是唯一的。
我理解在他们的示例中，他们的键是子项，而值（右侧）是父项，但是对于我的数据，我仍然无法让它适用，因为在父项和子项两侧都有多个相同的项目。（想想复杂的关系，其中一篇文章可以包含在多个父类别中。）
2) 我已经尝试创建一个“基础数组”来存储唯一的父元素，然后创建一个递归函数来搜索“原始键值数组”，但这也没有完全成功。
3) 我尝试将数据保存在数据库中，因为我非常熟悉使用左/右值来访问/操作作为嵌套集的数据，但我想避免必须从数据库中进行所有的INSERT/SELECT。
4) 我尝试使用各种PHP迭代器类，因为我已经成功地用它们来处理文件系统和构建文件/目录列表，所以我一直在玩RecursiveArrayIterator / ParentIterator/ArrayIterator，但似乎无法找到正确的语法。
我知道对于这么大的数据集，递归可能不如使用引用高效，但它似乎提供了最大的灵活性，只是我无法正确地进行递归迭代。
除了这个具体问题之外，我还想更好地理解编程递归的算法性质。
我越是阅读其他人的代码示例，他们试图使用不同的数据结构来做类似的事情，我就越感到困惑。
如果有人能帮我指明方向，我会很感激。 澄清说明
  1. 将会有多个层次。
  2. 已经指出，数据结构可以被视为有向无环图，这是完全有道理的。
你的意图并不是很清楚。A）你想要使用什么类型的数组？B）所以你有一个有向无环图，有一个单一源和潜在的多个汇点，并且你想要提取从源到汇点的所有路径并显示它们？ - Vincent van der Weele
Heuster，是的，谢谢你，你对有向图和想要可视化所有相关路径的理解是正确的。 - blaine
1个回答
1

** 更新 #2 - 我使用引用（而不是递归）进行了重新设计。这仅需要一次通过数据。如果父项或子项不存在，则将其添加为顶级项目到一个数组中（在本例中为 $a）。此顶级项的键是父项或子项的名称。该值是一个包含对其子项顶级项引用的数组。此外，第二个数组（$p）仅创建有对第一个数组（$a）中父项的引用。在非常快的单次传递中，发现所有关系。

代码（更新＃2）：

<?php
$tree_base = array(
    array('parent' => 'parentA','name' => 'child1'),
    array('parent' => 'parentB','name' => 'childC'),
    array('parent' => 'parentA','name' => 'child2'),
    array('parent' => 'parentC','name' => 'child3'),
    array('parent' => 'child1','name' => 'child4'),
    array( 'parent' => 'child4', 'name' => 'child5'),
    array( 'parent' => 'DataSelect', 'name' => 'getBaseUri'),
    array( 'parent' => 'getBaseUri', 'name' => 'getKbBaseURI')
    );

    $tree = parseTree($tree_base);
    echo '<pre>'.print_r($tree, TRUE).'</pre>';
    showresults($tree);

function parseTree($tree){
    $a = array();
    foreach ($tree as $item){
        if (!isset($a[$item['name']])){
            // add child to array of all elements
            $a[$item['name']] = array();
        }
        if (!isset($a[$item['parent']])){
            // add parent to array of all elements
            $a[$item['parent']] = array();

            // add reference to master list of parents
            $p[$item['parent']] = &$a[$item['parent']];
        }
        if (!isset($a[$item['parent']][$item['name']])){
            // add reference to child for this parent
            $a[$item['parent']][$item['name']] = &$a[$item['name']];
        }   
    }
    return $p;
}

function showresults($tree, &$loop = array()){
        if (is_array($tree) & count($tree) > 0){       
                echo "<table>";
                echo "<tr>";
                foreach ($tree as $key => $children){
                    // prevent endless recursion
                    if (!array_key_exists($key, $loop)){
                        $loop[$key] = null;
                        echo "<tr>";
                        echo "<td style='border:1px solid'>";
                        echo $key;
                        echo "<td style='border:1px solid'>";
                        showresults($children, $loop);
                        echo "</td>";
                        echo "</td>";
                        echo "</tr>";
                    }
                }
                echo "</tr>";
                echo "</table>";
        }
}

?>

更新 #2 的输出：
Array
(
    [parentA] => Array
        (
            [child1] => Array
                (
                    [child4] => Array
                        (
                            [child5] => Array
                                (
                                )

                        )

                )

            [child2] => Array
                (
                )

        )

    [parentB] => Array
        (
            [childC] => Array
                (
                )

        )

    [parentC] => Array
        (
            [child3] => Array
                (
                )

        )

    [DataSelect] => Array
        (
            [getBaseUri] => Array
                (
                    [getKbBaseURI] => Array
                        (
                        )

                )

        )

)

enter image description here

**更新#1 - 我已经修复了代码以显示多级子项（和您的新示例数组结构）。为了保持干净，我只使用生成的数组元素的键来存储父项和子项的名称。表格输出变得更加复杂。我为每个父/子组使用一行，并将第一列用于父项，第二列用于其子项。这也是递归的，因此包含子项的列可以在同一格式的新表格中显示其子项（如果有的话），这比解释更容易查看。

输出结果（更新＃1）：

 Array
(
    [parentA] => Array
        (
            [child1] => Array
                (
                    [child4] => Array
                        (
                            [child5] => 
                        )

                )

            [child2] => 
        )

    [parentB] => Array
        (
            [childC] => 
        )

    [parentC] => Array
        (
            [child3] => 
        )

)

enter image description here

更新 #1 的代码如下:
<?php
$array = array(
    array('parent' => 'parentA',
                    'name' => 'child1'),
    array('parent' => 'parentB',
                    'name' => 'childC'),
    array('parent' => 'parentA',
                    'name' => 'child2'),
    array('parent' => 'parentC',
                    'name' => 'child3'),
    array('parent' => 'child1',
                    'name' => 'child4'),
    array( 'parent' => 'child4',
                    'name' => 'child5')
    );

    // parse array into a hierarchical tree structure
    $tree = parseTree($array);

    // Show results
    echo '<pre>';
    print_r($tree);
    echo '</pre>';  
    echo "<br>Table Format:";

    showresults($tree);

    function parseTree(& $tree, $root = null) {
        $return = null;
        // Traverse the tree and search for children of current parent
      foreach ($tree as $key=> $item){
      // A child is found
            if ($item['parent'] == $root){
                // append child into array of children & recurse for children of children
                $return[$item['name']] = parseTree($tree, $item['name']);
                // delete child so won't include again
                unset ($tree[$key]);
            }
            elseif ($root == null) {
                // top level parent - add to array 
                $return[$item['parent']] = parseTree($tree, $item['parent']);
                // delete child so won't include again
                unset ($tree[$key]);
            }
        }
        return $return;
    }

    function showresults($tree){

        if (is_array($tree)){       
            echo "<table>";
            echo "<tr>";

            foreach ($tree as $key => $children){
                echo "<tr>";

                echo "<td style='border:1px solid'>";
                echo $key;

                echo "<td style='border:1px solid'>";
                showresults($children, true);
                echo "</td>";

                echo "</td>";

                echo "</tr>";
            }

            echo "</tr>";
            echo "</table>";
        }
    }

?>
mseifert，感谢您的代码示例。但是当我尝试运行它时，它只显示一个父节点及其相关的子节点。源数据将具有多个级别的子节点，都在该父节点（键/值）结构内。因此，我希望能够得到一些Parent->Child->Child of Child->Child of Child of Child类型的结果，但我在示例1中没有看到这样的结果。如果我表述不清楚，那么我可能是错过了什么非常基本的东西，请见谅。 - blaine
我已更新以上代码，以展示子孙级递归处理。希望这有所帮助。 - mseifert
我一直在尝试您的示例，当我使用$array示例运行它时，它看起来完美。但是，当我在包含6,000个元素的数组上运行它时，它无法运行。我将其调整为仅使用几百个元素运行，它可以运行，但是打印出来的数组和表格并不像预期的那样。然而，这可能是因为当我将其限制为400时，没有足够的数据来拥有父/子关系。所以我的问题是1）如果有一个键值，且没有其他同名的父级，它应该创建一个顶层条目，对吗？然后我的第二个问题是，我应该增加服务器大小并重试吗？ - blaine
我在想，是否将一个名为$root_parent的变量传递进去会有意义，它将成为我想要查看的树的根节点？因此，不必尝试跟踪整个树/图，而只需至少关注单个起始点即可。 - blaine
我不确定“无法运行”和“增加服务器大小”确切的含义。有6000个元素，可能会发生数百万次递归，这可能会很慢。您可以在其中添加调试echo命令以查看进度。如果您想向我提供文件（发送链接或从我的网站-列在我的个人资料中-向我发送电子邮件），我将很乐意使用您的6000个元素进行测试。关于$root_parent，任何限制递归的方法都有助于提高性能。您可以组合一组较小的元素，以确保它提供了您想要的内容。 - mseifert
我已经更新了代码（更新＃2），使用引用而不是递归，这允许对数据进行单次遍历 - 这非常快。 - mseifert
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接