php - オブジェクトの多次元配列の最後に到達する

Question

オブジェクトの配列を出力するSQL接続があり、そのようにソートされています

適切な階層を持つとして出力したいので、このように並べ替えています。

私はこの機能を持っています

function buildHTML($tree){
  echo 'building tree';
  foreach($tree as $item){
      $topItem = makeHtmlListItem($item);
       $pos = strpos($topItem, '</li>');
       $newItem = substr($topItem,0 , $pos);
       echo $newItem;
        foreach($item->childs as $subItem){
         echo '<ul>' . makeHtmlListItem($subItem) . '</ul>' ;
        }
echo '</li>';
 }
}

しかし、それは2番目のレベルにしか到達しません。任意の深さで底に到達するにはどうすればよいですか? 私は再帰でそれを行うことができましたが、今は再帰なしでやりたいと思っています。

score 2 · Accepted Answer

いつでもスタックアプローチを使用できます。これは、再帰が可能になる前に使用していたものとほぼ同じです。これは、関数を再帰的に呼び出すことがとにかく実際に行っていることのすべてであり、代わりにパラメーターをスタックするだけです。

次の例では、スタック配列 (FILO) を使用して現在処理中の配列を格納し、別のスタック配列を使用してそのレベルの現在の配列インデックスを追跡しています。簡単にするために 2 つの配列を使用しましたが、配列と現在のインデックスの両方を同じオブジェクトに格納できる構造を構築することもできます。以下は明らかに、非連想配列に対してのみ機能します。

あなたの基本クラス：

class listItem {
  public $name = '';
  public $parentId = 0;
  public $id = 0;
  public $childs = NULL;
  public function __construct($name, $parentId, $id, $childs = NULL){
    $this->name = $name;
    $this->parentId = $parentId;
    $this->id = $id;
    $this->childs = $childs;
  }
}

基本データ:

$data = array(
  new listItem('TV', 0, 1,
    array(
      new listItem('mini tv', 1, 29,
        array(
          new listItem('tiny tv', 29, 548),
        )
      ),
    )
  ),
  new listItem('RADIO', 0, 2,
    array(
      new listItem('mini radio', 2, 30),
      new listItem('Tiny LCD', 2, 551),
    )
  ),
  new listItem('Stereo', 0, 550),
  new listItem('Joe the Plumber', 0, 568,
    array(
      new listItem('Joe the Plumber', 568, 569,
        array(
          new listItem('Joe the Plumber', 569, 570,
            array(
              new listItem('Joe the Plumber', 570, 571)
            )
          )
        )
      )
    )
  ),
);

トラバース方式：

function traverse( $data ){
  $stack = array( $data );
  $place = array( 0 );
  $build = '<ul>';
  while ( $stack ) {
    $a = end($stack);
    $i = end($place);
    $k = key($place);
    $place[$k]++;
    if ( isset($a[$i]) ) {
      $item = $a[$i];
      $build .='<li><span>' . $item->name . '</span>';
      if ( $item->childs ) {
        $build .= '<ul>';
        $stack[] = $item->childs;
        $place[] = 0;
      }
    }
    else {
      array_pop($stack);
      array_pop($place);
      $build .= '</ul>' . ( $stack ? '</li>' : '' );
    }
  }
  return $build;
}

利用方法：

echo traverse( $data );

コメント付き:

function traverse( $data ){
  /// prep the stack
  $stack = array( $data );
  $place = array( 0 );
  /// I've tailored the build to be for list items
  $build = '<ul>';
  /// loop until we have no more stack
  while ( $stack ) {
    /// you could improve optimisation at the cost of readability
    /// by storing the end offsets rather than using `end()`.
    $a = end($stack); /// current array
    $i = end($place); /// current offset in that array
    $k = key($place); /// key used to update current offset
    /// update the current levels array index
    $place[$k]++;
    /// if we have an item, investigate
    if ( isset($a[$i]) ) {
      $item = $a[$i];
      /// output our list item
      $build .='<li><span>' . $item->name . '</span>';
      /// if we have children, level up the stack
      if ( $item->childs ) {
        $build .= '<ul>';
        $stack[] = $item->childs; /// adding child array for next iteration
        $place[] = 0; /// start scanning childs from 0 offset
      }
    }
    /// if no more items at this level, level down the stack
    else {
      array_pop($stack);
      array_pop($place);
      /// always output a ul at this point, but not an li at the end
      $build .= '</ul>' . ( $stack ? '</li>' : '' );
    }
  }
  /// the final html returned
  return $build;
}

