Recursive tree traversal - How to track recursion level?

Question

I'm basically trying to build an html ul / li nested list from a multidimensional array representing a tree structure.

The following code works fine, but I want to improve it:

I need a way to track the recursion level so that I can apply different classes to different levels, add padding to the generated output, etc.

function buildTree($tree_array, $display_field, $children_field, $class='', $id='') { echo "<ul>\n"; foreach ($tree_array as $row) { echo "<li>\n"; echo $row[$display_field] . "\n"; if (isset($row[$children_field])) { $this->buildTree($row[$children_field]); } echo "</li>\n"; } echo "</ul>\n"; } 

$ tree_array looks like this:

 Array ( [0] => Array ( [category_id] => 1 [category_name] => calculatoare [parent_id] => 0 [children] => Array ( [0] => Array ( [category_id] => 4 [category_name] => placi de baza [parent_id] => 1 ) [1] => Array ( [category_id] => 5 [category_name] => carcase [parent_id] => 1 [children] => Array ( [0] => Array ( [category_id] => 6 [category_name] => midi-tower [parent_id] => 5 ) ) ) ) ) [1] => Array ( [category_id] => 2 [category_name] => electronice [parent_id] => 0 ) [2] => Array ( [category_id] => 3 [category_name] => carti [parent_id] => 0 ) ) 

I marked this as homework, because I would like to use this as an opportunity to improve my (poor) understanding of recursion, therefore, I will be grateful for the answers that will help me in the solution, and not in providing a complete working example :)

Answer 1

Quick'n'dirty approach (see the "Spoiler" block below for implementation):

Add an additional variable $recursionDepth to the function declaration, by default set it to 0 .

For each subsequent recursion, call your function with $recursionDepth + 1 .

Since function variables are “visible” (limited) only for the corresponding function instance, you will get an indicator of the current iteration depth.

Also line 12 of your function

 $this->buildTree(); 

I don’t think this will work - the reason is that you are not passing your variables to the next buildTree instance.

It should probably look like this:

 $this->buildTree($row[$children_field], $display_field, $children_field, $class, $id) 

Here are the changes that I will make to your code to achieve what you want:

 function buildTree($tree_array, $display_field, $children_field, $class='', $id='', $recursionDepth = 0, $maxDepth = false) { if ($maxDepth && ($recursionDepth == $maxDepth)) return; echo "<ul>\n"; foreach ($tree_array as $row) { echo "<li>\n"; echo $row[$display_field] . "\n"; if (isset($row[$children_field])) $this->buildTree($row[$children_field], $display_field, $children_field, $class, $id, $recursionDepth + 1, $maxDepth); echo "</li>\n"; } echo "</ul>\n"; } 

Answer 2

You make your life harder than necessary. SPL offers a range of iterators for your convenience. Moving multidimensional arrays is easy with the RecursiveArrayIterator class . Not only does it allow you to process any levels of deep arrays, but it will also track depth.

Example

 $iterator = new RecursiveIteratorIterator( new RecursiveArrayIterator($array) ); for($iterator; $iterator->valid(); $iterator->next()) { printf( "Key: %s Value: %s Depth: %s\n", $iterator->key(), $iterator->current(), $iterator->getDepth() ); } 

Code example

As you can see, there is a getDepth() method that will always indicate the current iteration depth. This is the RecursiveIteratorIterator method needed to iterate over children in recursive iterators.

If you need to influence what happens when an iteration starts or when children are addressed, see my answer to a multidimensional iteration of an array that shows a custom RecursiveIteratorIterator that will transfer the values ​​of the multidimensional array to xml elements and mark them with the depth of the current iteration (which should be trivial to adapt to ul / li elements).

Also check out the Wikipedia article on Iterators for a general introduction.

Answer 3

 public virtual int GetLevelById(int id) { int i = GetParentById(id); if (i == 0) return 1; else return (1 + GetLevelById(i)); } 

public virtual int GetParentById (int t) {var ret = this._list.FirstOrDefault ((f) => f.Id == t); if (ret! = null) return ret.ParentId; return -1; }