Converting tree to correct HTML list in PHP

Created:07 Jul 2017 22:48:43 , in  Maths,  Web development

From time to time, when doing coding for the web or otherwise, you might come across a tree of data to be turned into a correct HTML list (what "correct" means in this context will be explained in a minute). In order to meet the requirement, you have to be able to traverse a tree in an efficient manner first.

.

Trees, unlike one-dimensional arrays, are recursively-defined data structures. So, rather than using loops for traversing them, which incidentally can be done, but looks ugly and feels even worse, you might need to cosy up to, or at least stop frowning upon, recursion for a while.

By the way, I hope you have have some experience of recursion or perhaps practiced it on linear data structures a little by now. If not, doesn't matter really, not for this this article anyway. Code presented in this article requires next to nothing knowledge of the technique.

In terms of used PHP code, this text builds on what I wrote in Traversing trees in pre-order recursively in PHP

.

In that article I have given a PHP class, SWWWTreeTraversal, that implements recursive tree traversal in pre-order algorithm.

In this instalment I'm going to extend SWWWTreeTraversal with a class called SWWWTreeTraversalArrToList. SWWWTreeTraversalArrToList is a piece of PHP code, that builds a HTML ordered / unordered list based on a tree as its input.

A word on correct HTML lists

Before moving further probably I should explain what I mean by "correct HTML list". Basically it is a list, that has all the tags closed right and nested items placed in a separate list tag as opposed to li tags doubled or skipped entirely. The latter can be frequently found in quick fixes for "building a HTML list from a tree" problem.

Hence:

This is correct:      This is not:
<ul>                  <ul>
  <li>                   <li>
    <ul>                    <li> 
      <li></li>             </li>
      <li></li>         </li>    
    </ul>              </li> 
  </li>
</ul> 

SWWWTreeTraversalArrToList PHP class

Here is, SWWWTreeTraversalArrToList listing:

/*
  Class: SWWWTreeTraversalArrToList 
  Description: Convert tree given as array to a correct HTML list
  Author: Sylwester Wojnowski
  WWW: wojnowski.net.pl

  Configuration options:
    $tree - array - a tree to be traversed
    [$ltype] - HTML list type to convert tree to (ol/ul) defaults to ul  
    [$bclass] - HTML element class property to give to a list item that has children (tree branch)  
    [$lclass] - HTML element class property to give to a list item that has no children (tree leaf)

  Methods:
    get - get a HTML list
      return - String - HTML list
*/

class SWWWTreeTraversalArrToList extends SWWWTreeTraversal{
  // list type to construct
  protected $ltype = 'ul';
  // leaf HTML class 
  protected $bclass = 'branch';
  // branch HTML class
  protected $lclass = 'leaf';
  
  public function __construct($conf){
  
    foreach($conf as $k => $s){
    
      if(property_exists($this,$k)){
        $this -> {$k} = $s;
      }
    }
    
    $this -> output = '';
    
    parent::__construct($conf);
  }

  protected function preorder($nodes){
  
    if(empty($nodes)){
        return;
    }
    
    $counter = 0;
  
    $this -> output .= '<'. $this -> ltype .'>';
  
    foreach($nodes as $i => $node){
      $this -> visit_root($i,$node);
    
      $this -> visit_children($node);
      
      $counter++;     

      if($counter === count($nodes)){
        $this -> output .= '</'. $this -> ltype .'>';
        unset($counter);
      }
    }   
  }
  
  protected function visit_root($i,$root){
    // process leaf
    if(is_string($root)){ 
      if($i % 2 === 0){
        if(!empty($root)){
          $this -> output .= '<li class="'. $this -> lclass .'">';
          $this -> output .= '<a href="'. $root .'">';
        }  
      }else{
        if(!empty($root)){  
          $this -> output .= $root;
          $this -> output .= '</a>';
          $this -> output .= '</li>';
        }
      }
    }  
  }
  
  protected function visit_children($children){
    if(is_array($children) && !empty($children)){
      $this -> output .= '<li class="'. $this -> bclass .'">';  
      $this -> preorder($children);
      $this -> output .= '</li>';
    }   
  }
}

To use this class you need to include both it and its parent class - SWWWTreeTraversal in your program.

Examples of converting trees to HTML lists

Here is a fairly simple tree with nodes called anchor1,https://domain1.com through anchor7,https://domain7.com.

  anchor1,https://domain1.com
  |
  |_____anchor2,https://domain2.com
  |     |
  |     |_____anchor4,https://domain2.com
  |     |     |
  |     |     |____anchor5,https://domain5.com
  |     |     |
  |     |     |____anchor8,https://domain8.com
  |     |     |
  |     |     |____
  |     |     |    |
  |     |     |    |____anchor6,https://domain6.com        
  |     |
  |     |_____anchor7,'https://domain7.com'
  |
  anchor3,'https://domain3.com'

For the tree to become readable to PHP, it has to be turned into an array, which results in the following:

