» Convert anything to Tree Structures in PHP

3 Tree Manipulation

PHP Recursive functions

Yep, that's a tree alright.In real life I do not consider myself to be a tree-hugger, but as a developer: tree data structures and recursive technology totally get me going ;) Seriously though, they are very powerful ways to solve problems and often lead to elegant & reusable solutions.

In this series I am going to share a couple of functions and ways of approaching recursive problems in PHP.

On twitter

I recently faced a programming challenge that almost broke my brain. I needed to create a function that could explode any single-dimensional array into a full blown tree structure, based on the delimiters found in it's keys. Tricky part was size of the tree could be infinite. I called the function: explodeTree. And maybe it's best to first look at an example.

The Directory Example

Here I will give an example what the explodeTree function could be used for. Let's say we need a recursive directory listing of /etc/php5, and for that we execute:

if(exec("find /etc/php5", $files)){
    // the $files array now holds the path as it's values,
    // but we also want the paths as keys:
    $key_files = array_combine(array_values($files), array_values($files));
 
    // show the array
    print_r($key_files);
}

Which will return something like:

Array
(
    [/etc/php5] => /etc/php5
    [/etc/php5/cli] => /etc/php5/cli
    [/etc/php5/cli/conf.d] => /etc/php5/cli/conf.d
    [/etc/php5/cli/php.ini] => /etc/php5/cli/php.ini
    [/etc/php5/conf.d] => /etc/php5/conf.d
    [/etc/php5/conf.d/mysqli.ini] => /etc/php5/conf.d/mysqli.ini
    [/etc/php5/conf.d/curl.ini] => /etc/php5/conf.d/curl.ini
    [/etc/php5/conf.d/snmp.ini] => /etc/php5/conf.d/snmp.ini
    [/etc/php5/conf.d/gd.ini] => /etc/php5/conf.d/gd.ini
    [/etc/php5/apache2] => /etc/php5/apache2
    [/etc/php5/apache2/conf.d] => /etc/php5/apache2/conf.d
    [/etc/php5/apache2/php.ini] => /etc/php5/apache2/php.ini
)

Now if we want to transform this list into a tree structure with each directory as a nested node, a child of another directory, all we would have to do is run:

// let '/' be our delimiter
$tree = explodeTree($key_files, "/");
// show the array
print_r($tree);

And that single command would give the totally awesome:

Array
(
    [etc] => Array
        (
            [php5] => Array
                (
                    [cli] => Array
                        (
                            [conf.d] => /etc/php5/cli/conf.d
                            [php.ini] => /etc/php5/cli/php.ini
                        )
 
                    [conf.d] => Array
                        (
                            [mysqli.ini] => /etc/php5/conf.d/mysqli.ini
                            [curl.ini] => /etc/php5/conf.d/curl.ini
                            [snmp.ini] => /etc/php5/conf.d/snmp.ini
                            [gd.ini] => /etc/php5/conf.d/gd.ini
                        )
 
                    [apache2] => Array
                        (
                            [conf.d] => /etc/php5/apache2/conf.d
                            [php.ini] => /etc/php5/apache2/php.ini
                        )
 
                )
 
        )
 
)

Wow! So this would make it very easy to visually layout a tree structure of the directory /etc/php5. But remember this is just an example. The function now explodes on the '/' character, but you can use any delimiter to explode a single-dimensional array into a Tree. So how does this explodeTree function work?

The Function: explodeTree()

The key to my original approach was not to use static PHP code, but to generate PHP code, and to later execute it using the eval() function. Though it did the job  and posed an fresh approach to the problem, I wouldn't be surprised if someone told me that the piece of code secretly spawned gateways to hell ;)

My blog visitors agreed on the evil part and came with other neat approaches. Now thanks to Lachlan Donald and Takkie, here's the new explodeTree() function.

<?php
/**
 * Explode any single-dimensional array into a full blown tree structure, 
 * based on the delimiters found in it's keys.
 * 
 * @author    Kevin van Zonneveld <kevin@vanzonneveld.net>
 * @author    Lachlan Donald
 * @author    Takkie
 * @copyright 2008 Kevin van Zonneveld (http://kevin.vanzonneveld.net)
 * @license   http://www.opensource.org/licenses/bsd-license.php New BSD Licence
 * @version   SVN: Release: $Id: explodeTree.inc.php 89 2008-09-05 20:52:48Z kevin $
 * @link      http://kevin.vanzonneveld.net/
 * 
 * @param array   $array
 * @param string  $delimiter
 * @param boolean $baseval
 * 
 * @return array
 */
