PHP无限分类——左右值实现

shilang

Post at 2012-06-13 02:03:33php无限分类左右值预排序树

网站，一定离不开多级分类：小到导航栏的两三级分类，大到其它货物的无限分类等。PHP无限分类有多种算法，本文将介绍的是PHP左右值无限分类，也称为预排序树无限分类 ...

• 什么是左右值无限级分类
  
• 左右值无限分类的优缺点
  
• PHP无限分类研究对象
  
• 创建PHP左右值无限分类的SQL数据
  
• 获取所有的后代节点
  
• 计算所有子类的数量
  
• 插入分类算法
  
• PHP插入节点代码
  
• 移动节点演示图
  
• PHP移动分类函数
  
• 获取所有的父级
  
• 本文本演示文件下载
  
• PHP无限分类扩展阅读
  

什么是左右值无限级分类　　左右值无限级分类，也称为预排序树无限级分类，是一种有序的树状结构，位于这些树状结构中的每一个节点都有一个“左值”和“右值”，其规则是：每一个后代节点的左值总是大于父类，右值总是小于父级，右值总是小于左值。处于这些结构中的每一个节点，都可以轻易的算出其祖先或后代节点。因此，可以用它来实现无限分类。
左右值无限分类的优缺点
　　优点：

• 通过一条SQL就可以获取所有的祖先或后代，这在复杂的分类中非常必要
  
• 通过简单的四则运算就可以得到后代的数量
  

　　缺点

• 分类操作麻烦
  
• 无法简单的获取子代（请看请“子代”和"后代"）
  

