左右值无限分类实现算法

《左右值无限分类实现算法》由会员分享，可在线阅读，更多相关《左右值无限分类实现算法（33页珍藏版）》请在装配图网上搜索。

1、一、引言 产品分类，多级的树状结构的论坛，邮件列表等许多地方我们都会遇到这样的问题：如何存 储多级结构的数据？在PHP的应用中，提供后台数据存储的通常是关系型数据库，它能够 保存大量的数据，提供高效的数据检索和更新服务。然而关系型数据的基本形式是纵横交错 的表，是一个平面的结构，如果要将多级树状结构存储在关系型数据库里就需要进行合理的 翻译工作。接下来我会将自己的所见所闻和一些实用的经验和大家探讨一下： 层级结构的数据保存在平面的数据库中基本上有两种常用设计方法：* 毗邻目录模式(adjacency list model)* 预排序遍历树算法(modified preorder tree tr

2、aversal algorithm)我不是计算机专业的，也没有学过什么数据结构的东西，所以这两个名字都是我自己按照字 面的意思翻的，如果说错了还请多多指教。这两个东西听着好像很吓人，其实非常容易理解。二、模型这里我用一个简单食品目录作为我们的示例数据。我们的数据结构是这样的，以下是代码：1.Food2.13.| Fr uit4.1 15.| Red6.1 1 17.|-Cherry8.1 |9.|+Yellow10.| |11.|+-Banana12.|13.+Meat14.|-Beef15. +-Pork复制代码为了照顾那些英文一塌糊涂的PHP爱好者1. Food :食物2. Fruit :

3、水果3. Red :红色4. Cherry:樱桃5. Yellow:黄色6. Banana:香蕉7. Meat :肉类8. Beef :牛肉9. Pork :猪肉复制代码三、实现1、毗邻目录模式(adjacency list model)这种模式我们经常用到，很多的教程和书中也介绍过。我们通过给每个节点增加一个属性 parent 来表示这个节点的父节点从而将整个树状结构通过平面的表描述出来。根据这个原 则，例子中的数据可以转化成如下的表：以下是代码：1. + -+2. |parent |name|3+3.十十4. |IFood|5. |Food|Fruit|6. |Fruit |Green|7

4、. |Green |Pear|8. |Fruit |Red|9. |Red|Cherry |10. |Fruit |Yellow |11. |Yellow |Banana |12. |Food|Meat|13. |Meat|Beef|14. |Meat|Pork|15. +-+复制代码我们看到Pear是Green的一个子节点，Green是Fruit的一个子节点。而根节点Food没有 父节点。为了简单地描述这个问题，这个例子中只用了 name来表示一个记录。在实际的 数据库中，你需要用数字的 id 来标示每个节点，数据库的表结构大概应该像这样： id, paren t_ id, name, de

5、scr。tion有了这样的表我们就可以通过数据库保存整个多级树状结构了。显示多级树，如果我们需要显示这样的一个多级结构需要一个递归函数。 以下是代码：1. 复制代码对整个结构的根节点(Food)使用这个函数就可以打印出整个多级树结构，由于Food是根 节点它的父节点是空的，所以这样调用:display_children(,O)。将显示整个树的内容：1.Food2.Fr uit3.Red4.Cherry5.Yellow6.Banana7.Meat8.Beef9.Pork复制代码如果你只想显示整个结构中的一部分， 比如说水果部分， 就可以这样调用 display_children(Fruit,0)