function explodeTree($array, $delimiter = '_', $baseval = false)
{
    if(!is_array($array)) return false;
    $splitRE   = '/' . preg_quote($delimiter, '/') . '/';
    $returnArr = array();
    foreach ($array as $key => $val) {
        // Get parent parts and the current leaf
        $parts    = preg_split($splitRE, $key, -1, PREG_SPLIT_NO_EMPTY);
        $leafPart = array_pop($parts);
 
        // Build parent structure 
        // Might be slow for really deep and large structures
        $parentArr = &$returnArr;
        foreach ($parts as $part) {
            if (!isset($parentArr[$part])) {
                $parentArr[$part] = array();
            } elseif (!is_array($parentArr[$part])) {
                if ($baseval) {
                    $parentArr[$part] = array('__base_val' => $parentArr[$part]);
                } else {
                    $parentArr[$part] = array(); 
                }
            }
            $parentArr = &$parentArr[$part];
        }
 
        // Add the final part to the structure
        if (empty($parentArr[$leafPart])) {
            $parentArr[$leafPart] = $val;
        } elseif ($baseval && is_array($parentArr[$leafPart])) {
            $parentArr[$leafPart]['__base_val'] = $val;
        }
    }
    return $returnArr;
}
?>

The first to arguments of explodeTree() are clear I guess. But what about that 3rd parameter: $baseval?

The baseval argument

