CODEWITHSUNDEEP
phprecursioniteration
Steam Second
Steam Second

Reputation: 11

Tree iteration without recursion

So, I was trying to print my class:

class category {

  public $name;
  public $id;
  public $subCats = array();

  public function __construct($name = "", $id = "") {
    $this->name = $name;
    $this->id = $id;
  }

  public function add_sub_cat($subCat) {
    array_push($this->subCats, $subCat);
  }

}

In two ways recursive and iterative, first one I did without any problems:

function recursive_print($category, $path) {
  ?>
    <li><div id="category-name" ><p><? echo $category->name ?></p>
              </div></li>
      <?php foreach($category->subCats as $subCat) { ?>
      <ul>
        <?php recursive_print($subCat, $path.=$subCat->id) ?>
      </ul>
    <?php }
}

But now I got stuck on second part of this task. Do I have to modify my class? Is it even possible to print without recursion? I have read this but it did not cleared anything. Maybe someone have better tutorial or any advice?

Upvotes: 0

Views: 990

Answers (1)

Keiji
Keiji

Reputation: 1042

Walking a tree without recursion is always an interesting problem.

The basic idea is you need to keep track of a stack by yourself. (Function calls are implemented by pushing temporary variables and a return address to a stack before the call, and popping that return address afterwards, so when you make a recursive function, you're avoiding having to do this yourself.)

Here's a non-recursive implementation:

function tree_print($root_category) {
  $stack = array(array($root_category));
  echo '<ul>'."\n";
  while (count($stack)) {
    $category = array_shift($stack[count($stack)-1]);
    echo '<li><div id="category-name"><p>' . $category->name . '</p></div></li>'."\n";
    echo '<ul>'."\n";
    $stack[] = $category->subCats;
    while (count($stack) && count($stack[count($stack)-1]) == 0) {
      echo '</ul>'."\n";
      array_pop($stack);
    }
  }
}

In each iteration round the main loop, we shift the first tree node from the array at the top of the stack, print it, open a <ul> tag, and push to the stack an array of all its child nodes. Then, we get rid of any empty arrays from the top of the stack, closing one <ul> tag for each such empty array.

See it running here: https://3v4l.org/umpvf

Upvotes: 1

Related Questions