Tree iteration without recursion

Question

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?

Im not asking for complete solution, Im asking for a direction, sources or just to answer those 2 questions — Steam Second
– Steam Second, Commented Mar 17, 2018 at 18:35
make a stack of all the items you have to process. add your "master"-item. if the item you currently scan has children, push them onto the stack. repeat until stack is empty. — Franz Gleichmann
– Franz Gleichmann, Commented Mar 17, 2018 at 18:38

Keiji · Accepted Answer · 2018-03-17 18:35:59Z

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

Collectives™ on Stack Overflow

Tree iteration without recursion

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related