In the first example you see that only leafs (the bottom nodes that don't have any children) maintain their original values (the filepaths in this case). If you want higher nodes (parents) to also maintain their values, you'll have to tell explodeTree to do so like this:

// now the 3rd argument, the baseval, is true
$tree = explodeTree($key_files, "/", true);

And then explodeTree will preserve the node's original value in the __base_val items. Like this:

Array
(
    [etc] => Array
        (
            [__base_val] => 
            [php5] => Array
                (
                    [__base_val] => /etc/php5
                    [cli] => Array
                        (
                            [__base_val] => /etc/php5/cli
                            [conf.d] => /etc/php5/cli/conf.d
                            [php.ini] => /etc/php5/cli/php.ini
                        )
 
                    [conf.d] => Array
                        (
                            [__base_val] => /etc/php5/conf.d
                            [mysqli.ini] => /etc/php5/conf.d/mysqli.ini
                            [curl.ini] => /etc/php5/conf.d/curl.ini
                            [snmp.ini] => /etc/php5/conf.d/snmp.ini
                            [gd.ini] => /etc/php5/conf.d/gd.ini
                        )
 
                    [apache2] => Array
                        (
                            [__base_val] => /etc/php5/apache2
                            [conf.d] => /etc/php5/apache2/conf.d
                            [php.ini] => /etc/php5/apache2/php.ini
                        )
 
                )
 
        )
 
)

See what happens? Baseval creates a placeholder. A semi-node for the original value of it's parent. The value: '/etc/php5' is now saved, without baseval this value would be lost because there was no place to store it in. Now that might come in handy!

So you've got a tree. Now what?

Trees with unlimited levels of nodes require recursive functions that can traverse the entire structure. Recursive functions are functions that call themselves every time they find more items to process. Here's one to layout the directories:

function plotTree($arr, $indent=0, $mother_run=true){
    if($mother_run){
        // the beginning of plotTree. We're at rootlevel
        echo "startn";
    }
 
    foreach($arr as $k=>$v){
        // skip the baseval thingy. Not a real node.
        if($k == "__base_val") continue;
        // determine the real value of this node.
        $show_val = ( is_array($v) ? $v["__base_val"] : $v );
 
        // show the indents
        echo str_repeat("  ", $indent);
        if($indent == 0){
            // this is a root node. no parents
            echo "O ";
        } elseif(is_array($v)){
            // this is a normal node. parents and children
            echo "+ ";
        } else{
            // this is a leaf node. no children
            echo "- ";
        }
 
        // show the actual node
        echo $k . " (".$show_val.")"."n";
 
        if(is_array($v)){
            // this is what makes it recursive, rerun for childs
            plotTree($v, ($indent+1), false);
        }
    }
 
    if($mother_run){
        echo "endn";
    }
}

And this would output:

start
O etc ()
+ php5 (/etc/php5)
+ cli (/etc/php5/cli)
- conf.d (/etc/php5/cli/conf.d)
- php.ini (/etc/php5/cli/php.ini)
+ conf.d (/etc/php5/conf.d)
- mysqli.ini (/etc/php5/conf.d/mysqli.ini)
- curl.ini (/etc/php5/conf.d/curl.ini)
- snmp.ini (/etc/php5/conf.d/snmp.ini)
- gd.ini (/etc/php5/conf.d/gd.ini)
+ apache2 (/etc/php5/apache2)
- conf.d (/etc/php5/apache2/conf.d)
- php.ini (/etc/php5/apache2/php.ini)
end

If I overlooked a standard PHP function that can already do this, or you have other improvements/ideas leave a comment!

Thanks again: Lachlan Donald & Tokkie for insightful comments and great effort.

Stay up to date

You can track my blog rss articles and rss comments. You may also find my rss bookmarks interesting. Or twitter Follow me on Twitter


Like this article?

   Then Digg it!
Or use another bookmark button below to show your support &
help me spread the word.


tags: php, programming, recursion, hierarchy, tree data structure, array, delimiter
category: Programming - PHP - Tree Manipulation
read: 51,099 times

Add comment

(required, shown)(required, not shown)for syntax highlighting

[CODE="Javascript"]
your_code_here();
[/CODE]

Replace "Javascript"
with "php", "text", etc.
code (to make sure you are not a spammer)

 Track replies: rss feed comments feed

Comments

#35. Alex on 28 February 2010

Gravatar.com: AlexThanks Kevin, this is great and almost what I've been looking for! :)

I'm having a hard time trying to add nodes to a children array inside the parent instead of adding then directly.

If you wouldn't mind I could really use the help! Thanks! :)
... [more]
Alex

#34. Kevin on 28 February 2010

Twitter.com: kvz@ Tang: Haven't used it with jQuery Treeview yet, but I'm sure some people will find your info useful. Thanks!

#33. Tang on 27 February 2010

Gravatar.com: TangThis is a good source of solution.. It is exactly what I am looking for to expand a treeview... Thanks Kevin ..

Also I've used Ash Ketchum on 27 July 2009 codes to combine it with the jQuery Treeview ..Big thanks to Ash that save huge amount of my time ... :-)

Not sure if some of you came accross a problem in IE6 when implementing the codes with the jQuery treeview.(It works fine with Firefox and Opera). The expanded list become transparent (or disappear) when expanded.. If you do, try remove the html comment tags (example : <!--subfolder-->) in the codes.. I removed it and solved the disssapearing list in IE6...
... [more]
Kevin and Ash save me lots of time (big thanks to you guys), so I hope my finding could help someone else save their time as well..

#32. Kevin on 04 September 2009

Twitter.com: kvz@ Shubhadeep: That's way to much credit : )

#31. Shubhadeep on 31 August 2009

Gravatar.com: ShubhadeepYou are a GOD to me :)

#30. Kevin on 28 July 2009

Twitter.com: kvz@ Ash Ketchum: Very kind of you to share Ash, thank you very much.
I do think there's an issue when your array has identical values though as it seems you're checking if it's the last item by checking it's value.
It may be better to use a counter or sth.

Wouldn't it be possible to modify the plotTree() function to use tags instead of symbols like + and - ?

#29. Ash Ketchum on 27 July 2009

Gravatar.com: Ash KetchumThanks for this awesome function. Just what I was looking for.

But I had a really hard time trying to get the array to display the way I wanted (In an unordered list, so that I can make a nice graphical tree out of it using css). Anyway, I came up with the following function, which displays the array contents in an unordered list.

