将一系列父子关系转换为树形结构？

Question

我非常困惑。我认为我需要编写一个递归方法，但是我无法弄清楚如何做...

我正在尝试将一个父子关系的数组转换为分层树形结构，然后再向用户显示。

以下是我可能拥有的输入数据示例：

$input = array(
    array(
            'itemGroupID' => 1,
            'childItemGroupID' => 2
        ),
    array(
            'itemGroupID' => 1,
            'childItemGroupID' => 3
        ),
    array(
            'itemGroupID' => 1,
            'childItemGroupID' => 4
        ),
    array(
            'itemGroupID' => 1,
            'childItemGroupID' => 212
        ),
    array(
            'itemGroupID' => 1,
            'childItemGroupID' => 339
        ),
    array(
            'itemGroupID' => 1,
            'childItemGroupID' => 336
        ),
    array(
            'itemGroupID' => 1,
            'childItemGroupID' => 6
        ),
    array(
            'itemGroupID' => 1,
            'childItemGroupID' => 5
        ),
    array(
            'itemGroupID' => 6,
            'childItemGroupID' => 8
        ),
    array(
            'itemGroupID' => 6,
            'childItemGroupID' => 9
        ),
    array(
            'itemGroupID' => 6,
            'childItemGroupID' => 10
        ),
    array(
            'itemGroupID' => 6,
            'childItemGroupID' => 11
        ),
    array(
            'itemGroupID' => 6,
            'childItemGroupID' => 12
        ),
    array(
            'itemGroupID' => 6,
            'childItemGroupID' => 13
        ),
    array(
            'itemGroupID' => 6,
            'childItemGroupID' => 74
        ),
    array(
            'itemGroupID' => 9,
            'childItemGroupID' => 15
        ),
    array(
            'itemGroupID' => 10,
            'childItemGroupID' => 16
        ),
    array(
            'itemGroupID' => 11,
            'childItemGroupID' => 17
        ),
    array(
            'itemGroupID' => 12,
            'childItemGroupID' => 18
        ),
    array(
            'itemGroupID' => 13,
            'childItemGroupID' => 19
        ),
    array(
            'itemGroupID' => 74,
            'childItemGroupID' => 75
        )
 );

我希望以如下格式获取数据：

$output = array(
    array(
        'itemGroupID' => 1,
        'children' => array(
              array(
                  'itemGroupID' => 2                   
              ),
              array(
                  'itemGroupID' => 3                   
              ),
              array(
                  'itemGroupID' => 4                   
              ),
              array(
                  'itemGroupID' => 212                   
              ),
              array(
                  'itemGroupID' => 339                   
              ),
              array(
                  'itemGroupID' => 336                  
              ),
              array(
                  'itemGroupID' => 6,
                  'children' => array(
                      array(
                          'itemGroupID' => 8                  
                      ),
                      array(
                          'itemGroupID' => 9,
                          'children' => array(
                              array(
                                  'itemGroupID' => 15
                              )   
                          )                 
                      ), 
                      array(
                          'itemGroupID' => 10,
                          'children' => array(
                              array(
                                  'itemGroupID' => 16
                              )   
                          )                  
                      ), 
                      array(
                          'itemGroupID' => 11,
                          'children' => array(
                              array(
                                  'itemGroupID' => 17
                              )   
                          )                   
                      ), 
                      array(
                          'itemGroupID' => 12,
                          'children' => array(
                              array(
                                  'itemGroupID' => 18
                              )   
                          )                   
                      ), 
                      array(
                          'itemGroupID' => 13,
                          'children' => array(
                              array(
                                  'itemGroupID' => 19
                              )   
                          )                   
                      ), 
                      array(
                          'itemGroupID' => 74,
                          'children' => array(
                              array(
                                  'itemGroupID' => 75
                              )   
                          )                   
                      )                    
                  )               
              ),
              array(
                  'itemGroupID' => 5                   
              )
         )
    )
);

我成功地编写了一些代码，可以告诉我应该从哪个根节点开始。 (因为我担心如果你从第一个节点开始递归，可能会发现这已经是链条中间部分了...)

顺便说一下，我输出的元素可用于获取每个分层链的起始索引。

private function _arraySearch($arr, $callback)
{
    foreach ($arr as $key => $item) {
        if ($callback($item)) {
            return $key;
        }
    }
    return false;
}

