快捷搜索:

The Nested Model 树形结构

先把树按水平的要领摆开,如下图

然后按前序遍历的措施,为每一个结点编号,每一个结点都有左、右的编号,根结点从1开始开始谋略。我们分手把阁下编号称为左值和右值。

根据前序遍历的规律,我们可以知道,每一个结点的子结点的左值比父结点左值大年夜而比父结点的右值小。例如 Fruit(2,11) 的子结点 Red(3,6)、Cherry(4,5)、 Yellow(7,10)、Banana(8,9) ,可以看到Red、Cherry、Yellow、Banana的左值均比Fruit大年夜,而右值均比Fruit小。

数据库设计如下:

CREATE TABLE `nested_category` (

`id` int(11) NOT NULL AUTO_INCREMENT,

`name` varchar(16) DEFAULT NULL,

`parent` int(11) DEFAULT NULL,

`lft` int(11) DEFAULT NULL,

`rgt` int(11) DEFAULT NULL,

PRIMARY KEY (`id`)

)

常用到的SQL语句:

返回完备的树(Retrieving a Full Tree)

SELECT node.name

FROM nested_category node, nested_category parent

WHERE node.lft BETWEEN parent.lft AND parent.rgt

AND parent.name = 'Food'

ORDER BY node.lft

返回某结点的祖谱路径(Retrieving a Single Path)

SELECT parent.name

FROM nested_category node, nested_category parent

WHERE node.lft BETWEEN parent.lft AND parent.rgt

AND node.name = 'Yellow'

ORDER BY node.lft

返回所有节点的深度(Finding the Depth of the Nodes)

提示:所有父结点的个数即为深度

SELECT V.*

FROM (SELECT node.name, (COUNT(parent.name) - 1) depth

FROM nested_category node, nested_category parent

WHERE node.lft BETWEEN parent.lft AND parent.rgt

GROUP BY node.name) V,

nested_category T

WHERE V.name = T.name

ORDER BY T.Lft

返回子树的深度(Depth of a Sub-Tree)

提示:

SELECT V.*

FROM (SELECT node.name,

(COUNT(parent.name) - (AVG(sub_tree.depth) + 1)) depth

FROM nested_category node,

nested_category parent,

nested_category sub_parent,

(SELECT V.*

FROM (SELECT node.name, (COUNT(parent.name) - 1) depth

FROM nested_category node, nested_category parent

WHERE node.lft BETWEEN parent.lft AND parent.rgt

AND node.name = 'Yellow'

GROUP BY node.name) V,

nested_category T

WHERE V.name = T.name

ORDER BY T.lft) sub_tree

WHERE node.lft BETWEEN parent.lft AND parent.rgt

AND node.lft BETWEEN sub_parent.lft AND sub_parent.rgt

AND sub_parent.name = sub_tree.name

GROUP BY node.name) V,

nested_category T

WHERE V.name = T.name

ORDER BY T.Lft

返回某结点的直接子树(Find the Immediate Subordinates of a Node)

提示:某结点A的所有子结点的深度(depth)减去A结点的深度即是1的所有结点即为A的直接结点

SELECT V.*

FROM (SELECT node.name,

(COUNT(parent.name) - (AVG(sub_tree.depth) + 1)) depth

FROM nested_category node,

nested_category parent,

nested_category sub_parent,

(SELECT V.*

FROM (SELECT node.name, (COUNT(parent.name) - 1) depth

FROM nested_category node, nested_category parent

WHERE node.lft BETWEEN parent.lft AND parent.rgt

AND node.name = 'Yellow'

GROUP BY node.name) V,

nested_category T

WHERE V.name = T.name

ORDER BY T.lft) sub_tree

WHERE node.lft BETWEEN parent.lft AND parent.rgt

AND node.lft BETWEEN sub_parent.lft AND sub_parent.rgt

AND sub_parent.name = sub_tree.name

GROUP BY node.name) V,

nested_category T

WHERE V.name = T.name

and V.depth0

ORDER BY T.Lft

返回所有的叶子节点(Finding all the Leaf Nodes)

提示:左值与右值相减为1的所有结点即为叶子结点

SELECT name FROM nested_category WHERE rgt = lft + 1

插入节点(Adding New Nodes)

即所有的后续的子结点都响应的加2

LOCK TABLE nested_category WRITE;

SELECT @myRight := rgt FROM nested_category WHERE name = 'TELEVISIONS';

UPDATE nested_category SET rgt = rgt + 2 WHERE rgt > @myRight;

UPDATE nested_category SET lft = lft + 2 WHERE lft > @myRight;

INSERT INTO nested_category

(name, lft, rgt)

VALUES

('GAME CONSOLES', @myRight + 1, @myRight + 2);

UNLOCK TABLES;

删除节点(Deleting Nodes)

提示:所有后续的结点都响应的减去结点删除后的阁下值的误差

LOCK TABLE nested_category WRITE;

SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1

FROM nested_category

WHERE name = 'GAME CONSOLES';

DELETE FROM nested_category WHERE lft BETWEEN @myLeft AND @myRight;

UPDATE nested_category SET rgt = rgt - @myWidth WHERE rgt > @myRight;

UPDATE nested_category SET lft = lft - @myWidth WHERE lft > @myRight;

UNLOCK TABLES;

源码下载:http://bbs.fengfly.com/thread-131-1-1.html

您可能还会对下面的文章感兴趣: