php - 深入到多维对象数组的底部

Question

我有一个 SQL 连接，它输出一个对象数组，它是这样排序的

我以这种方式对其进行排序，因为我想将其输出为具有适当层次结构的 a 。

我有这个功能

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

但它只达到了第二个层次。如何以任意深度到达底部？我设法通过递归来做到这一点，但现在我想在没有递归的情况下做到这一点，我快疯了。

score 2 · Accepted Answer

你总是可以使用堆栈方法，这几乎是在递归成为可能之前你会使用的方法——这就是递归调用函数实际上所做的一切，它只是堆叠参数。

下面只使用一个堆叠数组（FILO）来存储当前正在处理的数组，并使用另一个堆叠数组来跟踪该级别的当前数组索引。为简单起见，我使用了两个数组，但您可以构建一个结构，将数组和当前索引存储在同一个对象中。以下显然仅适用于非关联数组：

你的基类：

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

$counter = array(-1);
$depth = 0;
echo "<ul>";

while ($depth > -1) {
    $tmptree = new stdClass;
    $tmptree->childs = $tree; // little hack to not have to do in the for loop: if (!$i) $tmptree = $tmptree[...]; else $tmptree = $tmptree->childs[...];
    for ($i = 0; $i <= $depth; $i++) {
        if ($i == $depth && !isset($tmptree->childs[++$counter[$i]])) {
            echo "</ul>",$i?"</li>":"";
            $depth--;
            continue 2;
        }
        $tmptree = $tmptree->childs[$counter[$i]];
    }

    $topItem = makeHtmlListItem($tmptree);
    $pos = strpos($topItem, '</li>');
    $newItem = substr($topItem,0 , $pos);
    echo $newItem;

    if (isset($tmptree->childs)) {
        echo "<ul>";
        $counter[++$depth] = -1;
    }
}

这个小片段存储了您在某个数组中的位置以及您的深度（$counter和$depth）。然后它越来越深，直到它找到一个结束，然后返回。

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