Traversing trees in pre-order recursively in PHP

Traversing trees in pre-order recursively in PHP

Created:03 Jul 2017 13:58:12 , in  Maths,  Web development

Like in the real world, trees are ubiquitous in computer programming today. Frequently tree data structure turns out to be a perfect choice for modelling a naturally occurring phenomena and not only them these days. The bad news is, unlike one-dimensional arrays or other data structures which can be traversed in linear order, or simply speaking - pretty painlessly, excluding the simplest cases, trees cannot.

However, there is also a good news. For many years trees are well-researched and better and better understood. There exists abundance of information on them both online and in Maths literature. Moreover, over recent decades there have been devised some very clever schemes for traversing trees efficiently.

It is worth nothing, that at least in the field of computer programming, I'm not sure about climbing trees in the real world, recursion is frequently a tool to employ for handling trees.

Recursion can be difficult to follow at times. On the other hand, especially if written carefully, it reduces amount of code needed to perform a complex task. Moreover, or perhaps first of all, it is a perfect technique for dealing with recursively defined data structures - trees are such structures.

Depth-first pre-order tree traversal

Among others, a tree can be traversed in pre-order, which is a sort of depth-first tree traversal method. In this method, which start from visiting the "top-most" node, the goal is to reach the lowest laying nodes (leafs) from left to right (or otherwise) first. While traversing towards the bottom, if present, intermediate nodes (branches), are visited. Once all terminal nodes (leafs) for given branch have been visited, traversing moves on to its siblings and stops when all leafs in the tree have been reached.

Suppose, there is a tree like this:


           a
          / \
         b   c
        / \   \
       d   e   f

Traversing it in pre-order from left to right will result in visiting all the nodes in the following order: a , b , d , e , c , f .

SWWWTreeTraversal class

SWWWTreeTraversal is a PHP class for traversing trees depth-first I wrote some time ago. It uses recursion and pre-order method of traversing this data structure. It can traverse trees whose nodes are numbers, strings, associative arrays or objects (when extended) among others. It can also be extended freely.

Here is the code:


/*
  Class: SWWWTreeTraversal 
  Description: Recursive tree traversal in pre-order
  Author: Sylwester Wojnowski
  WWW: wojnowski.net.pl

  Configuration parameters:
    $tree - a tree to be traversed  

  Methods:
    get - get output from traversing a tree
      return value: array
*/
class SWWWTreeTraversal{
  protected $tree;
  protected $output = array();


  public function __construct($conf){
    $this -> tree = isset($conf['tree']) ? $conf['tree'] : array();   
    $this -> preorder($this -> tree);
  }

  protected function preorder($nodes){
  
    if(empty($nodes)){
        return;
    }
  
    foreach($nodes as $node){
      $this -> visit_root($node);
    
      $this -> visit_children($node);
    }   
  }
  
  protected function visit_root($root){
      if(! is_array($root) && !is_object($root)){
        $this -> output[] = $root;      
      }
  }
  
  protected function visit_children($children){
    if(is_array($children)){
      $this -> preorder($children);
    }   
  }
  
  public function get(){
    return $this -> output;
  }
}

Configuration and use

SWWWTreeTraversal accepts associative array of configuration options, with exactly one item in it - a tree to be traversed.

Examples of traversing trees with SWWWTreeTraversal

Once configured and instantiated SWWWTreeTraversal outputs array of values which can be obtained using "get" method.

Going back to the tree mentioned earlier in this article:


           a
          / \
         b   c
        / \   \
       d   e   f

And here is a piece of code needed to traverse the tree


# the tree in the form digestible to PHP:
$tree = array(
  'a', 
  array(
    'b',
    array('d','e')
  ), 
  array(
    'c',
    array('f')
  ) 
);

# configuration options: 
$conf = array(
  'tree' => $tree
);

# instantiate SWWWTreeTraversal    
$instance = new SWWWTreeTraversal($conf);
# get output:
$instance -> get()
=> array('a','b','d','e','c','f')  

The same can be done for tree made of numbers:


           1
          / \
         2   5
        / \   \
       3   4   6

Here is PHP code:

       
$tree = array( 1, array(2,array(3,4)), array(5,array(6)) );   
$conf = array('tree' => $tree);
    
$instance = new SWWWTreeTraversal($conf);  
$instance -> get()
=> array(1,2,3,4,5,6)

Trees made up of associative arrays can be traversed:


         a
         |_ _
         | | |
         b e c
         | | 
         d f  

Here is PHP code for the case:


$tree = array(
  'name' => 'a',
  'children' => array(
    array(
      'name' => 'b',
      'children' =>  array(
        'name' => 'd',
        'children' => array() 
      ) 
    ),
    array(
      'name' => 'e',
      'children' =>  array(
        'name' => 'f',
        'children' => array() 
      ) 
    ),
    array(
      'name' => 'c',
      'children' =>  array()
    )    
  )
);

$conf = array('tree' => $tree);      
$instance = new SWWWTreeTraversal($conf);  
$this -> assertEquals(array('a','b','d','e','f','c'),$instance -> get());

Extending SWWWTreeTraversal

Nothing stops you from extending SWWWTreeTraversal:

SWWWTreeTraversalObj, which is an extension to SWWWTreeTraversal, handles traversing trees of objects:

 
class SWWWTreeTraversalObj extends SWWWTreeTraversal{
  protected $p_children;
  
  public function __construct($conf){
    $this -> p_children = isset($conf['p_children']) ? $conf['p_children'] : 'children';  
    parent::__construct($conf);
  }
  
  protected function visit_root($root){ 
    $this -> output[] = $root;      
  }
  
  protected function visit_children($children){
    if(is_object($children)){
      $this -> preorder($children);
    }
  }    
}

Here is a small tree to be traverse with it:


        o
       / 
      o
     / \
    o   o
   /     \
  o       o

And here is traversal PHP code:


$tree = (object)array(
  'children' => (object)array(
    'children' => (object)array(
      (object)array(
        'children' => (object)array(),
      (object)array(
        'children' => (object)array()
      )  
     )
   )
  )
);

$conf = array('tree' => $tree);
    
$instance = new SWWWTreeTraversalObj($conf);  
count($instance -> get());
=> 6

Finally, 'get' also can be overwritten to do something more useful than just returning node values. Your imagination is the limit here.

Final thoughts

SWWWTreeTraversal is a basic and readily extensible PHP class which makes traversing trees easy. In this article I have focused on basic use examples for it. In the follow-up I'm going to do something useful using the class.

This post was updated on 03 Jul 2017 14:00:30

Tags:  data structure ,  php ,  recursion 


Author, Copyright and citation

Author

Sylwester Wojnowski

Author of the above article, Sylwester Wojnowski, is sWWW admin and owner.He enjoys doing Maths and studying algorithms, writing code in scripting and command languages, Thrash Metal music and playing electric guitar.

Copyrights

©Copyright, 2017 Sylwester Wojnowski. This article may not be reproduced or published as a whole or in parts without permission from the author. If you share it, please give author credit and do not remove embedded links.

Computer code, if present in the article, is excluded from the above and licensed under GPLv3.

Citation

Cite this article as:

Wojnowski, Sylwester. "Traversing trees in pre-order recursively in PHP." From sWWW - Code For The Web . https://wojnowski.net.pl//main/index/traversing-trees-in-pre-order-recursively-in-php