How can I build an infinite depth nested HTML list from a flat array?

Question

I am trying to create a multi-level list of HTML from a source array that is formatted as follows:

/** * id = unique id * parent_id = "id" that this item is directly nested under * text = the output string */ $list = array( array( 'id' => 1, 'parent_id' => 0, 'text' => 'Level 1', ), array( 'id' => 2, 'parent_id' => 0, 'text' => 'Level 2', ), array( 'id' => 3, 'parent_id' => 2, 'text' => 'Level 2.1', ), array( 'id' => 4, 'parent_id' => 2, 'text' => 'Level 2.2', ), array( 'id' => 5, 'parent_id' => 4, 'text' => 'Level 2.2.1', ), array( 'id' => 6, 'parent_id' => 0, 'text' => 'Level 3', ) ); 

The goal is a nested <ul> with infinite depth. Expected array output above:

• Level 1
• Level 2
  • Level 2.1
  • Level 2.2
    • Level 2.2.1
• Level 3

If only the elements of the array had a key named child or something that contained the actual submatrix, it would be easy to recursively occupy them and get the desired result using this function:

 function makeList($list) { echo '<ul>'; foreach ($list as $item) { echo '<li>'.$item['text']; if (isset($item['child'])) { makeList($item['child']); } echo '</li>'; } echo '</ul>'; } 

Unfortunately, not for me - the format of the source arrays cannot be changed. So, a long time ago I wrote this very unpleasant function to make this happen, and it works only up to three levels (the code is inserted verbatim with the original comments). I know this is a long boring read, please carry me:

 function makeArray($links) { // Output $nav = array(); foreach ($links as $k => $v) { // If no parent_id is present, we can assume it is a top-level link if (empty($v['parent_id'])) { $id = isset($v['id']) ? $v['id'] : $k; $nav[$id] = $v; // Remove from original array unset($links[$k]); } } // Loop through the remaining links again, // we can assume they all have a parent_id foreach ($links as $k => $v) { // Link parent_id is in the top level array, so this is a level-2 link // We already looped through every item so we know they are all accounted for if (isset($nav[$v['parent_id']])) { $id = isset($v['id']) ? $v['id'] : $k; // Add it to the top level links as a child $nav[$v['parent_id']]['child'][$id] = $v; // Set a marker so we know which ones to loop through to add the third level $nav2[$id] = $v; // Remove it from the array unset($links[$k]); } } // Last iteration for the third level // All other links have been removed from the original array at this point foreach ($links as $k => $v) { $id = isset($v['id']) ? $v['id'] : $k; // Link parent_id is in the second level array, so this is a level-3 link // Orphans will be ignored if (isset($nav2[$v['parent_id']])) { // This part is crazy, just go with it $nav3 = $nav2[$v['parent_id']]['parent_id']; $nav[$nav3]['child'][$v['parent_id']]['child'][] = $v; } } return $nav; } 

This makes an array like:

 array( 'text' => 'Level 1' 'child' => array( array( 'text' => 'Level 1.2' 'child' => array( array( 'text' => 'Level 1.2.1' 'child' => array( // etc. ), array( 'text' => 'Level 1.2.2' 'child' => array( // etc. ), ) ) ) ) ); 

Using:

 $nav = makeArray($links); makeList($nav); 

---

I spent a lot of free hours trying to figure it out, and the source code I provided here is still the best solution I could create.

How can I do this without this terrible function (which is limited to a depth of 3) and has an infinite number of levels? Is there a more elegant solution for this?

Answer 1

Print

 function printListRecursive(&$list,$parent=0){ $foundSome = false; for( $i=0,$c=count($list);$i<$c;$i++ ){ if( $list[$i]['parent_id']==$parent ){ if( $foundSome==false ){ echo '<ul>'; $foundSome = true; } echo '<li>'.$list[$i]['text'].'</li>'; printListRecursive($list,$list[$i]['id']); } } if( $foundSome ){ echo '</ul>'; } } printListRecursive($list); 

Create a multidimensional array:

 function makeListRecursive(&$list,$parent=0){ $result = array(); for( $i=0,$c=count($list);$i<$c;$i++ ){ if( $list[$i]['parent_id']==$parent ){ $list[$i]['childs'] = makeListRecursive($list,$list[$i]['id']); $result[] = $list[$i]; } } return $result; } $result = array(); $result = makeListRecursive($list); echo '<pre>'; var_dump($result); echo '</pre>'; 

Answer 2

Tested and working :)

 $list = array(...); $nested = array(); foreach ($list as $item) { if ($item['parent_id'] == 0) { // Woot, easy - top level $nested[$item['id']] = $item; } else { // Not top level, find it place process($item, $nested); } } // Recursive function function process($item, &$arr) { if (is_array($arr)) { foreach ($arr as $key => $parent_item) { // Match? if (isset($parent_item['id']) && $parent_item['id'] == $item['parent_id']) { $arr[$key]['children'][$item['id']] = $item; } else { // Keep looking, recursively process($item, $arr[$key]); } } } } 

Answer 3

Some methods that I recently wrote, maybe some of them will help, I'm sorry that I am short on time and I can not rewrite them according to your needs.

This code is actually part of the Kohana Framework model model, the ->as_array() method ->as_array() used to align the Database_Result object.

 function array_tree($all_nodes){ $tree = array(); foreach($all_nodes as $node){ $tree[$node->id]['fields'] = $node->as_array(); $tree[$node->id]['children'] = array(); if($node->parent_id){ $tree[$node->parent_id]['children'][$node->id] =& $tree[$node->id]; } } $return_tree = array(); foreach($tree as $node){ if($node['fields']['depth'] == 0){ $return_tree[$node['fields']['id']] = $node; } } return $return_tree; } 

array_tree() used to create a tree from a flat array. The key feature is =& part;)

 function html_tree($tree_array = null){ if( ! $tree_array){ $tree_array = $this -> array_tree(); } $html_tree = '<ul>'."\n"; foreach($tree_array as $node){ $html_tree .= $this->html_tree_crawl($node); } $html_tree .= '</ul>'."\n"; return $html_tree; } function html_tree_crawl($node){ $children = null; if(count($node['children']) > 0){ $children = '<ul>'."\n"; foreach($node['children'] as $chnode){ $children .= $this->html_tree_crawl($chnode); } $children .= '</ul>'."\n"; } return $this->html_tree_node($node, $children); } 

html_tree_node() is an easy way to display the current node and children in HTML. Example below:

 <li id="node-<?= $node['id'] ?>"> <a href="#"><?= $node['title'] ?></a> <?= (isset($children) && $children != null) ? $children : '' ?> </li>