6、;几乎使用同样的方法我们可以知道从根节点到任意节点的路径。比如 Cherry 的路径是 Food ; Fruit ; Red。为了得到这样的一个路径我们需要从最深的一级Cherry开始，查 询得到它的父节点Red把它添加到路径中，然后我们再查询Red的父节点并把它也添加到 路径中，以此类推直到最高层的F ood，以下是代码：1. ;复制代码如果对Cherry使用这个函数：print_r(get_path(Cherry),就会得到这样的一个数组了:1.Array (2.0 = Food3.1 = Fruit4.2 = Red5.)复制代码接下来如何把它打印成你希望的格式，就是你的事情了缺点： 这

7、种方法很简单，容易理解，好上手。但是也有一些缺点。主要是因为运行速度很慢，由于 得到每个节点都需要进行数据库查询，数据量大的时候要进行很多查询才能完成一个树。另 外由于要进行递归运算，递归的每一级都需要占用一些内存所以在空间利用上效率也比较 低。2、预排序遍历树算法现在让我们看一看另外一种不使用递归计算，更加快速的方法，这就是预排序遍历树算法 (modified preorder tree traversal algorithm) 这种方法大家可能接触的比较少，初次使用也不像上面的方法容易理解，但是由于这种方法 不使用递归查询算法，有更高的查询效率。我们首先将多级数据按照下面的方式画在纸上，在

8、根节点 Food 的左侧写上 1 然后沿着这 个树继续向下 在 Fruit 的左侧写上 2 然后继续前进，沿着整个树的边缘给每一个节点都标 上左侧和右侧的数字。最后一个数字是标在 Food 右侧的 18。在下面的这张图中你可以看 到整个标好了数字的多级结构(。没有看懂？用你的手指指着数字从1 数到 18就明白怎么回 事了。还不明白，再数一遍，注意移动你的手指)。这些数字标明了各个节点之间的关系，Red”的号是3和6,它是Food 1-18的子孙节点。 同样，我们可以看到所有左值大于2和右值小于11的节点都是”Fruit 2-11的子孙节点以下是代码：1.1 Food 182.3.4.5.2 F

9、ruit 1112 Meat 176.8.9.Red 67 Yellow 1013 Beef 1415 Pork 1610.复制代码这样整个树状结构可以通过左右值来存储到数据库中。继续之前，我们看一看下面整理过的 数据表。以下是代码：1. +2. | parent | name | lft | rgt |3. +4. |Food| 1I 185. |Food|Fr uit| 2I 116. |Fruit |RedI 3I 67. |Red|CherryI 4I 58. |Fruit |YellowI 7I 109. |Yellow |BananaI 8I 910. |Food|MeatI 12

10、I 1711. |Meat|BeefI 13I 1412. |Meat|PorkI 15I 1613.+II|复制代码注意：由于left和right在SQL中有特殊的意义，所以我们需要用lft和rgt来表示左右 字段。另外这种结构中不再需要parent字段来表示树状结构。也就是说下面这样的表结 构就足够了。以下是代码：1. +十-+十2. InameI lftI rgt I3丄3.十十-十十4. IFoodI 1I 18 I5. IFr uitI 2I 11 I6. |Red1 31 6 |7. |Cherry1 415|8. |Yellow1 71 10 19. |Banana1 819|1

11、0. |Meat1 121 17|11. |Beef1 131 14|12. |Pork1 151 16 |13. +-+-+复制代码好了我们现在可以从数据库中获取数据了，例如我们需要得到Fruit项下的所有所有节点就 可以这样写查询语句：1. SELECT * FROM tree WHERE lft BETWEEN 2 AND 11；复制代码这个查询得到了以下的结果。以下是代码：1.+2.|name十-| lft十十I rgt |3i3.十十-十十4. |Fr uit1 2I 11 I5. |RedI 3I 6 I6. |CherryI 4I 5 I7. |YellowI 7I 10 I8.

12、 |BananaI 8I 9 I9.+复制代码看到了吧，只要一个查询就可以得到所有这些节点。为了能够像上面的递归函数那样显示整个树状结构，我们还需要对这样的查询进行排序。用节点的左值进行排序：1. SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC；1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20.21.22.23.24.25.26.27.28.复制代码剩下的问题如何显示层级的缩进了。以下是代码： 0) /检查我们是否应该将节点移出堆栈while ($rightcoun

13、t($right) - 1 复制代码如果你运行一下以上的函数就会得到和递归函数一样的结果。只是我们的这个新的函数可能 会更快一些，因为只有2 次数据库查询。要获知一个节点的路径就更简单了，如果我们想知道Cherry的路径就利用它的左右值4和 5 来做一个查询。1. SELECT name FROM tree WHERE lft ; 5 ORDER BY lft ASC；复制代码这样就会得到以下的结果： 以下是代码：1.+-2.|name33.十4.|Food5.|Fr uit6.|Red7.+-复制代码那么某个节点到底有多少子孙节点呢？很简单，子孙总数=(右值-左值-1)/21. descen

14、dants = (right -left - 1) / 2复制代码不相信？自己算一算啦。用这个简单的公式，我们可以很快的算出”Fruit 2-11”节点有4个子孙节点，而Banana 8-9 节点没有子孙节点，也就是说它不是一个父节点了。很神奇吧？虽然我已经多次用过这个方法，但是每次这样做的时候还是感到很神奇。 这的确是个很好的办法，但是有什么办法能够帮我们建立这样有左右值的数据表呢？这里再 介绍一个函数给大家，这个函数可以将name和parent结构的表自动转换成带有左右值的数 据表。以下是代码：1.复制代码当然这个函数是一个递归函数，我们需要从根节点开始运行这个函数来重建一个带有左右值的树

15、1. rebuild_tree（Food,1）;复制代码这个函数看上去有些复杂，但是它的作用和手工对表进行编号一样，就是将立体多层结构的 转换成一个带有左右值的数据表。那么对于这样的结构我们该如何增加，更新和删除一个节点呢？ 增加一个节点一般有两种方法：第一种，保留原有的 name 和 parent 结构，用老方法向数据中添加数据，每增加一条数据以 后使用 rebuild_tree 函数对整个结构重新进行一次编号。第二种，效率更高的办法是改变所有位于新节点右侧的数值。举例来说：我们想增加一种新 的水果Strawberry（草莓）它将成为Red节点的最后一个子节点。首先我们需要为它腾出 一些空间

16、。Red的右值应当从6改成8，Yellow 7-10 的左右值则应当改成9-12。依次类 推我们可以得知，如果要给新的值腾出空间需要给所有左右值大于5的节点（5是Red 最后一个子节点的右值） 加上 2。所以我们这样进行数据库操作：1. UPDATE tree SET rgt = rgt + 2 WHERE rgt 5;2. UPDATE tree SET lft = lft + 2 WHERE lft 5；复制代码 这样就为新插入的值腾出了空间，现在可以在腾出的空间里建立一个新的数据节点了， 它 的左右值分别是6和7复制代码再做一次查询看看吧！怎么样？很快吧。四、结语好了，现在你可以用两种不

17、同的方法设计你的多级数据库结构了，采用何种方式完全取决于 你个人的判断，但是对于层次多数量大的结构我更喜欢第二种方法。如果查询量较小但是需 要频繁添加和更新的数据，则第一种方法更为简便。另外，如果数据库支持的话你还可以将rebuild_tree（）和腾出空间的操作写成数据库端的触 发器函数， 在插入和更新的时候自动执行， 这样可以得到更好的运行效率， 而且你添加 新节点的 SQL 语句会变得更加简单。本帖最后由 小霈 于 2009-5-15 22:54 编辑今天，给同学讲课时，无意中看到自己几年前（还在高中时）总结的一个无限分类回想当年，逃课去搞 PHP不知道，大家还需要否，觉得当时自己总结的

18、还不错，发给大家，希望大家多提提意见啊数据库结构:采用左右值编码的保存该树的数据记录如下（设表名为tree）： c_id | name | left_node | right_node1 |商品| 1 | 182 | 食品 | 2 | 113 | 肉类 | 3 | 64 | 猪肉 |4|55 | 菜类 |7| 106 | 白菜 |8|97| 电器 |2| 178| 电视 |13| 149| 电棒 |15| 16第一次看见上面的数据记录，相信大部分人都不清楚左值(left_node)和右值(right_node) 是根据什么规则计算出来的，而且，这种表设计似乎没有保存父节点的信息。下面把左右值

19、和树结合起来，请看：1 商品 18+2 食品 1112 电器 17+13 电视 1415电棒 16+3 肉类 67 菜类 104 猪肉 58 白菜 9请用手指指着上图中的数字，从1 数到18，学习过数据结构的朋友肯定会发现什么吧？对 你手指移动的顺序就是对这棵树的进行先序遍历的顺序。接下来，让我讲述一下如何利用节 点的左右值，得到该节点的父节点，子孙节点数量，及自己在树中的层数。采用左右值编码的设计方案，在进行类别树的遍历时，由于只需进行2 次查询，消除了递归， 再加上查询条件都为数字比较，效率极高，类别树的记录条目越多，执行效率越高。(上面的部分应该时我在网上COPY的吧=.=！)下面的应用

20、部分就是原创喽)应用某个节点到底有多少子孙节点？子孙总数=（父节点的右值-父节点的左值-1） /2以节点“食品”举例，其子孙总数=（11-2-1） / 2 = 4如何判断某一节点下有没有子节点？当 该节点左值-1 等于 其右值 时，其下没有子节点检索某一父节点的所有子节点？假定我们要对节点“食品”及其子孙节点进行先序遍历的列表，只需使用如下一条sql语句：SELECT * FROM tree WHERE left_node BETWEEN 2 AND 11 ORDER BY left_node ASC如何取得父类？SELECT * FROM tree WHERE left_node$right