$tree = array(
  'https://domain1.com',
  'anchor1',
  array(
    'https://domain2.com',
    'anchor2',
    array(
      'https://domain4.com',
      'anchor4',
      array(
        'https://domain5.com',
        'anchor5',
        'https://domain8.com',
        'anchor8'
      ),
      array(
        'https://domain6.com',
        'anchor6'
      )
    ),
    array(
      'https://domain7.com',
      'anchor7'
    )
  ),
  array(
    'https://domain3.com',
    'anchor3'
  )
);

Applying SWWWTreeTraversalArrToList class to the PHP array:

$conf = array(
  'tree' => $tree
);
    
$instance = new SWWWTreeTraversalArrToList($conf);  
$instance -> get();

Results in the following correct HTML unordered list:

<ul>
  <li class="leaf"><a href="https://domain1.com">anchor1</a></li>
  <li class="branch">
    <ul>
      <li class="leaf"><a href="https://domain2.com">anchor2</a></li>
      <li class="branch">
        <ul>
          <li class="leaf"><a href="https://domain4.com">anchor4</a></li>
          <li class="branch">
            <ul>
              <li class="leaf"><a href="https://domain5.com">anchor5</a></li>
              <li class="leaf"><a href="https://domain8.com">anchor8</a></li>
            </ul>
          </li>
          <li class="branch">
            <ul>
              <li class="leaf"><a href="https://domain6.com">anchor6</a></li>
            </ul>
          </li>
        </ul>
      </li>
      <li class="branch">
        <ul>
          <li class="leaf"><a href="https://domain7.com">anchor7</a></li>
        </ul>
      </li>
    </ul>
  </li>
  <li class="branch">
    <ul>
      <li class="leaf"><a href="https://domain3.com">anchor3</a></li>
    </ul>
  </li>
</ul>

This list contains not only HTML list elements but also anchor elements in them.

Here is another example in which a tree is converted to an ordered list. In this example, custom names get assigned to HTML class property of list items.

  |
  |_____anchor1,https://domain1.com
  |      
  |_____anchor2,https://domain2.com
  |     |
  |     |_____anchor3,https://domain3.com
  |     | 
  |     |_____anchor4,https://domain2.com
  |     |
  |     |_____
  |     |     |
  |     |     |
  |     |     anchor7,https://domain7.com  
  |     |     
  |     |_____ 
  |     |     |
  |     |     |_____anchor5,https://domain5.com
  |     |     |
  |     |     |_____anchor6,https://domain6.com   

Turning the tree into a PHP array will result in this:

$tree = array(
  'https://domain1.com',
  'anchor1',
  'https://domain2.com',
  'anchor2',
  array(
    'https://domain3.com',
    'anchor3',
    'https://domain4.com',
    'anchor4',
    array(
      'https://domain7.com',
      'anchor7'
    )  
  ),
  array(
    'https://domain5.com',
    'a5',
    'https://domain6.com',
    'a6',
  )
);

Here are configuration options for this case:

        
$conf = array(
  'tree' => $tree,
  'ltype' => 'ol',
  'bclass' => 'b',
  'lclass' => 'l',
);

Instantiate the class and get a HTML list:

    
$instance = new SWWWTreeTraversalArrToList($conf); 
$instance -> get();  

Here is the result:

<ol>
  <li class="l"><a href="https://domain1.com">anchor1</a></li>
  <li class="l"><a href="https://domain2.com">anchor2</a></li>
  <li class="b">
    <ol>
      <li class="l"><a href="https://domain3.com">anchor3</a></li>
      <li class="l"><a href="https://domain4.com">anchor4</a></li>
      <li class="b">
        <ol>
          <li class="l"><a href="https://domain7.com">anchor7</a></li>
        </ol>
      </li>
    </ol>
  </li>
  <li class="b">
    <ol>
      <li class="l"><a href="https://domain5.com">a5</a></li>
      <li class="l"><a href="https://domain6.com">a6</a></li>
    </ol>
  </li>
</ol>

I hope these two examples are clear enough to give you some insight on how SWWWTreeTraversalArrToList works and what can be achieved with it.

Final thoughts

SWWWTreeTraversalArrToList is a not-too-complicated example of a class that extends SWWWTreeTraversal. It works on ordinary arrays and creates its output in a particular way. It certainly lacks some more advanced features like capabilities of finding a tree depth level or adding a HTML class for the current item. Either of these features are implementable using an extra object property, inheritance or simply rewriting visit_children and/or visit_root methods to suit your needs.

Very similar class to SWWWTreeTraversalArrToList can be written for trees made of associative arrays or objects. Code in SWWWTreeTraversalArrToList should give you enough clues how to do that.

I hope you have found the article interesting and informative. If in doubt take a look at the first article in this series - Traversing trees in pre-order recursively in PHP.

This post was updated on 09 Jul 2017 01:05:36

Tags:  data structure ,  php ,  recursion