mysql 實現非遞歸樹

非递归树2011-01-23 19:25

这几天在捣鼓jqGrid,开始以为他只有表格的使用,无意中发现他的树还不错,看了示例觉得这个基本可以满足现在要求了,所以就看了一下,开始使用自己生成的数据来作为解析数据源,总是有这样或那样的缺陷,后来发现他是使用mysql官方网站上的数据分层实现,所以按照他的思路来做了一个,其实他的原理上面已经有说过,对于英文是超级白菜的我更是看得满头大汗,所以具体是上面看是自己去看看吧,我就不误导你们了,嘿嘿....
  具体的在这里,mysql数据分层算法

    下面就是非递归树的实现,原理真的很简单,mysql官网上的那个图已经很明了了,这个实现是通用的,至少我知道的mysql sqlserver oracle都可以!
    现在我就把sql基本和一些常用的操作贴出来,不同的 拿下去运行下就知道了,因为现在忙于做这个,没时间整理,到差不多了的话,如果可能的话,我在整理下:
sql脚本:
SET FOREIGN_KEY_CHECKS=0;
-- ----------------------------
-- Table structure for `tree`
-- ----------------------------
DROP TABLE IF EXISTS `tree`;
CREATE TABLE `tree` (
  `id` int(11) NOT NULL auto_increment,
  `title` varchar(50) collate utf8_unicode_ci default NULL,
  `lft` int(11) default NULL,
  `rgt` int(11) default NULL,
  `level` int(11) default NULL,
  PRIMARY KEY  (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci;
INSERT INTO `tree` VALUES ('1', 'ELECTRONICS', '1', '24', '0');
INSERT INTO `tree` VALUES ('2', 'TELEVISIONS', '2', '9', '1');
INSERT INTO `tree` VALUES ('3', 'TUBE', '3', '4', '2');
INSERT INTO `tree` VALUES ('4', 'LCD', '5', '6', '2');
INSERT INTO `tree` VALUES ('5', 'PLASMA', '7', '8', '2');
INSERT INTO `tree` VALUES ('7', 'PORTABLE ELECTRONICS', '10', '23', '1');
INSERT INTO `tree` VALUES ('8', 'MP3 PLAYERS', '11', '18', '2');
INSERT INTO `tree` VALUES ('9', 'FLASH', '12', '15', '3');
INSERT INTO `tree` VALUES ('10', 'CD PLAYERS', '19', '20', '2');
INSERT INTO `tree` VALUES ('11', '2 WAY RADIOS', '21', '22', '2');
INSERT INTO `tree` VALUES ('12', 'NODES', '16', '17', '3');
INSERT INTO `tree` VALUES ('13', 'FLASH-child', '13', '14', '4');
我在使用里觉得这几个操作已经够用了,如果希望有更高级的用法,自己去捣鼓下sql实现也不是什么难题
下面贴上操作sql
/*----------------------节点操作------------------------*/
/*遍历树*/
select concat(repeat(' ',(count(parent.title)-1)), node.title)as title from
tree as node, tree as parent where node.lft between parent.lft
and parent.rgt group by node.title order by node.lft

/*根据父节点名称查找子节点(所有深度)*/
SELECT node.title, (COUNT(parent.title) - (sub_tree.depth + 1)) AS depth
FROM tree AS node,
        tree AS parent,
        tree AS sub_parent,
        (
                SELECT node.title, (COUNT(parent.title) - 1) AS depth
                FROM tree AS node,
                tree AS parent
                WHERE node.lft BETWEEN parent.lft AND parent.rgt
                AND node.title = 'PORTABLE ELECTRONICS'
                GROUP BY node.title
                ORDER BY node.lft
        )AS 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.title = sub_tree.title
GROUP BY node.title
ORDER BY node.lft;

/*根据父节点名称查找子节点(一个深度)*/
SELECT node.title, (COUNT(parent.title) - (sub_tree.depth + 1)) AS depth
FROM tree AS node,
        tree AS parent,
        tree AS sub_parent,
        (
                SELECT node.title, (COUNT(parent.title) - 1) AS depth
                FROM tree AS node,
                tree AS parent
                WHERE node.lft BETWEEN parent.lft AND parent.rgt
                AND node.title = 'PORTABLE ELECTRONICS'
                GROUP BY node.title
                ORDER BY node.lft
        )AS 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.title = sub_tree.title
GROUP BY node.title
HAVING depth <= 1
ORDER BY node.lft;

/*同级目录添加节点*/
LOCK TABLE tree WRITE;
SELECT @myRight := rgt FROM tree WHERE title = 'FLASH';
UPDATE tree SET rgt = rgt + 2 WHERE rgt > @myRight;
UPDATE tree SET lft = lft + 2 WHERE lft > @myRight;
INSERT INTO tree(title, lft, rgt) VALUES('NODES', @myRight + 1, @myRight + 2);
UNLOCK TABLES;

/*父级添加子节点*/
LOCK TABLE tree WRITE;
SELECT @myLeft := lft FROM tree WHERE title = 'FLASH';
UPDATE tree SET rgt = rgt + 2 WHERE rgt > @myLeft;
UPDATE tree SET lft = lft + 2 WHERE lft > @myLeft;
INSERT INTO tree(title, lft, rgt) VALUES('FLASH-child', @myLeft + 1, @myLeft + 2);
UNLOCK TABLES;

/*-删除节点(可删除单独节点,也可删除指定节点包括子节点)-*/
LOCK TABLE tree WRITE;
SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1
FROM tree
WHERE title = 'FLASH-child';
DELETE FROM tree WHERE lft BETWEEN @myLeft AND @myRight;
UPDATE tree SET rgt = rgt - @myWidth WHERE rgt > @myRight;
UPDATE tree SET lft = lft - @myWidth WHERE lft > @myRight;
UNLOCK TABLES;

/*-删除父节点,所有该节点下的子节点上升一个级别(问题:递归改变节点级别)-*/

/*-SELECT t.lft, t.rgt,t.rgt - t.lft + 1 FROM tree as t 效果类似于
SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1
FROM tree -*/
LOCK TABLE tree WRITE;
SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1
FROM tree
WHERE title = 'MP3 PLAYERS';
DELETE FROM tree WHERE lft = @myLeft;
UPDATE tree SET rgt = rgt - 1, lft = lft - 1 WHERE lft BETWEEN @myLeft AND @myRight;
UPDATE tree SET rgt = rgt - 2 WHERE rgt > @myRight;
UPDATE tree SET lft = lft - 2 WHERE lft > @myRight;
UNLOCK TABLES;