douruyun8153 2014-05-21 04:17
浏览 89
已采纳

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

I have a situation where I have an array structure that consists of about 6,000 key/value pairs.

The array is in a structure like:

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
    )

From that data source I am trying to massage the output into

A) An array that I can use in later functionality
B) A table display where each row will be one full chain, and each column will be a level deeper. Essentially if you think of page navigation, this is a bread crumb display where each node would be in the next column.

I have been playing with a few approaches here

1) Using the recursive function at this stack overflow question: https://stackoverflow.com/a/2915920/997226, however I have not been able to modify this to work with my data where the parent can be the same. In their example of $tree, the left hand (key) value is always unique.

I understand in their example their key is the child, and the value (right hand side) is the parent, however I still can not get this to work for me as in my data there are multiples of the same item on both the parent side and the child side. (Think complex relationships where an article can be contained within multiple parent categories.

2) I have tried starting to create a "base array" of unique parent elements, and then creating a recursive function to do a search on the "original key value array" but this didn't quite work either.

3) I tried saving the data in a database as I'm pretty familiar with using left/right values for accessing/manipulating data as a nested set, but I'm trying to avoid having to have everything INSERT/SELECT from a database.

4) I tried working with the various PHP Iterators classes as I have used these successfully for working with the file system and building file/directory listings, so I've been playing with RecursiveArrayIterator / ParentIterator/ArrayIterator, but can't seem to figure out the proper syntax to use.

I understand that recursing may not be as efficient as using references for a data set of this size, however it seems like it provides the most flexibility, I just can't seem to get it to iterate recursively correctly.

Beyond, this specific question, I'm also trying to better understand the algorithm nature of programmatic recursion.

The more I read through other people's code examples that are trying to do something similar, but with a different data structure I just become more confused.

If anyone could help point me in the right direction it would be appreciated.

Clarification Notes

  1. There will be multiple levels.
  2. It has been pointed out that the data structure can be thought of as a Directed acyclic graph and that makes complete sense.
  • 写回答

1条回答 默认 最新

  • douji1999 2014-05-21 06:07
    关注

    ** Update #2 - I've redesigned using referencing (not recursion). This requires only a single pass through the data. Every parent or child is added as a top level item to an array ($a in this case) if it does not already exist. The key of this top level item is the name of the parent or child. The value is an array which contains references to its children's top level item. In addition, a second array ($p) is created with only references to the parents in the first array ($a). In a single pass which is very quick, all the relationships are discovered.

    The Code (for update #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>";
            }
    }
    
    ?>
    

    The output (for update #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

    **Update #1 - I've fixed code to show multi-level children (and your new example array structure). To keep it clean, I am only using the key of the resulting array elements to store the name of parent and child. The table output becomes more visually complicated. I've used one row for each parent / child group with the first column for the parent and second column for its children. This is also recursive so that the column containing the children can show its children (if any) in a new table of the same format (easier viewed than explained).

    The output (for update #1):

     Array
    (
        [parentA] => Array
            (
                [child1] => Array
                    (
                        [child4] => Array
                            (
                                [child5] => 
                            )
    
                    )
    
                [child2] => 
            )
    
        [parentB] => Array
            (
                [childC] => 
            )
    
        [parentC] => Array
            (
                [child3] => 
            )
    
    )
    

    enter image description here

    The code (for update #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>";
            }
        }
    
    ?>
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 file converter 转换格式失败 报错 Error marking filters as finished,如何解决?
  • ¥15 ubuntu系统下挂载磁盘上执行./提示权限不够
  • ¥15 Arcgis相交分析无法绘制一个或多个图形
  • ¥15 关于#r语言#的问题:差异分析前数据准备,报错Error in data[, sampleName1] : subscript out of bounds请问怎么解决呀以下是全部代码:
  • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
  • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)
  • ¥15 用前端向数据库插入数据,通过debug发现数据能走到后端,但是放行之后就会提示错误
  • ¥30 3天&7天&&15天&销量如何统计同一行
  • ¥30 帮我写一段可以读取LD2450数据并计算距离的Arduino代码
  • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型