Getting a modified preorder tree traversal model (nested set) into a ul
Ok, let's do some bounty hunting ;)
Step 0 - Sanitize example:
As already mentioned, your example data is broken, as it does not define a valid nested set. If you took this data from an app, you should check the insert/delete logic.
So for testing, I used a sanitized version like so:
(MySQL here, as it was the first at hand)
CREATE TABLE t_categories`(
`id` INTEGER UNSIGNED NOT NULL AUTO_INCREMENT,
`title` VARCHAR(45) NOT NULL,
`lft` INTEGER UNSIGNED NOT NULL,
`rght` INTEGER UNSIGNED NOT NULL,
PRIMARY KEY (`id`)
);
INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 1',1,16);
INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 2',2,3);
INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 3',4,7);
INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 4',5,6);
INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 5',8,13);
INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 6',9,12);
INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 7',10,11);
INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 8',14,15);
Step 1 - Let the database do the ordering
Nested sets where primarily invented as a convenient way of storing trees in databases, as they make it pretty easy to query for subtrees, parent relations and, especially interesting in this case, for order and depth:
SELECT node.title, (COUNT(parent.title) - 1) AS depth
FROM t_categories AS node
CROSS JOIN t_categories AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rght
GROUP BY node.title
ORDER BY node.lft
This will return your set neatly ordered, starting with the root node and continuing to the end in preorder. Most importantly, it will add the depth of each node as a positive integer, indicating how many levels the node is below root (level 0). For the above example data, the result will be:
title, depth
'Cat 1', 0
'Cat 2', 1
'Cat 3', 1
'Cat 4', 2
'Cat 5', 1
'Cat 6', 2
'Cat 7', 3
'Cat 8', 1
In code:
// Grab ordered data
$query = '';
$query .= 'SELECT node.title, (COUNT(parent.title) - 1) AS depth';
$query .= ' FROM t_categories AS node';
$query .= ' CROSS JOIN t_categories AS parent';
$query .= ' WHERE node.lft BETWEEN parent.lft AND parent.rght';
$query .= ' GROUP BY node.title';
$query .= ' ORDER BY node.lft';
$result = mysql_query($query);
// Build array
$tree = array();
while ($row = mysql_fetch_assoc($result)) {
$tree[] = $row;
}
The resulting array will look like this:
Array
(
[0] => Array
(
[title] => Cat 1
[depth] => 0
)
[1] => Array
(
[title] => Cat 2
[depth] => 1
)
...
)
Step 2 - Output as HTML list fragment:
Using while loop:
// bootstrap loop
$result = '';
$currDepth = -1; // -1 to get the outer <ul>
while (!empty($tree)) {
$currNode = array_shift($tree);
// Level down?
if ($currNode['depth'] > $currDepth) {
// Yes, open <ul>
$result .= '<ul>';
}
// Level up?
if ($currNode['depth'] < $currDepth) {
// Yes, close n open <ul>
$result .= str_repeat('</ul>', $currDepth - $currNode['depth']);
}
// Always add node
$result .= '<li>' . $currNode['title'] . '</li>';
// Adjust current depth
$currDepth = $currNode['depth'];
// Are we finished?
if (empty($tree)) {
// Yes, close n open <ul>
$result .= str_repeat('</ul>', $currDepth + 1);
}
}
print $result;
Same logic as recursive function:
function renderTree($tree, $currDepth = -1) {
$currNode = array_shift($tree);
$result = '';
// Going down?
if ($currNode['depth'] > $currDepth) {
// Yes, prepend <ul>
$result .= '<ul>';
}
// Going up?
if ($currNode['depth'] < $currDepth) {
// Yes, close n open <ul>
$result .= str_repeat('</ul>', $currDepth - $currNode['depth']);
}
// Always add the node
$result .= '<li>' . $currNode['title'] . '</li>';
// Anything left?
if (!empty($tree)) {
// Yes, recurse
$result .= renderTree($tree, $currNode['depth']);
}
else {
// No, close remaining <ul>
$result .= str_repeat('</ul>', $currNode['depth'] + 1);
}
return $result;
}
print renderTree($tree);
Both will output the following structure:
<ul>
<li>Cat 1</li>
<li>
<ul>
<li>Cat 2</li>
<li>Cat 3</li>
<li>
<ul>
<li>Cat 4</li>
</ul>
</li>
<li>Cat 5</li>
<li>
<ul>
<li>Cat 6</li>
<li>
<ul>
<li>Cat 7</li>
</ul>
</li>
</ul>
</li>
<li>Cat 8</li>
</ul>
</li>
</ul>
Nitpickers corner: Questioner explicitly asked for <ul>, but ordered unordered lists!? Come on...
;-)
Getting nested set model into a ul but hiding closed subtrees
As you already managed to sort the sequence, why not just output as needed?
As some leafs need to appear closed, so the iterator should be able to skip children of non-selected nodes.
Doing so lead me to an idea to solve the problem of terminating the output tree (output = parsing). What to do if the last valid node in the sequence is at a higher depth than 0? I appended a NULL terminator for that. So still open levels can be closed before the loop finishes.
Additionally the iterator overloads nodes to offer common methods on them, like comparing against the currently selected element.
The MyRenderTree function (Demo/Full code)
Edit: The Demo Codepad has problems, here is the source-code: Gist
Getting nested set model into a but hiding “closed” subtrees
function MyRenderTree($tree = array(array('name'=>'','depth'=>'', 'lft'=>'','rgt'=>'')) , $current=false)
{
$sequence = new SequenceTreeIterator($tree);
echo '<ul>';
$hasChildren = FALSE;
foreach($sequence as $node)
{
if ($close = $sequence->getCloseLevels())
{
echo str_repeat('</ul></li>', $close);
$hasChildren = FALSE;
}
if (!$node && $hasChildren)
{
echo '</li>', "\n";
}
if (!$node) break; # terminator
$hasChildren = $node->hasChildren();
$isSelected = $node->isSupersetOf($current);
$classes = array();
$isSelected && ($classes[] = 'selected') && $hasChildren && $classes[] = 'open';
$node->isSame($current) && $classes[] = 'current';
printf('<li class="%s">%s', implode(' ', $classes), $node['name']);
if ($hasChildren)
if ($isSelected)
echo '<ul>';
else
$sequence->skipChildren()
;
else
echo '</li>'
;
}
echo '</ul>';
}
This can be solved as well in a single foreach and some variables, however I think for re-useablilty, the implementation based on the SPL Iterators is better.
Display tree structure in ul li tag from preorder traversal table not working
This should work :
function printTree ($tree) {
$last_level = -1;
foreach ($tree as $v) {
$diff = $v['level'] - $last_level;
if ($diff == 0) {
echo '<li>' .$v['name']. '</li>';
}
elseif ($diff > 0) {
for ($i = 0; $i < $diff; $i++)
echo '<ul>';
echo '<li>' .$v['name']. '</li>' ;
}
else {
for ($i = 0; $i > $diff; $i--)
echo '</ul>';
echo '<li>' .$v['name']. '</li>' ;
}
$last_level = $v['level'];
}
}
But with this function, you won't have the depth printed.
Tested and working with
$tree = array (
array (
'name' => 'Line',
'level' => 0
),
array (
'name' => 'Line',
'level' => 1
),
array (
'name' => 'Line',
'level' => 2
),
array (
'name' => 'Line',
'level' => 1
)
);
printTree ($tree);
Getting Modified Preorder Tree Traversal Data into an Array
Give this code a shot. $results is the database results. $tree is the array you're getting back.
function create_tree ($results) {
$return = $results[0];
array_shift($results);
if ($return['lft'] + 1 == $return['rgt'])
$return['leaf'] = true;
else {
foreach ($results as $key => $result) {
if ($result['lft'] > $return['rgt']) //not a child
break;
if ($rgt > $result['lft']) //not a top-level child
continue;
$return['children'][] = create_tree(array_values($results));
foreach ($results as $child_key => $child) {
if ($child['rgt'] < $result['rgt'])
unset($results[$child_key]);
}
$rgt = $result['rgt'];
unset($results[$key]);
}
}
unset($return['lft'],$return['rgt']);
return $return;
}
$tree = create_tree($results);
How to create an array from this result set (nested categories stored in databased with traversal model)?
Ah, finally something for which references are handy:
<?php
$tree = array(
array('Cat 1', 'depth' => 0),
array('Cat 2', 'depth' => 1),
array('Cat 3', 'depth' => 1),
array('Cat 4', 'depth' => 2),
array('Cat 5', 'depth' => 1),
array('Cat 6', 'depth' => 2),
array('Cat 7', 'depth' => 3),
array('Cat 8', 'depth' => 1)
);
//same as before
$currDepth = -1;
//initilialize result
$result = array();
//create path structure for depths
$path = array();
//create 'root' node
$olditem = array('children'=> &$result);
foreach($tree as $item){
if($item['depth'] > $currDepth){
//remove possible old reference (old depth of other branch
if(isset($path[$item['depth']])) unset($path[$item['depth']]);
//make sure we have an array entry
if(!isset($olditem['children'])) $olditem['children'] = array();
//acquire target
$path[$item['depth']] = &$olditem['children'];
}
if($item['depth'] != $currDepth) unset($olditem);
//set correct target
$currDepth = $item['depth'];
//add item
$path[$currDepth][] = &$item;
//copy & remove reference
$olditem = &$item;
unset($item);
}
//always nice to clean up reference bombs:
unset($path);
unset($olditem);
var_dump($result);
?>
Nested set tree view data structure using with recursing and traversal techniques in MongoDB or JavaScript
You could create a Map to key your objects by slug. The values per key will be the result objects for parent objects. Include an entry for null, which will collect the top-level elements.
Then iterate the data again to populate children arrays -- when that property does not exist yet, create it on the fly. Finally output the top-level elements.
function makeTree(data) {
let children = []; // Top-level elements
let map = new Map(data.map(({title, slug}) => [slug, { title }]))
.set(null, {children});
for (let {slug, parent, title} of data) {
(map.get(parent || null).children ??= [])
.push(slug ? map.get(slug) : {title});
}
return children;
}
// Your mongodb data:
const data = [{_id:123, title:'Books', slug:'books', parent:null },{_id:124, title:'Programming', slug:'programming', parent:null },{_id:125, title:'JavaScript', slug:'javascript', parent:'programming' },{_id:126, title:'C++',slug:'cpp', parent:'programming' },{_id:127, title:'React', slug:'react', parent:'javascript' },{_id:128, title:'Redux', slug:'redux', parent:'react' },{_id:129, title:'Toolkit', parent:'redux' },{_id:130, title:'Saga', parent:'redux' },{_id:131, title:'Nodejs', parent:'programming' },{_id:132, title:'Databases', slug:'databases' },{_id:133, title:'MongoDB', parent:'databases' }];
console.log(makeTree(data));How to get the depth of each node from a Nested Set Table where there are duplicate node names
You can GROUP BY the unique ID:
SELECT node.name, (COUNT(parent.name) - 1) AS depth
FROM menu AS node
CROSS JOIN menu AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.id
ORDER BY node.lft
See my fiddle here: SQL Fiddle
How to generate a tree view from this result set based on Tree Traversal Algorithm?
I got it.
All you need to do is set root_id to the top parents too, so that you can ORDER BY correctly.
With the query bellow I can have separeted trees, and uptade only the tree that I'm working on:
SELECT c . * , count( p.id ) AS depth
FROM `categories` c
CROSS JOIN categories p
WHERE (
c.lft
BETWEEN p.lft
AND p.rht
)
AND c.root_id = p.root_id
GROUP BY c.id
ORDER BY c.root_id, c.lft
Related Topics
How to Check If Curl Is Enabled or Disabled
How to Call a PHP Script/Function on a HTML Button Click
Using PHP to Populate a <Select></Select> Dropdown
What Does "Mass Assignment" Mean in Laravel
How to Override Trait Function and Call It from the Overridden Function
Why Should I Use Templating System in PHP
Expected Response Code 220 But Got Code "", with Message "" in Laravel
PHP Header(Location: ...): Force Url Change in Address Bar
How to Get MAC Address of Client Using PHP
Can PHP Namespaces Contain Variables
Casting an Array with Numeric Keys as an Object
PHP Emitting 500 on Errors - Where Is This Documented
Send Email with PHPmailer - Embed Image in Body