This example seems to assume a maximum of two children. Does the code also work if you have many more child nodes per each parent as you would with a nested discussion forum?
| SitePoint Sponsor |
This example seems to assume a maximum of two children. Does the code also work if you have many more child nodes per each parent as you would with a nested discussion forum?
I posted this into another thread about nested sets and categories.
http://www.sitepoint.com/forums/show...7&postcount=10
The class file in my post might be useful to some people.
Retrieve correct node with node values are not unique
To retrieve single path to 'banana' you would use the following query
however this won't work if we had 'banana' in more than one node.Code:SELECT p.title FROM tree1 AS node, tree1 AS p WHERE node.lft BETWEEN p.lft AND p.rgt AND node.title = 'banana' ORDER BY p.lft;
If the values of all nodes from one of the bananas were known can the right 'banana' be found with one query?
Is there a way to retrieve only nodes of the same level (depth), but all of them, no matter if their parents are different?
In the example above, if I'd like to have all nodes only from depth of 3 (result would be: red, yellow, beef, pork), how can this be achieved?
@p3t3r
The article mentions basic database normalization, which means you would be referring to a unique node id. Titles are used as examples for simplicity. Using an id will solve your problem.
@Anonymous
Check out the display_tree() function. The indentation, which is based on the node level, is calculated by using the stack size. Use that information to restrict which nodes you display.
Great article, it certainly helped me with a album project. But, I cant seem to figure out a way to put this into a multi-dimensional array as opposed to just displaying it. Anyone know how?
I did exactly that but my code is all a big object-oriented re-construction of this article and i cant really post it all here. Hoping you are smart enough to figure it out, I can sorta give you a pseudo-code of my approach:Originally Posted by TNK
..something like that. But take note of the additional method, I basically defined and object structure to represent a tree node.PHP Code:function get_array_tree($master_node = null){
$root_node = $master_node;
function child_parse($node){
if(!$node->is_end_node()){
$branch = array($node->title);
if($node->has_children()){
$children = $node->children;
while($child = array_shift($children)){
$branch[] = child_parse($child);
}
}
return $branch;
}else{
return $node->title;
}
}
$tree = child_parse($master_node->first_child);
return array($root_node->title,$tree);
}
Hmmm ... I tried your code, changing the field names, in a mysql table having 89 rows, which instead of showing 1 and 178 as lft and rgt values of root respectively, shows me 1 and 127. By further inspection, I found that this has caused as many of the entries got lft and rgt values as (same) 127, whereas some getting the same rgt value (127) having different lft values.
Strange !!! (It has many levels and sublevels, probably that's causing the issue here !!!)
Code PHP:function rebuild_tree($parent, $left) { $right = $left+1; $result = mysql_query('SELECT id FROM menu_management '. 'WHERE parent_menu='.$parent); while ($row = mysql_fetch_array($result)) { $right = rebuild_tree($row['id'], $right); } mysql_query('UPDATE menu_management SET lft='.$left.', rgt='. $right.' WHERE id='.$parent); return $right+1; } rebuild_tree(1,1);
Viz. (order by id asc)
id | pm | lt | rt
174 | 1 | 122 | 127
175 | 174 | 123 | 127
178 | 174 | 127 | 127 (176 and 177 doesn't exist in the db)
184 | 1 | 127 | 127 (ids between 178 and 184 doesn't exist)
Hmmmm ... my mistake or bug in the code / table !!!
Last edited by kigoobe; Nov 2, 2007 at 06:34.
Still nice, but how to sort the tree in mysql by name or weight-ident?
How can I delete node and all it's children in The Adjacency List Model? If I replace printing with deleting, it just simply don't work.
I'm also looking for an easy way to sort the output array alphabetically. I don't really care how it stores the information, but when I display the formatted tree I'd like to be able to sort it by the "name" field in the DB on each level. Is there a way to do this? Maybe some recursive function?
How can I do move up/down operation, can someone share the SQL Query for moving nodes up and down, like I wanted to reorder the nodes from UI by just drag and drop
You can easily do this by changing the node IDs of the upper and the selected node. However this is not the best solution because it can ruin your application.
First an apologize to the one whos recieving my feedback mail, my browser gut stuck and wouldn't scrool futher down from the review function.
But i found a way that uses the adjacency storing method, and is memory efficient for finding a specific tree with only all anchestors and the ones at same level and above. so like a recursive method just only fetching the tree that we want to show.
To the simple point, backwards travel through the tree!
Alle numbers id's:
I have record 1 & 5 root nodes,
Then i have 2 & 4 as childs of 1, and no childs for 5.
then 2 has a child, 3 and that has a child of 6.
So if i want to print out a smooth menu from id: 3.
Then i SELECT * FROM menu WHERE id = 3
find out whenever it hasChilds and get thoose. then i read the parent property, and unless its zero i fetch the parent and put the menuElemnt(3) into the newly created object(with id 2) the i go back and do the same, its recursive but efficient for building a menu.
Only problem: sitemaps! i still ned the Preorder travelsal tree. or a recursive/adjacency function.
What if you wanted to show all the items in a SELECT form element in proper order using the Adjacency List Model? How would you do that?
that's one of the disadvantages of the adjacency list model: it's more difficult to sort than MPTT/nested set.
This is bloomin genius, I love you!
what if a store procedure is created to call the items from the database. How would you update the code to display this information in the correct order on the webpage?
I am creating something similar but using ASP and vbscript and I'm having a difficult time getting the data to display correctly. right now it's display all the items as parents. Any suggestions?
Thanks for the article.
I wonder if it's possible to calculate node's depth relative to top level based on its left & right properties...
I knew that this trick have to be possible, but I've never expected that it will be SO simple and quick! :D
Just a note, recursion alone is not usually that bad of a memory problem, since it's only the local data that appears on the stack - the code itself is not repeated anywhere.
Furthermore, when dealing with trees, recursion is often the most elegant and efficient way to access data, as trees often offer the shortest path to a desired object.
The reason this algorithm is interesting is because the repeated sql calls are what make recursion take so long, for large datasets. You should test to be sure which approach is better.
It seems to be a missing bit in the loop in the 'display_tree' function. You need to verify that 'count($right) - 1' is actually larger than -1 (if all items in the $right array is popped, you have none left and 'count($right) - 1' will result in -1) - otherwise you hit an infinite loop.
So to make this code running, the while condition in 'display_tree' function should be:
while ( count($right) > 0 && $right[ count($right) - 1 ] < $right_pos )
This is an excellent walkthrough of an algorithm I had never thought of myself. I am glad I stumbled across this article - it really brought a big lamp above my head. Thanks!!
You can easily build an XML structure for the output by modifying the 'display_tree' function slightly.
function display_tree() {
// retrieve the left and right value of the $root node
$result = mysql_query('SELECT lft, rgt FROM tree '.
'WHERE title="'.$root.'";');
$row = mysql_fetch_array($result);
// start with an empty $right stack
$right = array();
// now, retrieve all descendants of the $root node
$result = mysql_query('SELECT id, title, lft, rgt FROM tree '.
'WHERE lft BETWEEN '.$row['lft'].' AND '.
$row['rgt'].' ORDER BY lft ASC;');
// start with an empty $right stack
$right = array();
// Helper variables for pinpointing the location in the tree
$root_lft = 0;
$root_rgt = 0;
$last_rgt = 0;
$strTree = "";
// display each row
while ($row = mysqli_fetch_array( $result ))
{
$id = $row['id'];
$lft = $row['lft'];
$rgt = $row['rgt'];
$title = $row['title'];
// Helper variables
$hasChildren = ( ( $rgt - $lft - 1 ) / 2 ) > 0;
$isLast = ( $rgt == ( $lft + 1 ) );
$isRootNode = ( $root_rgt > 0 && $lft > $root_rgt ); // ($root_rgt > 0) is for ruling out the very first iteration
// Only set on first iteration and when it is a root node
if( $last_rgt == 0 || $isRootNode )
{
$root_lft = $lft;
$root_rgt = $rgt;
}
$strTree .= "<node haschildren=\"" . ( $hasChildren? "true" : "false" ) . "\" id=\"$id\"><title>$title</title>";
$strTree .= ( $hasChildren ) ? "<nodes>" : "" ;
$strTree .= ( $isLast ) ? "</node>" . (!$isRootNode ? "</nodes></node>" : "" ) : "";
// only check stack if there is one
if (count($right)>0)
{
// check if we should remove a node from the stack
while ( count($right) > 0 && $right[ count($right) - 1 ] < $rgt )
{
array_pop($right);
}
}
$right[] = $rgt;
$last_rgt = $rgt;
}
echo "<root>$strTree</root>";
}
Thank you very much for taking the time to write this tutorial; it is extremely lucid and easy to follow. Most importantly, it has helped put to rest many of my own questions regarding storing hierarchical data efficiently in a relational database.
Thanks again!
Your article is missing a couple of key points. Some databases, such as Oracle, handle hierarchical queries just fine using the CONNECT BY PRIOR syntax. Your code, in both methods, seems to be too clunky.
Also, your solution using the LEFT and RIGHT is simply turning a hierarchical model into a binary try, which will have severe limitations when building a complex tree, such as when a child has multiple parents, and those parents have other multiple children. CONNECT BY PRIOR handles that very well.
Posting Permissions
Bookmarks