function plotNewTree($array, $is_sub = false, $first_run = true) {
if ($first_run) {
echo "<ul class=\"contents\">\r\n";
}

$items = count($array);
$lastval = end($array);
// apparently the following may not work as expected. but works for me :D
$lastkey = end(array_keys($array));

foreach($array as $key=>$value) {
if($key == "__base_val") continue;

if ($is_sub && is_array($value)) {
if ($lastval == $value) {
echo "<ul class=\"subfolder lastnode\">\r\n";
} else {
echo "<ul class=\"subfolder\">\r\n";
}
}

if ($first_run || ($is_sub && is_array($value))) {
if ($first_run && !is_array($value) && $items == 1) {
$file_ext = pathinfo(basename($key), PATHINFO_EXTENSION);
echo "<li><span class=\"file ext-$file_ext\">$key</span>\r\n";
} else if ($lastval == $value) {
echo "<li class=\"lastnode\"><span class=\"folder\">$key</span>\r\n";
} else {
echo "<li><span class=\"folder\">$key</span>\r\n";
}
}

if (is_array($value)) {
plotNewTree($value, true, false);
if ($is_sub && is_array($value)) {
echo "</li></ul><!--subfolder-->\r\n";
}
}

if (!$first_run && !is_array($value)) {
if (!isset($firstfiledone)) {
echo "<ul class=\"files\">\r\n";
}
$firstfiledone = true;
$file_ext = pathinfo(basename($key), PATHINFO_EXTENSION);
if ($value == $lastval && $key == $lastkey) {
echo "<li class=\"lastnode\"><span class=\"file ext-$file_ext\">$key</span> (".bytestostring($value).")</li>\r\n";
echo "</ul><!--files ul-->\r\n";
} else {
echo "<li><span class=\"file ext-$file_ext\">$key</span> (".bytestostring($value).")</li>\r\n";
}
}
 
}

if ($first_run) {
echo "</li></ul>\r\n";
}
}


The "bytestostring" function (which I came across in another site) formats file size in bytes to a string like "1.56 MB". Here's the "bytestostring" function.

function bytestostring( $size,$precision = 2 ) {
$sizes=array( 'YB','ZB','EB','PB','TB','GB','MB','KB','Bytes' );
$total=count( $sizes );
 
while( $total-- && $size > 1024 ) $size /= 1024;
return round( $size,$precision )." ".$sizes[$total];
}


Anyway, thanks again Kevin.

#28. Kevin on 25 July 2009

Twitter.com: kvz@ Morten Slott Hansen & Sandro Frenzel: Thanks for the kind words.

#27. Sandro Frenzel on 17 July 2009

Gravatar.com: Sandro FrenzelThanks for this create article! I was searching a long time to create a treeview like this http://jquery.bassistance.de/treeview/demo/?1

I simply add some HTML-Tags to generate the right structure and it works!

Great!
... [more]
Thank you for sharing your knowledge :))!

#26. Morten Slott Hansen on 10 July 2009

Gravatar.com: Morten Slott HansenIndeed awesome stuff - Have been trying something like this the whole week and have so far been unsuccessful - this just saved my entire week!
Now I can finally make a WEB frontend for digikam!

#25. Kevin on 26 June 2009

Twitter.com: kvz@ Andrei: You could write a recursive function that uses UL and LI HTML elements. You could have a look at the plotTree() function above for inspiration, google for one, or have a hack at it :)

#24. Andrei on 18 June 2009

Gravatar.com: AndreiGreat function plotTree. I want to use it on a table witch looks like this:
id | id_parent | page
1 | 0 | home
2 | 1 | page1
3 | 0 | page2
... [more] 4 | 1 | page3
5 | 3 | page4
6 | 1 | page5
7 | 4 | page6
8 | 7 | page7
9 | 5 | page8
Using this table I want to generate a sitemap. Cand someone give me a hint?

#23. Kevin on 18 June 2009

Twitter.com: kvz@ Matt: Thanks for sharing!

#22. Matt on 17 June 2009

Gravatar.com: MattGreat function, I've used it a few times. I agree that with many problems where it seems my brain is about to break I realize that this is probably the solution.
The only thing I needed to add was a limit parameter for a recent project but it was easy as all that was changed was the -1 to a default of $limit=-1 on the preg_split.

Thanks!

#21. EllisGL on 17 October 2008

Gravatar.com: EllisGLI found this while trying to figure out what kind of tree scheme PHP array's use, so I can do multidimensional associative arrays in C/C++ like PHP does.

#20. Kevin on 10 September 2008

Twitter.com: kvz@ steve: My mistake, fixed it. Thanks for telling me!