PHP无限分类研究对象
　　本文用于演示的对象：狼魂博客[http://pjiaxu.com]的导航栏，其结构如下图：
1.[1]舞文弄墨[8] [9]洞若观火[12] [13]WEB开发[20]
2.------------------------------------------------------
3.| | |
4.| | |
5.| [10]用户体验[11] |
6.| |
7.-------------------------------------------- ----------------------------------
8.[2]似水流年[3] [4]纸上谈兵[5] [6]隔岸观火[7] [14]PHP[15] [16]JS[17] [18]HTML[19]


　　其中的[数字]就是每一级的“左右值”，这里的左右值是早已经存在的，我们就以此为例，逐步研究这种算法。
创建PHP左右值无限分类的SQL数据
01.createtable`navs`(
02.`id`intprimary key auto_increment,
03.`name`varchar(32)notnull,
04.`lft`intnot null,
05.`rght`intnot null
06.);
07.insertinto`navs`(`name`,`lft`,`rght`)
08.values
09.('舞文弄墨',1,8),
10.('似水流年',2,3),
11.('纸上谈兵',4,5),
12.('隔岸观火',6,7),
13.('洞若观火',9,12),
14.('用户体验',10,11),
15.('WEB开发',13,20),
16.('PHP',14,15),
17.('JS',16,17),
18.('HTML',18,19);


　　上图，我为了方便，将SQL有意识的缩进了一下，这应该可以一目了然这种结构了吧。
获取所有的后代节点
　　了解了PHP预排序村的规则后，我们就可以很清晰的知道如何获取某个节点的所有子代——左值比它大，右值比它小。如，我们要获取“舞文弄墨”的所有子后代，可以使用以下的SQL语句：
1.select*from `navs` where`lft`>1 and `rght`<8


得到如下的结果：

计算所有子类的数量
　　有人认为使用 count 配合上面的语句就可以算出，这当然是可以的，但有更快的方式：每有子类节点中每个节点占用两个值，而这些值都是不一样且连续的，那些就可以计算出子代的数量=(右值-左值-1)/2。减少1的原因是排除该节点，你可以想像一个，一个单节点，左值是1，右值是2，没有子类节点，而这时它的右值-左值=1.
插入分类算法
　　还是先以图为例，比如，现在狼魂的博客[http://pjiaxu.com]发行了一个pblog博客系统，那么它想要在顶级导航上加上pblog这个导航菜单，需要怎么做（这是加顶级菜单的例子）？然而，它又想在Javascript中加入个jQuery分类，又该怎么做？做这些操作有两个重难点：

• 为插入分类分配一个左右值
  
• 更新其它节点的左右值
  

　　结果的示例图如下：
01.[1]舞文弄墨[8] [9]洞若观火[12] [13]WEB开发[22] [23]pblog[24]
02.-----------------------------------------------------------------------
03.| | |
04.| | |
05.| [10]用户体验[11] |
06.| |
07.-------------------------------------------- ----------------------------------
08.[2]似水流年[3] [4]纸上谈兵[5] [6]隔岸观火[7] [14]PHP[15] [16]JS[19] [20]HTML[21]
09.|
10.[17]jquery[18]


我们分析一下这两种情况：

• 插入最顶级节点：它的左右值与该树中最大的右值有关：左值=最大右值+1，右值=最大右值+2，你可以自己模拟一下；
  
• 插入子节点：它的左右值与它的父级有关：左值=父级的右值，右值=父级的左值+1，这时要更新的数据有：父级的右值，所有左值大于父级左级，右值大于低级右值的节点左右值都应该+2；你可以模拟在jquery下再加一个节点看是不是如此。
  

　　有了这些分析，就不难用PHP来实现了，下面，就使用PHP写一个插入算法；
PHP插入节点代码
01.define('DB_HOST','localhost');
02.define('DB_USER','root');
03.define('DB_PWD','`12345');
04.define('DB_NAME','test');
05.classEndlessByLR
06.{
07.functioninsert($name,$parentid)
08.{
09.$db=new mysqli(DB_HOST,DB_USER,DB_PWD,DB_NAME);
10.if($parentid==0)
11.{
12.//增加最高级，即与WEB开发同级，详见[http://pjiaxu.com/]导航中的Pblog
13.$sql='select max(`rght`) as `maxid` from `navs`;';
14.$result=$db->query($sql);
15.//这里基本不用做出错判断，一般都有数据的
16.$row=$result->fetch_array(MYSQLI_ASSOC);
17.$lft=$row['maxid']+1;
18.$rght=$lft+1;
19.}
20.else
21.{
22.$sql="select * from `navs` where `id`={$parentid};";
23.$result=$db->query($sql);
24.//这里应做个出错判断
25.$row=$result->fetch_array(MYSQLI_ASSOC);
26.$rght=$row['rght'];
27.$sql="update `navs` set `rght`=`rght`+2 where `rght`>={$rght};";
28.$db->query($sql);
29.$sql="update `navs` set `lft`=`lft`+2 where `lft`>{$rght};";
30.$db->query($sql);
31.$lft=$row['rght'];
32.$rght=$lft+1;
33.}
34.$sql="insert into `navs`(`name`,`lft`,`rght`)values('{$name}',{$lft},{$rght});";
35.return$db->query($sql);
36.}
37.}


注意，使用这段PHP函数需要以上SQL的支持；现在，我们就使用这个函数插入刚才所说的两个节点，看看结果是否一致？view sourceprint?

1.$eblr=new EndlessByLR();
2.$eblr->insert('pblog',0);//0是顶级,9是JS，在插入之前，你应该是知道的！
3.$eblr->insert('jquery',9);


产生了以下的结果：

　　你可以花点时间验证一下是不是跟演示图一样。

网上搜索引擎有一个相似的文章占了前几页，在更新又值时是使用 `rght`>{$rght} 而不是 `rght`>={$rght}；就我今天目测了N久的得出结果：这是不科学的！

　　解决了插入的问题，实际上就解决了很多实际应用了。现在，我们需要研究另一种操作：移动节点——这个是要了亲命的操作！
移动节点演示图
　　我们还是来演示推算一下再到代码中去吧。突然间，狼魂博客[http://pjiaxu.com/map.html]觉得pblog大多的内容都是PHP，那何不把它移动到PHP分类下呢？
view sourceprint?

01.[1]舞文弄墨[8] [9]洞若观火[12] [13]WEB开发[22](24) [25]other[26](假设存在)
02.----------------------------------------------------------------------
03.| | |
04.| | |
05.| [10]用户体验[11] |
06.| |
07.-------------------------------------------- --------------------------------------
08.[2]似水流年[3] [4]纸上谈兵[5] [6]隔岸观火[7] [14]PHP[15](17) (18)[16]JS[19](21) (22)[20]HTML[21](23)
09.| |
10.(15)[23]pblog[24](16) (19)[17]jquery[18](20)


方括号[]中的数字是现在的左右值，小括号()中的数字是期望值，也就是移动后应该得到的左右值。最终将是以下的样子：01.[1]舞文弄墨[8] [9]洞若观火[12] [13]WEB开发[24]
02.----------------------------------------------------------------------
03.| | |
04.| | |
05.| [10]用户体验[11] |
06.| |
07.-------------------------------------------- ---------------------------------------
08.[2]似水流年[3] [4]纸上谈兵[5] [6]隔岸观火[7] [14]PHP[17] [18]JS[21] [22]HTML[23]
09.| |
10.[15]pblog[16] [19]jquery[20]


　　我们继续分析——移动共可以四个方向移动：

• pblog移动到php之下成为它的子类
  
• pblog移动到php之上成为它的父类
  
• pblog移动到php左右成为它的兄弟
  

　　我们以子类为例子演示推算一下，假设(x1,y1)、(x2,y2)是php和pblog的左右值，那么，我们能过分析得到以下的结论：

• 左值在min(y1,y2)最小右值和max(x1,x2)最大左值之间都需要加2
  
• 右值在min(x1,x2)最小左值和max(y1,y2)最大右值之间都需要加2
  
• 移动节点的左值=父类节点的右值，右值=父类节点右值+1
  

　　通过以上的分析，就可以写出移动节点的PHP代码。
PHP移动分类函数
01.<?php
02.classEndlessByLR{
03.//......
04.//......
05.//接上面的代码
06.functionmove($formid,$toid,$derect)
07.{
08.if($formid==$toid)
09.{
10.returntrue;
11.}
12.$sql= "select * from `navs` where `id`=$formid
13.union
14.select * from `navs` where `id`=$toid";
15.$db=new mysqli(DB_HOST,DB_USER,DB_PWD,DB_NAME);
16.$result=$db->query($sql);
17.$rows=$result->fetch_all(MYSQLI_ASSOC);//php版本要大于5.3才可以用
18.if($rows[0]['lft']>$rows[1]['lft'])
19.{
20.$maxlft=$rows[0]['lft'];
21.$minlft=$rows[1]['lft'];
22.}
23.else
24.{
25.$maxlft=$rows[1]['lft'];
26.$minlft=$rows[0]['lft'];
27.}
28.if($rows[0]['rght']>$rows[1]['rght'])
29.{
30.$minrght=$rows[1]['rght'];
31.$maxrght=$rows[0]['rght'];
32.}
33.else
34.{
35.$minrght=$rows[0]['rght'];
36.$maxrght=$rows[1]['rght'];
37.}
38.
39.switch($derect)
40.{
41.case'child':
42.$sql="update `navs` set `lft`=`lft`+2 where `lft` between $minrght and $maxlft";
43.$db->query($sql);
44.//echo $sql;
45.$sql="update `navs` set `rght`=`rght`+2 where `rght` between $minlft and $maxrght";
46.$db->query($sql);
47.//echo $sql;
48.$lft=$minlft+1;
49.$rght=$lft+1;
50.$sql="update `navs` set `lft`=$lft,`rght`=$rght where id=$formid limit 1;";
51.//echo $sql;
52.$db->query($sql);
53.break;
54.case'parent':
55.break;
56.case'before':
57.break;
58.case'after':
59.break;
60.}
61.}


这个函数就将我们刚才的分析以代码的方式实现，现在我们就将pblog移到PHP子类中去：1.$eblr->move(11,8,'child');


得到的结果如下图：

　　如要移动看其它位置，看各位模仿移动子类自行分析。
获取所有的父级
　　这个为什么要放最后，那是——只有在最后，jquery才有直属两个祖先——js和web开发，其实看一下就知道了，获取一个分类的直属祖先（类似于我们平时看到网站的"你所在的位置"一样获取一条直达首页的路径）。规则就是：左值小于该分类，右值大于该分类的节点；如，获取jquery的路径就是：
1.select*from `navs` where`lft`<17 and `rght`>28