所以，

问题

假设我们有具有以下结构的平面数组:

$array = [
  ['level'=>1, 'name' => 'Root #1'],
  ['level'=>1, 'name' => 'Root #2'],
  ['level'=>2, 'name' => 'subroot 2-1'],
  ['level'=>3, 'name' => '__subroot 2-1/1'],
  ['level'=>2, 'name' => 'subroot 2-2'],
  ['level'=>1, 'name' => 'Root #3']
];

问题是 - 转换该数组，使其成为一棵树。从属仅由元素顺序和 level 字段确定。让我们定义 children 作为存储子节点的维度名称。对于上面的数组将是:

  array (
    array (
      'level' => 1,
      'name' => 'Root #1',
    ),
    array (
      'level' => 1,
      'name' => 'Root #2',
      'children' => 
      array (
        array (
          'level' => 2,
          'name' => 'subroot 2-1',
          'children' => 
          array (
            array (
              'level' => 3,
              'name' => '__subroot 2-1/1',
            ),
          ),
        ),
        array (
          'level' => 2,
          'name' => 'subroot 2-2',
        ),
      ),
    ),
    array (
      'level' => 1,
      'name' => 'Root #3',
    ),
  )

A little more clarifications, if it's not obvious who is parent for who: following code could easily visualize idea:

function visualize($array)
{
   foreach($array as $item)
   {
      echo(str_repeat('-', $item['level']).'['.$item['name'].']'.PHP_EOL);
   }
}
visualize($array);

-对于上面的数组是:

-[Root #1]
-[Root #2]
--[subroot 2-1]
---[__subroot 2-1/1]
--[subroot 2-2]
-[Root #3]

Specifics

There are some restrictions both for desired solution and input array:

• Input array is always valid: that means it's structure can always be refactored to tree structure. No such weird things as negative/non-numeric levels, no invalid levels structure, e t.c.
• Input array can be huge and, currently, maximum level is not restricted
• Solution must resolve a matter with single loop, so we can not split array to chunks, apply recursion or jump within array somehow. Just simple foreach (or another loop - it does not matter), only once, each element one-by-one should be handled.

My approach

Currently, I have solution with stack. I'm working with references and maintaining current element of stack to which writing will be done at current step. That is:

function getTree(&$array)
{
   $level = 0;
   $tree  = [];
   $stack = [&$tree];
   foreach($array as $item)
   {
      if($item['level']>$level) //expand stack for new items
      {
         //if there are child elements, add last to stack:
         $top = key($stack);
         if(count($stack[$top]))
         {
            end($stack[$top]);
            $stack[] = &$stack[$top][key($stack[$top])];
         }
         //add ['children'] dim to top stack element
         end($stack);
         $top = key($stack);
         $stack[$top]['children'] = [];
         $stack[] = &$stack[$top]['children'];
      }
      while($item['level']<$level--) //pop till certain level
      {
         //two times: one for last pointer, one for ['children'] dim
         array_pop($stack);
         array_pop($stack);
      }
      //add item to stack top:
      end($stack);
      $stack[key($stack)][] = $item;
      $level = $item['level'];
   }
   return $tree;
}

-因为它足够长，我创建了一个sample使用和输出。

问题

如您所见，我的解决方案很长，它依赖于引用和数组内部指针处理(例如 end())，所以问题是 :

可能有其他更短更清晰的方法来解决这个问题？它看起来像一些标准问题，但我没有找到任何相应的解决方案(有一个类似的 question - 但 OP 有确切的 parent_id 从属关系，而我没有)

最佳答案

关于您的问题的好处是，您的输入始终格式正确，因此您的实际问题缩小到为每个节点查找子节点(如果存在)或为每个节点查找父节点(如果有)。后者在这里更合适，因为我们知道如果节点的级别大于 1，则该节点有父节点，并且它是初始平面数组中其上方最近的节点，其级别等于当前节点的级别减一。根据这一点，我们可以只跟踪我们感兴趣的几个节点。更准确地说，每当我们找到两个具有相同级别的节点时，较早找到的节点不能有更多的 child 。

这个的实现看起来像这样:

function buildTree(array &$nodes) {
    $activeNodes = [];

    foreach ($nodes as $index => &$node) {
        //remove if you don't want empty ['children'] dim for nodes without childs
        $node['children'] = [];
        $level = $node['level'];
        $activeNodes[$level] = &$node;

        if ($level > 1) {
            $activeNodes[$level - 1]['children'][] = &$node;
            unset($nodes[$index]);
        }
    }
}

Demo

关于php - 使用一次性循环将平面数组转换为树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19927176/