#19. steve on 09 September 2008

Gravatar.com: steveI read your article with great interest, but it looks like the actual code for the function in included on your site via a non-valid url in PHP.

I get this:
/var/www/web5/web/code/kvzlib/code/php/functions/explodeTree.inc.php

... [more] instead of the script. Any chance I can peek at this code? ;-)

#18. Robert on 06 May 2008

Default avatar:RobertYou may have saved my life... I was thinking of killing myself because I had some seriously problems with getting this to work! Thanks!

#17. Emacs on 06 April 2008

Default avatar:EmacsNice snippet :) Thanks a lot ^^

#16. http://www.sezgioto.com on 26 December 2007

Default avatar:http://www.sezgioto.comthanks man

#15. Takkie on 12 October 2007

Default avatar:Takkie@ Kevin: Thanks, but my site first needs to contain some content before anybody should link to it ;)

#14. Kevin on 12 October 2007

Default avatar:Kevin@ Lachlan: I've included a link to your site.
@ Takkie: If you have site you want listed here just say so.

#13. Lachlan on 12 October 2007

Default avatar:Lachlan@Takkie Oh your right, it is order dependent :) Although my code doesn't generate notices, the isset guard in it should prevent those.

Although not quite as succinct, here is a version that works with any array order:

function expand($array,$delim='/')
... [more] {
$newArray = array();
$delim = preg_quote($delim,'/');

foreach($array as $key=>$value)
{
$current = &$newArray;
$stack = preg_split("/$delim/",$key,-1,PREG_SPLIT_NO_EMPTY);

// iterate down the array, leaving $current as the leaf
foreach($stack as $item)
{
// clobber leafs, replace this for baseval support
if(isset($current[$item]) && !is_array($current[$item]))
{
$current[$item] = array();
}

$current =& $current[$item];
}

// don't overwrite existing branches
if(!is_array($current) || count($current) == 0)
{
$current = $value;
}
}

return $newArray;
}

I haven't implemented baseval support, but it would be fairly straightforward, see the comments in the inner for loop.

- Lachlan Donald http://www.lachlandonald.com

#12. Kevin on 10 October 2007

Default avatar:Kevin@ Takkie: I think we all agree on the evil part ;)

But that's some awesome code you wrote. I've updated the article and replaced the original function with yours.
Thanks a lot you guys, you've really contributed powerful stuff.

#11. Kevin on 10 October 2007

Default avatar:Kevin@ Craig: Your function is indeed good for the pure purpose of recursively indexing a directory. However, I feel that the explodeTree() function is more generic and could be used for a lot of other things as well. Thanks for your comment.

#10. Takkie on 10 October 2007

Default avatar:TakkieI agree with lachlan on the evil eval part. Besides that your code depends heavily on the given array being sorted (parents first), which conflicts with your goal: explode _any_ single-dimensional array into a tree.The code lachlan proposes also depends on the same ordering btw.

