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]

仕様

目的の解と入力配列の両方にいくつかの制限があります。

  • 入力配列は常に有効です。つまり、その構造は常にツリー構造にリファクタリングできます。負/非数値レベル、無効なレベル構造などの奇妙なことはありません
  • 入力配列は巨大になる可能性があり、現在、最大レベルは制限されていません
  • ソリューションは単一のループで問題を解決する必要があるため、配列をチャンクに分割したり、再帰を適用したり、配列内でジャンプしたりすることはできません。シンプルに (または別のループ - それは問題ではありません)、一度だけ、各要素を 1 つずつ処理する必要があります。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()) に依存しているため、問題は次のとおりです。

この問題を解決するためのより短くて明確な方法は他にもあるのでしょうか? 標準的な質問のように見えますが、対応する解決策が見つかりませんでした(同様の質問が1つありますが、OPには正確なparent_id従属がありますが、私はありません)

4

2 に答える 2

2

問題の良い点は、入力が常に適切にフォーマットされているため、実際の問題は、ノードが存在する場合は各ノードの子を見つけるか、ノードがある場合は各ノードの親を見つけることに絞り込まれることです。ここでは後者の方が適しています。これは、ノードのレベルが 1 を超える場合にノードに親があり、現在のノードのレベルから 1 を引いたレベルに等しいレベルを持つ初期フラット配列でその上にある最も近いノードであることがわかっているためです。これによれば、関心のあるいくつかのノードを追跡することができます。より正確には、同じレベルのノードが 2 つ見つかった場合、以前に見つかったノードはそれ以上の子を持つことはできません。

これの実装は次のようになります。

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 に答える