Traversing trees in pre-order recursively in PHP

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

Code for traversing trees in pre-order in PHP

Depth-first pre-order tree traversal

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

This post was updated on 06 Oct 2021 21:50:25

Tags:  data structure ,  php ,  recursion