Also, your code makes use of undefined variables and indices. Just for fun: add shuffle($files); right after if(exec("find /etc/php5", $files)){ and run the code with a configuration that shows notices.


... [more] Another possible solution could be (independend of ordering):

function explodeTree($array, $delimiter = '_', $baseval = false)
{
$splitRE = '/' . preg_quote($delimiter, '/') . '/';
$returnArr = array();
foreach ($array as $key => $val) {
// Get parent parts and the current leaf
$parts = preg_split($splitRE, $key, -1, PREG_SPLIT_NO_EMPTY);
$leafPart = array_pop($parts);

// Build parent structure (might be slow for really deep and large structures)
$parentArr = &$returnArr;
foreach ($parts as $part) {
if (!isset($parentArr[$part])) {
$parentArr[$part] = array();
} elseif (!is_array($parentArr[$part])) {
$parentArr[$part] = $baseval ? array('__base_val' => $parentArr[$part]) : array();
}
$parentArr = &$parentArr[$part];
}

// Add the final part to the structure
if (empty($parentArr[$leafPart])) {
$parentArr[$leafPart] = $val;
} elseif ($baseval && is_array($parentArr[$leafPart])) {
$parentArr[$leafPart]['__base_val'] = $val;
}
}
return $returnArr;
}

#9. Craig Francis on 10 October 2007

Default avatar:Craig FrancisAlthough your implementation does seem to work on a more general setup, when it comes to listing a directory, I do prefer to use the native directory listing functions (not 'eval'), which work on all operating systems, and in this case, with a recursive function call.


<?php

... [more] function printFolder($folder, $prefix = '') {

$folder = str_replace('\\', '/', $folder);
if (substr($folder, -1) != '/') {
$folder .= '/';
}

if ($handle = opendir($folder)) {
while (false !== ($file = readdir($handle))) {
if (!preg_match('/^\./', $file)) {

if (is_dir($folder . $file)) {

echo $prefix . '+ ' . $file . "\n";

printFolder($folder . $file . '/', ' ' . $prefix);

} else {

echo $prefix . '- ' . $file . "\n";

}

}
}
closedir($handle);
}

}

printFolder('/etc/php5/');

?>

#8. Kevin on 10 October 2007

Default avatar:Kevin@ Andrew: Thanks, But this article aims at forming tree structures, not breaking them down (into single-dimensional arrays).
And yes, such a tree could be passed on nicely with serialize, but that's a bit outside this article's scope.

#7. Kevin on 10 October 2007

Default avatar:Kevin@ lachlan: Wow that's an awesome piece of code! I totally agree that my way is evil, nevertheless it does the trick and I think it brings an interesting approach.

I would like to include your function in this article however, shall I credit it to: 'lachlan' ?

btw, yours currently does not have a real 'baseval' replacement. In the original function baseval is used to store the values of parent nodes as well as leafs. In the example look at: '/etc/php5', this value isn't saved by expand().
... [more]
Thanks for your effort!

#6. Andrew on 10 October 2007

Default avatar:AndrewIt's a bad idea to pass around trees represented as 'single-dimensional arrays', consider something like XML, JSON, or serialized arrays.

If you haven't already, take a look at RecursiveIterators (SPL) and SimpleXML.

http://cvs.php.net/viewvc.cgi/php-src/ext/spl/examples/

#5. lachlan on 10 October 2007

Default avatar:lachlanUsing eval like this is really, really evil. Not to mention slow and error prone. This sort of usage results in evals bad reputation as its so easy to make a mistake and end up with a remote code execution bug.

Try this:

function expand($array,$delim='/')
... [more] {
$newArray = array();
$delim = preg_quote($delim,'/');

foreach($array as $key=>$value)
{
$current = &$newArray;
$stack = preg_split("/$delim/",$key,-1,PREG_SPLIT_NO_EMPTY);

// iterate down the array, leaving $current as the leaf
foreach($stack as $item)
{
// this actually clobbers non-leafs, replace for baseval
if(isset($current[$item]) && !is_array($current[$item]))
{
$current[$item] = array();
}
$current =& $current[$item];
}

// set the leaf value
$current = $value;
}

return $newArray;
}

#4. Kevin on 09 October 2007

Default avatar:Kevin@ Charles + guigouz: I gave it some more thought and you'll be happy to know that I've changed the article. I hope this will make the it a bit easier on the eyes and it may illustrate the need for such a function better. Thanks guys.

#3. Kevin on 09 October 2007

Default avatar:Kevin@ Charles: You're right. In that specific example there are other ways to do it. So maybe I'll replace it with something else.
However the example's main purpose is to illustrate how the function works and just one of it's many possible uses. My first thought was to use the POST example because everyone is familiar with that technology. Thanks for your comment, I'll think about updating the article.

#2. guigouz on 09 October 2007

Default avatar:guigouzyou know you can use something like
<input type="text" name="serverinfo[1][hostname]"/>
<input type="text" name="serverinfo[2][ip_address]"/> ?

even if you use multiple name="serverinfo[]" attrs php will turn those in an ordered array

#1. Charles on 09 October 2007

Default avatar:CharlesHuh?

You don't need a function for this.

Since PHP3 or so, PHP automagically turns input into arrays if you use square brackets.
... [more]
&lt;input name="serverinfo[1][hostname]" value="server1.example.com" />
&lt;input name="serverinfo[1][ipaddress]" value="123.123.123.123" />
&lt;input name="serverinfo[2][hostname]" value="server2.another.com" />
&lt;input name="serverinfo[2][ipaddress]" value="234.234.234.234" />