Convert Anything to Tree Structures in PHP

Huh?

You don\'t need a function for this.

Since PHP3 or so, PHP automagically turns input into arrays if you use square brackets.

<input name=\"serverinfo[1][hostname]\" value=\"server1.example.com\" />
<input name=\"serverinfo[1][ipaddress]\" value=\"123.123.123.123\" />
<input name=\"serverinfo[2][hostname]\" value=\"server2.another.com\" />
<input name=\"serverinfo[2][ipaddress]\" value=\"234.234.234.234\" />

you 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

@ 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.

@ 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.

Using 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=\'/\')
{
$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;
}

It\'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.c...

@ 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().

Thanks for your effort!

@ 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.

Although 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

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/\');

?>

I 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.

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;
}

@ 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.

@ 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.

@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=\'/\')
{
$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

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

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

thanks man

Nice snippet :) Thanks a lot ^^

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

I 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

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

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

I 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.

Great 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!

@ Matt: Thanks for sharing!

Great 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
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?

@ 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 :)

Indeed 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!

Thanks for this create article! I was searching a long time to create a treeview like this http://jquery.bassistance.d...

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

Great!

Thank you for sharing your knowledge :))!

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

Thanks 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.

[CODE=\"php\"]
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\";
}
}
[/CODE]

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.

[CODE=\"php\"]
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];
}
[/CODE]

Anyway, thanks again Kevin.

@ 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 - ?

You are a GOD to me :)

@ Shubhadeep: That\'s way to much credit : )

This 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...

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..

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

@ Alex: Hey, could you provide a code sample of what you are trying to do? That would help a lot. thx

This is a nice article, I found a similar one at a Django website. but it wasn\'t about PHP. It was about Django which is for Python. Python is good too, but Django takes a bit more learning than Python.

http://www.nuovolabs.com was the website but I can\'t find the actual URL to the article now.

Kevin,
the script that you have provided is awesome! I did get stuck a bit though and wonder if you can give me an idea of how to proceed. In essence, I have 2 arrays as per below where the array_values of array1 are key for array2. I need to break it down on categories and subcategories as well as sum up and roll the totals from array2 leaf categories into parent categories. The output that I am trying to get would look similar to:

o FX (sum of all the previous levels: FX)
+ FX (sum of all of the previous levels: EBSS & HT)
- EBSS (sum of all the corresponding leaf nodes from array2)
- HT (sum of all the corresponding leaf nodes from array2)
o IR (sum of BOND & FUT levels)
+ BOND (sum of all the corresponding levels: BTest & CME)
+ FUT (sum of all the corresponding levels: BTest & CME)
- BTest (sum of all the corresponding leaf nodes from array2)
- CME (sum of all the corresponding leaf nodes from array2)

Array
(
[0] => FX###FX###EBSS
[1] => FX###FX###EBSS
[2] => FX###FX###HT
[3] => FX###FX###HT
[4] => IR###BOND###BTest
[5] => IR###FUT###CME
[6] => IR###BOND###BTest
[7] => IR###FUT###CME
[8] => IR###BOND###BTest
[9] => IR###FUT###CME
[10] => IR###FUT###CME
[11] => IR###FUT###CME
[12] => IR###FUT###CME
)
Array
(
[0] => 0|3|6|530240000|-0|-0|-0|-0|0|0|
[1] => 0|3|6|8116100|-24.3483|-60.87075|-0|-0|-300|-385.21905|
[2] => 1|4|7|9468090|-28.40427|-47.34045|-0|-0|-1351670|-1351745.74472|
[3] => 0|3|6|6119940|-18|-30|-0|-0|0|-48|
[4] => -1|2|5|4889062.5|-0|-0|-10|-0|977500|977490|
[5] => 0|47|94|10926281.32|-5.64|-23.5|-7.52|-0|31.24|-5.42000000001|
[6] => 0|4|8|7867656.25|-0|-0|-16|-0|-156.25|-172.25|
[7] => 0|3|6|696375|-0.36|-1.5|-0.48|-0|0|-2.34|
[8] => 0|2|4|3893281.25|-0|-0|-8|-0|-468.75|-476.75|
[9] => 4|5|6|695812.5|-0.36|-1.5|-0.48|-0|-463750|-463752.34|
[10] => 3|17|31|3609250.13|-1.86|-7.75|-2.48|-0|-348625.01|-348637.1|
[11] => -3|0|3|348218.75|-0.18|-0.75|-0.24|-0|348218.75|348217.58|
[12] => -4|0|4|465453.14|-0.24|-1|-0.32|-0|465453.14|465451.58|
)