21、_node检索之后如何列表？当左值+1=右值时，该节点没有子节点，则下一节点不为其子节点若下一节点的左值=上一节点右值+1，则2个节点是同级关系若下一节点的左值=上一节点的左值+1 时，则第2个节点应是第一个节点的子节点若下一节点的左值-上一节点的右值1 时，则下一节点比上一节点高（下一节点的左值-上一节点的右值）级在某一父节点下添加一个子节点？ 1. 要求该子节点为该父节点下排序第一的节点，则 $left_node = 父节点 left_node+1, $right_node = $left_node+1;2. 要求该节点位于父节点下一个子节点A后面，贝l$left_node =节点A的ri

22、ght_node+l, $right_node = $left_node+1;3. 要求该节点是位于父节点下排序最后一位的节点，贝 $left_node = 父节点 right_node,$right_node = $left_node+l;Sql:UPDATE tree SET right_node=right_node+2 WHERE right_node=$left_nodeUPDATE tree SET left_node=left_node+2 WHERE left_node=$left_nodeINSERT INTO tree (name , left_node , right_n

23、ode) VALUES(名字 , $left_node , $right_node)移动节点，包括其子节点至节点 A 下？设该节点左值$left_node ,右值$right_node其子节点的数目为$count = ($right_node - $left_node -1 )/2 ,节点 A 左值为$Aeft_node ,UPDATE tree SET right_node=right_node-$right_node-$left_node-l WHERE right_node$right_node AND right_node$right_node AND left_node=$left_

