5

所以，

问题

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

$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']
];

问题是 - 转换该数组，使其成为一棵树。从属关系仅由元素 order 和levelfield 确定。让我们定义children为存储子节点的维度名称。对于上面的数组，它将是：

  大批 （
    大批 （
      '水平' => 1，
      '名称' => '根#1',
    ),
    大批 （
      '水平' => 1，
      '名称' => '根 #2',
      '孩子' =>
      大批 （
        大批 （
          '级别' => 2,
          '名称' => '子根 2-1',
          '孩子' =>
          大批 （
            大批 （
              '级别' => 3,
              '名称' => '__subroot 2-1/1',
            ),
          ),
        ),
        大批 （
          '级别' => 2,
          '名称' => '子根 2-2',
        ),
      ),
    ),
    大批 （
      '水平' => 1，
      '名称' => '根#3',
    ),
  )

如果不清楚谁是谁的父母，请进行更多说明：以下代码可以轻松地可视化想法：

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

- 对于上面的数组：

-[根#1]
-[根#2]
--[子根 2-1]
---[__subroot 2-1/1]
--[子根 2-2]
-[根#3]

细节

所需的解决方案和输入数组都有一些限制：

  • 输入数组始终有效：这意味着它的结构始终可以重构为树结构。没有负数/非数字级别，没有无效级别结构等奇怪的东西
  • 输入数组可能很大，目前最大级别不受限制
  • 解决方案必须通过单循环解决问题，因此我们不能将数组拆分为块，应用递归或以某种方式在数组内跳转。只是简单foreach（或另一个循环 - 没关系），只有一次，每个元素应该一个一个地处理。

我的方法

目前，我有堆栈的解决方案。我正在使用引用并维护堆栈的当前元素，将在当前步骤中写入该元素。那是：

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;
}

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

问题

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

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

4

2 回答 2

2

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

实现将如下所示：

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]);
        }
    }
}

演示

于 2013-11-13T12:27:58.800 回答
1

使用递归的实现：

 function buildTreeHelper(&$array, $currentLevel = 1)
 {
     $result = array();
     $lastIndex = 0;
     while($pair = each($array)) {
         list(, $row) = $pair;
         $level = $row['level'];
         if ($level > $currentLevel) {
             $result[$lastIndex]['children'] = buildTreeHelper($array, $level);
         } else if ($level == $currentLevel) {
             $result[++$lastIndex] = $row;
         } else {
             prev($array); // shift back
             break;
         }
     }
     return $result;
 }

 function buildTree($array)
 {
     reset($array);
     return buildTreeHelper($array);
 }

 $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']
];

 print_r(buildTree($array));
于 2013-11-12T12:00:15.583 回答