function my_debug($arr)
{
echo \'<pre>\';
print_r($arr);
echo \'</pre>\';
}
function xml2arr($file)
{

if(file_exists($file))
$handle=fopen($file,\'r\');
else
print \"file does not exists\";
$xml = fread($handle, filesize($file));
fclose($handle);

$xml = new SimpleXMLElement($xml);
//my_debug($xml);
return $xml;
}
$file=\'Test_reo_precision_nonprime_req_20100525113003_01.xml\';
$arr=xml2arr($file);
my_debug($arr);

@ Django Developers: Thanks for sharing though!

@ Ringo: You\'d have to pay me for such a thing ; ) Oh wait, already have a job, sorry

@ ali: Not making any sense to me?

I need a family tree/pedigree chart made from the hierarchial nodes I have on my site. Would you be able to help with that?

@ Karen: Well I\'m not for hire at the moment, but maybe you could have a look at Graphviz? They have a simple language that you can build such charts with.

Hi,
I created my site with Drupal and did look at Graphviz a while back, but couldn\'t get it to install. I can try again. I have all the data and all my nodes connected, I just need an output report. I have tried views, but can\'t get lines/boxes etc. and can only display the parent and children, not the children of the children and the children of their children, etc. I am using Node Hierarchy. Node Hierarchy displays a really nice outline, but it is in the navigation window and I don\'t know how to put it on a page. It also lists every node in the database, not just the node associated with related nodes. I have asked for repeated request for help, offered money and no takers. If you change your mind, let me know.

@Karen: I'm getting pretty close at thebookofross.com (lamp platform). I'm dan at ross dash clan dot net.

@ Karen: Looks like Dan is interested to help you out. If not, graphviz can be installed like this on Ubuntu:
[CODE="BASH"]
aptitude install graphviz
[/CODE]

then you need bindings for your programming language. For PHP:

[CODE="BASH"]
pear install -f Image_GraphViz
[/CODE]

There are some examples online of how to call the class next.

Thanks for this, saved me a lot of work! Very handy to turn an alphabetical list of URLs into a ol/ul sitemap tree

Great peace of code! Thank You!

Great Work boss,really helpful :)

Very good article.
Must be from Amsterdam ;-).

@ Hans: Si Señor : )

Thank you so much, great code! :P

Thanks for posting the explodeTree function, very handy as well as avoiding the headaches of dealing with multi-dimensional arrays!

I've implemented a more compact (less versatile) version of explodeTree as part of a wider preorder tree traversal script that puts data into MySQL. I've tested it with the root of my drive (200K filenames) and the DMOZ category RDF (~700K category names), simply bumping up the memory limit does the trick ;o)

For reference my script is here http://www.innvo.com/c/PHP/... ... credits to you are in the comments and a link to this page.

This is what I'm loking for a 3 day and for some reason it dosen't work why??? this code dosen't work below... sou you see I'm using my ovn directorys path and I don't know why it dosen't work ...can you help :)

if(exec("store/555555", $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);
}

Very usefull one. i needed to do something similliar and almost shat my pants untill i saw this one.
Thanks m8

I hate to resurrect this article almost 3 years later, but it seems like the __base_val code does not work in your posted code. I've been trying to work through why that may be but I've come up with nothing. It simply never reaches the if-statement where we check if $baseval is set to true. I can prove that the $baseval is being passed to the function correctly but it seems to not be triggering if-statements further down in the code.