出力：

<ul>
  <li>
    <span>TV</span>
    <ul>
      <li>
        <span>mini tv</span>
        <ul>
          <li><span>tiny tv</span></li>
        </ul>
      </li>
    </ul>
  </li>
  <li>
    <span>RADIO</span>
    <ul>
      <li>
        <span>mini radio</span>
      </li>
      <li>
        <span>Tiny LCD</span>
      </li>
    </ul>
  </li>
  <li>
    <span>Stereo</span>
  </li>
  <li>
    <span>Joe the Plumber</span>
    <ul>
      <li>
        <span>Joe the Plumber</span>
        <ul>
          <li>
            <span>Joe the Plumber</span>
            <ul>
              <li>
                <span>Joe the Plumber</span>
              </li>
            </ul>
          </li>
        </ul>
      </li>
    </ul>
  </li>
</ul>

score 1 · Accepted Answer

再帰を避けたい場合は、各要素がその親、最初の子、次の兄弟が何であるかを知る必要があります。恐ろしくコストがかかる各反復で検索する以外に、それを行う方法は他にありません。

理論的には、次のようなトラバースに適した方法でツリーを書き換えることができます。


function traverseTree($tree)
{
    $cnode = $tree[0];
    $process = true;
    while($cnode !== NULL) {
       if ($process)
         makeHtmlListItem($cnode);

       if ($cnode->child !== NULL && $process) {
         $process = true;
         $cnode = $cnode->child;
       } elseif ($pnode->next !== NULL) {
         $process = true;
         $cnode = $cnode->next;
       } else {
         // This is where we satisfy the exit condition, after we bubble up
         // upon processing the last top level branch
         $cnode = $cnode->parent;
         $process = false;
       }
    }
}

もちろん、静的な定義では、子プロパティと親プロパティの両方を設定することはできないため、事前にプログラムでツリーを準備する必要があります。

後で編集：実際には方法がありますが、それはとても醜いので、考えたくありません。各レベルのインデックスを含む配列を保存し、すべてをトラバースし終わるまで、それらを順番にインクリメントする必要があります。悪夢のようなもの。

score 0 · Accepted Answer

あなたと同様のデータ構造を使用するプログラムを作成しました。以下のコードをニーズに合わせて簡単に変更できるはずです。

<?php    

$arr = array(
    array(
        "name" => "lvl1",
        "childs" => array(
            array(
                "name" => "lvl2.1",
                "childs" => array(
                    array(
                        "name" => "lvl3.1",
                        "childs" => array()
                    ),
                    array(
                        "name" => "lvl3.2",
                        "childs" => array()
                    )
                )
            ),
            array(
                "name" => "lvl2.2",
                "childs" => array(
                    array(
                        "name" => "lvl3.3",
                        "childs" => array()
                    )
                )
            )
        )
    )
);


// current index at each level
$i = array(0);

// current array at each level
$cur = array($arr);


$lvl = 0;
while(TRUE) {
    // iterate over childless nodes at current level
    while(!$cur[$lvl][$i[$lvl]]["childs"]) {    
        echo $cur[$lvl][$i[$lvl]]["name"]."\n";
        ++$i[$lvl];
        // if ran out of nodes at current level
        while($i[$lvl] >= count($cur[$lvl])) {
            // and not at level 0
            if($lvl == 0) break 3;
            // move to next node one level above the current one
            ++$i[--$lvl];
        }
    }
    // descend until you hit the childless node
    while($cur[$lvl + 1] = $cur[$lvl][$i[$lvl]]["childs"]) {
        echo $cur[$lvl][$i[$lvl]]["name"]."\n";
        $lvl++;
        // start with first node at each level you descend to
        $i[$lvl] = 0;
    };
};

php - オブジェクトの多次元配列の最後に到達する

4 に答える 4

Related

Reference