到达多维对象数组的底部

I have an SQL connection which outputs an array of objects and it is sorted like so

I am sorting it this way since I want to output it as a with the proper hierarchy.

I have this function

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

But it only gets to the second level. How do I get to the bottom with an arbitrary depth? I managed to do it with recursion but now I want to do it without recursion and I am going nuts.

You could always use the stack approach, pretty much what you would use before recursion was a possibility — this is all that recursively calling a function is really doing anyway, it's just stacking parameters instead.

The following just uses a stacked array (FILO) to store the current array being dealt with and another stacked array to keep track of the current array index at that level. I've used two arrays for simplicity but you could construct a structure that could store both array and current index in the same object. The following obvsiously will only work for non-associative arrays:

Your base class:

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

Your base data:

$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)
            )
          )
        )
      )
    )
  ),
);

A traverse method:

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

usage:

echo traverse( $data );

with comments:

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

output:

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

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

This little snippet stores where you are in some array and your depth ($counter and $depth). Then it goes deeper and deeper until it finds an end, then goes back.

If you want to avoid recursion, you need each element to know what's its parent, first child and next sibling. There simply is no other way to do it, except searching on each iteration, which is horribly expensive.

You could theoretically rewrite your tree in such a fashion that it would lend itself to traversing like so:


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

Of course, that would mean you'd have to prepare the tree programatically beforehand, because with a static definition you can't end up with both the child and the parent properties set.

Later edit: actually, there is a way, but it's so ugly I don't even want to think about it. You'd have to store an array containing indexes for each level, and incrementing each of those in turn, until you finish traversing the whole thing. The stuff of nightmares.

I wrote program that uses data structure similar to yours. You should be able to adapt the code below to your needs easily.

<?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"]."
";
        ++$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"]."
";
        $lvl++;
        // start with first node at each level you descend to
        $i[$lvl] = 0;
    };
};