![Traversing trees in pre-order recursively in PHP Traversing trees in pre-order recursively in PHP](https://swww.com.pl/media/img/post/41_head.jpg)
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
Author, Copyright and citation
Author
![Sylwester Wojnowski](https://swww.com.pl/media/img/gravatar_110.png)
Author of the this article - Sylwester Wojnowski - is a sWWW web developer. He has been writing computer code for the websites and web applications since 1998.
Copyrights
©Copyright, 2024 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://swww.com.pl//main/index/traversing-trees-in-pre-order-recursively-in-php
Add Comment