private function _findRootsOfItemGroupTree($activeItemGroupChildren)
{
    $searchArray = $activeItemGroupChildren;
    $roots = array();
    foreach ($activeItemGroupChildren as $itemGroupChild) {
        $parentItemGroupID = $itemGroupChild['itemGroupID'];

        $found = array_filter($searchArray, function ($element) use ($parentItemGroupID) {
            return $element['childItemGroupID'] == $parentItemGroupID;
        });

        $rootItemGroupID = $parentItemGroupID;
        if (count($found) == 0
            && $this->_arraySearch($roots,
                function ($element) use ($rootItemGroupID) {
                    return $element['itemGroupID'] == $rootItemGroupID;
                }) === false) {

            $roots[] = $itemGroupChild;
        }
    }
    return $roots;
}

然而，我现在需要使用这些信息来创建一个新的关联数组。但我不知道该怎么做。(我将在几分钟内发布一些操作..)

有什么想法吗？

注意：虽然可能存在递归循环，但假设此结构中没有递归循环。

- olive

---

其实最后我自己写了一个解决方案，但是你的也能用，所以我会接受你的！ - undefined

Answer 1

如果我正确理解你的问题，这应该可以解决。 注意我在函数内部调用orderMe函数来使其递归。

function orderMe($input, $parentId)
{
    $return = array($parentId => array('itemGroupID' => $parentId));
    $childs = array();
    foreach ($input as $i)
    {
        if ($i['itemGroupID'] == $parentId)
        {
            $return[$i['itemGroupID']]['children'][$i['childItemGroupID']] = array('itemGroupID' => $i['childItemGroupID']);
            $childs[] = $i['childItemGroupID'];
        }

        if (in_array($i['childItemGroupID'], $childs))
        {
            $allChilds = orderMe($input, $i['childItemGroupID']);
            if (!empty($allChilds[$i['childItemGroupID']]['children']))
                $return[$i['itemGroupID']]['children'][$i['childItemGroupID']] =  $allChilds;
        }
    }

    return $return;
}

print_r(orderMe($input, 1));

输出：

array (
  1 => 
  array (
    'itemGroupID' => 1,
    'children' => 
    array (
      2 => 
      array (
        'itemGroupID' => 2,
      ),
      3 => 
      array (
        'itemGroupID' => 3,
      ),
      4 => 
      array (
        'itemGroupID' => 4,
      ),
      212 => 
      array (
        'itemGroupID' => 212,
      ),
      339 => 
      array (
        'itemGroupID' => 339,
      ),
      336 => 
      array (
        'itemGroupID' => 336,
      ),
      6 => 
      array (
        6 => 
        array (
          'itemGroupID' => 6,
          'children' => 
          array (
            8 => 
            array (
              'itemGroupID' => 8,
            ),
            9 => 
            array (
              9 => 
              array (
                'itemGroupID' => 9,
                'children' => 
                array (
                  15 => 
                  array (
                    'itemGroupID' => 15,
                  ),
                ),
              ),
            ),
            10 => 
            array (
              10 => 
              array (
                'itemGroupID' => 10,
                'children' => 
                array (
                  16 => 
                  array (
                    'itemGroupID' => 16,
                  ),
                ),
              ),
            ),
            11 => 
            array (
              11 => 
              array (
                'itemGroupID' => 11,
                'children' => 
                array (
                  17 => 
                  array (
                    'itemGroupID' => 17,
                  ),
                ),
              ),
            ),
            12 => 
            array (
              12 => 
              array (
                'itemGroupID' => 12,
                'children' => 
                array (
                  18 => 
                  array (
                    'itemGroupID' => 18,
                  ),
                ),
              ),
            ),
            13 => 
            array (
              13 => 
              array (
                'itemGroupID' => 13,
                'children' => 
                array (
                  19 => 
                  array (
                    'itemGroupID' => 19,
                  ),
                ),
              ),
            ),
            74 => 
            array (
              74 => 
              array (
                'itemGroupID' => 74,
                'children' => 
                array (
                  75 => 
                  array (
                    'itemGroupID' => 75,
                  ),
                ),
              ),
            ),
          ),
        ),
      ),
      5 => 
      array (
        'itemGroupID' => 5,
      ),
    ),
  ),
)

- mpratt