24、nodeAND right_node=$right_node删除所有子节点？DELETE FROM tree WHERE left_node父节点的左值 AND right_node父节点的右值删除一个节点及其子节点？在上例中的号号后面各加一个=号http:/www.cublog.en/u/11995/showart 527781.htmldb=$db;$this-tablefix=om_; / end func/* Short description.* 增加新的分类* Detail description* paramnone* globalnone* since1.0* accesspr

25、ivate* returnvoid* updatedate time*/function addsort($CatagoryID,$SortName)if($CatagoryID=0)$Lft=0;$Rgt=1;else$Result=$this-checkcatagory($CatagoryID);/取得父类的左值,右值$Lft=$ResultLft;$Rgt=$ResultRgt;$this-db-query(UPDATE、.$this-tablefix. catagory、SET、Lft、二Lft+2 WHERE Lft、$Rgt)；$this-db-query(UPDATE . $th

26、is-tablefix.catagory、SET、Rgt、二Rgt+2 WHERE Rgt=$Rgt)；/插入if($this-db-query(INSERT INTO、.$this-tablefix. catagory、SET、L ft、二,$Rg t,、Rg t、=$Rg t+l,、Name、=$Sor tName)/$ this-refer to(成功增加新的类别,JAVASCRIPT:HISTORY.BACK(1),3);return1;else/$ this-refer to(增加新的类别失败了,JAVASCRIPT:HISTORY.BACK(1),3);return -1; / e

27、nd func/* Short description.* 删除类别* Detail description* paramnone* globalnone* since1.0* accessprivate* returnvoid* updatedate time*/ functiondeletesort($CatagoryID)/取得被删除类别的左右值,检测是否有子类,如果有就一起删除$Result=$this-checkcatagory($CatagoryID);$Lft=$Result,Lft,;$Rgt=$Result,Rgt,;/执行删除if($this-db-query(DELETE

28、 FROM、.$this-tablefix. catagory、WHERE Lft=$Lft AND Rgtdb-query(UPDATE .$this-tablefix.catagory SET Lft= Lft-$Value WHERE Lft$Lft);$this-db-query(UPDATE .$this-tablefix.catagory SET Rgt= Rgt-$Value WHERE Rgt$Rgt);/$ this-refer to(成功删除类别,javascrip t:his tory.back(l),3);return 1;else/$ this-refer to(删除

29、类别失败了 ,javascrip t:his tory.back(l),3); return -1; / end func/* Short description.* 1, 所有子类,不包含自己;2包含自己的所有子类;3 不包含自己所有父类 4; 包含自己所有父类* Detail description* paramnone* globalnone* since1.0* accessprivate* returnvoid* updatedate time*/function getcatagory($CatagoryID,$type=1) $Result=$this-checkcatagory

30、($CatagoryID);$Lft=$ResultLft;$Rgt=$ResultRgt;$SeekSQL二SELECT * FROM .$this-tablefix.catagory WHERE ; switch ($type) case 1:$condition=Lft$Lft AND Rgt=$Lft AND Rgt=$Rgt;break;case 3:$condition=Lft$Rgt; break;case 4:$condition=Lft=$Rgt;break;default :$condition=Lft$Lft AND Rgtdb-getrows($SeekSQL); re

31、turn $Sorts; / end func/* Short description.* 取得直属父类* Detail description* paramnone* globalnone* since1.0* accessprivate* returnvoid* updatedate time*/function getparent($CatagoryID)$Parent=$this-getcatagory($CatagoryID,3); return $Parent; / end func /* Short description.* 移动类 , 如果类有子类也一并移动* Detail

32、description* paramnone* globalnone* since1.0* accessprivate* returnvoid* updatedate time*/function movecatagory($SelfCatagoryID,$ParentCatagoryID) $SelfCatagory=$this-checkcatagory($SelfCatagoryID);$NewCatagory=$this-checkcatagory($ParentCatagoryID);$SelfLft=$SelfCatagoryLft;$SelfRgt=$SelfCatagoryRg

33、t;$Value=$SelfRgt-$SelfLft;/取得所有分类的 ID 方便更新左右值$CatagoryIDS=$this-getcatagory($SelfCatagoryID,2); foreach($CatagoryIDS as $v)$IDS=$vCatagoryID;$InIDS=implode(,$IDS);$ParentLft=$NewCatagoryLft;$ParentRgt=$NewCatagoryRgt;/print_r($InIDS);/print_r($NewCatagory);/print_r($SelfCatagory);/exit; if($ParentR

34、gt$SelfRgt)$UpdateLeftSQL二UPDATE 、.$this-tablefix.catagory、 SET 、Lft、二、L ft、-$Value-l WHERE Lft、$SelfRgt AND Rgt$SelfRgt AND Rgttablefix.catagory SET Lft=L ft+$TmpValue,Rgt=Rgt+$TmpValue WHERE CatagoryID IN($InIDS);else$UpdateLeftSQL=UPDATE .$this-tablefix.catagory SET Lft=L ft+$Value+1 WHERE Lft$Pa

35、rentRgt AND Lfttablefix.catagory SET Rgt=Rgt+$Value+1 WHERE Rgt=$ParentRgt AND Rgttablefix.catagory SET Lft=L ft-$TmpValue,Rgt=Rgt-$TmpValue WHERE CatagoryID IN($InIDS);$this-db-query($UpdateLeftSQL);$this-db-query($UpdateRightSQL);$this-db-query($UpdateSelfSQL);/$ this-refer to(成功移动类别,javascrip t:h

36、is tory.back(l),3); return 1; / end func/* Short description.* Detail description* paramnone* globalnone* since1.0* accessprivate* returnvoid* updatedate time*/function checkcatagory($CatagoryID)/检测父类ID是否存在$SQL二SELECT * FROM .$this-tablefix.catagory WHERE CatagorylD、二 $CatagoryID LIMIT 1;$Result=$th

37、is-db-getrow($SQL); if(count($Result)referto(父类ID不存在，请检查 ,javascript:history.back(1),3);return $Result; / end func/* Short description.* Detail description* paramnone* globalnone* since1.0* accessprivate* returnarray($Catagoryarray，$Deep)* updatedate time*/function sort2array($CatagoryID=0)$Output =

38、 array(); if($CatagoryID=0)$CatagoryID=$this-getrootid();if(empty($CatagoryID)return array();exit;$Result = $this-db-query(SELECT Lft， Rgt FROM .$this-table fix.catagory WHERE CatagorylD = . $Cat agoryID);if($Row = $this-db-fetch_array($Result) $Right 二 array();$Query = SELECT * FROM 、.$this-tablefi

39、xcatagory WHERE Lft BETWEEN .$RowLft. AND . $RowRgt. ORDER BY Lft ASC;$Result = $this-db-query($Query) ;while ($Row = $this-db-fetch_array($Result) if (count($Right)0) while ($Rightcount($Right)-1$Row,Deep=count($Right); $Right = $RowRgt;return $Output; / end func/* Short description.* Detail descri

40、ption* paramnone* globalnone* since1.0* accessprivate* returnvoid* updatedate time*/function getrootid()$Query=SELECT * FROM.$this-tablefix.catagory ORDER BY Lft ASC LIMIT 1;$RootID=$this-db-getrow($Query);if(count($RootID)0)return $RootIDCatagoryID ;elsereturn0; / end func/* Short description.* Det

41、ail description* paramnone* globalnone* since1.0* accessprivate* returnvoid* update date time*/function referto($msg,$url,$sec)echo ;echo ; if(is_array($msg)foreach($msg as $key=$value)echo $key.=.$value.;elseecho $msg;exit; / end func / end class?80%BC+%E6%97%A0%E9%99%90%E5%88%86%E7%B1%BB&btnG=Google+%E6%90%9C %E7%B4%A2&aq=f&oq=