php - How to generate a tree view from this result set based on Tree Traversal Algorithm?

Question

I have this table:

CREATE TABLE `categories` (
  `id` int(11) NOT NULL auto_increment,
  `category_id` int(11) default NULL,
  `root_id` int(11) default NULL,
  `name` varchar(100) collate utf8_unicode_ci NOT NULL,
  `lft` int(11) NOT NULL,
  `rht` int(11) NOT NULL,
  PRIMARY KEY  (`id`),
  KEY `category_id` (`category_id`),
  KEY `lft` (`lft`,`rht`),
  KEY `root_id` (`root_id`)
) 

Based on this question: Getting a modified preorder tree traversal model (nested set) into a <ul>

The difference is that I have many trees in one table. Each row has a foreign key representing its parent and its top parent: category_id and root_id. Also I have the lft and rht fields based on this example: http://articles.sitepoint.com/article/hierarchical-data-database/2

Based on this rows:

INSERT INTO `categories` VALUES(1, NULL, NULL, 'Fruits', 1, 14);
INSERT INTO `categories` VALUES(2, 1, 1, 'Apple', 2, 3);
INSERT INTO `categories` VALUES(3, 1, 1, 'Orange', 4, 9);
INSERT INTO `categories` VALUES(4, 3, 1, 'Orange Type 1', 5, 6);
INSERT INTO `categories` VALUES(5, 3, 1, 'Orange Type 2', 7, 8);
INSERT INTO `categories` VALUES(6, 1, 1, 'Pear', 10, 11);
INSERT INTO `categories` VALUES(7, 1, 1, 'Banana', 12, 13);
INSERT INTO `categories` VALUES(8, NULL, NULL, 'Eletronics', 1, 14);
INSERT INTO `categories` VALUES(9, 8, 8, 'Cell Phones', 2, 3);
INSERT INTO `categories` VALUES(10, 8, 8, 'Computers', 4, 9);
INSERT INTO `categories` VALUES(11, 10, 8, 'PC', 5, 6);
INSERT INTO `categories` VALUES(12, 10, 8, 'MAC', 7, 8);
INSERT INTO `categories` VALUES(13, 8, 8, 'Printers', 10, 11);
INSERT INTO `categories` VALUES(14, 8, 8, 'Cameras', 12, 13);

How can I build an ordened list representing this tree?

With the sql bellow:

SELECT c. * , (COUNT( p.id ) -1) AS depth
FROM `categorias` AS p
CROSS JOIN categories AS c
WHERE (
c.lft
BETWEEN p.lft
AND p.rht
)
GROUP BY c.id
ORDER BY c.lft;

I got this result:

As you can see, I need to order by root_id too, so that I can generate the correct tree.

Also, after get the tree, is there a way to order each node by name?

Answer 1

As you can see, I need to order by root_id too, so that I can generate the correct tree.

When building the nested tree model, never make duplicates on lft and rgt. In fact, you should declare them unique.

In you data model, the sets for category 1 and 8 overlap. Say, 1 to 14 are used both for items 1 and 8.

Replace them with these values:

INSERT INTO `categories` VALUES(1, NULL, NULL, 'Fruits', 1, 14);
INSERT INTO `categories` VALUES(2, 1, 1, 'Apple', 2, 3);
INSERT INTO `categories` VALUES(3, 1, 1, 'Orange', 4, 9);
INSERT INTO `categories` VALUES(4, 3, 1, 'Orange Type 1', 5, 6);
INSERT INTO `categories` VALUES(5, 3, 1, 'Orange Type 2', 7, 8);
INSERT INTO `categories` VALUES(6, 1, 1, 'Pear', 10, 11);
INSERT INTO `categories` VALUES(7, 1, 1, 'Banana', 12, 13);
INSERT INTO `categories` VALUES(8, NULL, NULL, 'Eletronics', 15, 29);
INSERT INTO `categories` VALUES(9, 8, 8, 'Cell Phones', 16, 17);
INSERT INTO `categories` VALUES(10, 8, 8, 'Computers', 19, 24);
INSERT INTO `categories` VALUES(11, 10, 8, 'PC', 20, 21);
INSERT INTO `categories` VALUES(12, 10, 8, 'MAC', 22, 23);
INSERT INTO `categories` VALUES(13, 8, 8, 'Printers', 25, 26);
INSERT INTO `categories` VALUES(14, 8, 8, 'Cameras', 27, 28);

Now you don't have to order on root_id.

Also, after get the tree, is there a way to order each node by name?

No easy way, unless you insert the nodes in the name order from the beginning. Siblings with the greater name should have greater lft and rgt:

INSERT INTO `categories` VALUES(1, NULL, NULL, 'Fruits', 1, 14);
INSERT INTO `categories` VALUES(2, 1, 1, 'Apple', 2, 3);
INSERT INTO `categories` VALUES(7, 1, 1, 'Banana', 4, 5);
INSERT INTO `categories` VALUES(3, 1, 1, 'Orange', 6, 11);
INSERT INTO `categories` VALUES(4, 3, 1, 'Orange Type 1', 7, 8);
INSERT INTO `categories` VALUES(5, 3, 1, 'Orange Type 2', 9, 10);
INSERT INTO `categories` VALUES(6, 1, 1, 'Pear', 12, 13);

A nested tree can only have one implicit order.

There is also a way to query adjacency list in MySQL:

• Hierarchical queries in MySQL

, however, you will have to create an additional unique ordering column if you want to order on anything else than id.

You may also want to read this article:

• Adjacency list vs. nested sets: MySQL

which shows how to store and query nested sets more efficiently.