I'm sure I am missing something but I have very little experience with PHP's idiosyncrasies. In general code sense I feel the program should be working and I cannot understand why it is failing.

Any thoughts? I'd assume this code works with PHP5 since I'm running it under that, but could it have introduced quirks that might be causing my issue?

Found the problem.

When setting __base_val, we require the folders to be in the format "/etc/php5". This means if you use a "find ./ -type f" to populate your array __base_val will never be set. This could probably be fixed in the explodeTree code but in my case it's easier to just populate the array with more/better information.

Even tho' its years later, your article helped me a lot, and I just want to thank you -so very much-, Kevin, for your article and especially that bit about baseval.

After I melted my brain trying to figure out how to apply recursive spl methods, and especially trying to hunt down what I figured I must be missing about nailing the parent-child node relationship, this was a huge validator, and liberator, for me.

I had basically arrived at the realization, but not being versed well enough in php, I was sure I was over looking something - that I hunted days for and never found!

I wrote a script for iterating a directory for use with Alf's dhtmlgoodies Folder Tree project (which handles flat files or database input, but not a live directory). Its an old project, but that made the excersize valuably interesting.

I am uncertain about presuming to post a code-load here, but I am happy to share it if there's interest.

For now, just a shout back- thanks again.
twohawks

I'm really fond of your coding and need some help too I'm also trying to make a tree and save it in an xml file such that parent_id of one node is inserted in as pages key to the father node.By running this query
$sql = "Select * from category order by parent_id ASC";
I'm getting the following result.
Array
(
[0] => Array
(
[category_id] => 2
[parent_id] => 0
[category_name] => Clothes
)

[1] => Array
(
[category_id] => 5
[parent_id] => 1
[category_name] => T-shirts
)

[2] => Array
(
[category_id] => 6
[parent_id] => 1
[category_name] => Cotton-Shirts
)

[3] => Array
(
[category_id] => 1
[parent_id] => 2
[category_name] => Upper
)

[4] => Array
(
[category_id] => 4
[parent_id] => 2
[category_name] => Lower
)

[5] => Array
(
[category_id] => 3
[parent_id] => 4
[category_name] => Pants
)

)

My code is as follows but not executing correctly
function searchTree($arr,$node,$i){
if(!in_array($node['parent_id'],$arr[$i])) {
$stmt = '<pages_'.$i.'>';
$stmt .=$node;
$stmt .='</pages_'.$i.'>';
return $stmt;}
else{
//print_r($returnTree);
print_r ($arr[$i]);//['category_id'];
$returnTree = ($arr[$i]['category_id']==$node['parent_id'])?
searchTree($arr,$node,$i++): searchTree($arr,'',$i++);
}
}
$i=0;
foreach($links as $link){
$myArr = searchTree($links,$link,$i);}

The result should be as follows:
<page_1>
<label>Clothes</label>
<uri>#</uri>
<pages>

<page_1_1>
<label>Upper</label>
<uri>#</uri>
<pages>
<label>T-Shirt</label>
<uri>#</uri>
<page_1_1>
<page_1_1_1>
<label>Short Sleaves</label>
<uri>#</uri>
</page_1_1_1>
<page_1_1_2><label>Long Sleaves</label><uri>#</uri>
</page_1_1_2></page_1_1></page_1>
<page_1_2>
<label>Lower</label>
<uri>#</uri>
<pages>....</page_1_2>

Hopefully you can unsderstand this problem. Please help me.

Thanks a million, those Tree functions are very very good.
I also had errors with "find ./" and kinda worked around it with this:
[CODE="php"]
if(exec("find ".getcwd()."/" , $files)){
$files = substr_replace($files, "", 0, ( strlen(getcwd()) +1) );
$files = array_combine(array_values($files), array_values($files));
}
// and set baseval to true:
$tree = explodeTree($files, "/", true);
[/CODE]