左右值無(wú)限分類實(shí)現(xiàn)算法

/viewthread.php?tid=227253一、引言產(chǎn)品分類，多級(jí)的樹狀結(jié)構(gòu)的論壇，郵件列表等許多地方我們都會(huì)遇到這樣的問(wèn)題：如何存儲(chǔ)多級(jí)結(jié)構(gòu)的數(shù)據(jù)？在PHP的應(yīng)用中，提供后臺(tái)數(shù)據(jù)存儲(chǔ)的通常是關(guān)系型數(shù)據(jù)庫(kù)，它能夠保存大量的數(shù)據(jù)，提供高效的數(shù)據(jù)檢索和更新服務(wù)。然而關(guān)系型數(shù)據(jù)的基本形式是縱橫交錯(cuò)的表，是一個(gè)平面的結(jié)構(gòu)，如果要將多級(jí)樹狀結(jié)構(gòu)存儲(chǔ)在關(guān)系型數(shù)據(jù)庫(kù)里就需要進(jìn)行合理的翻譯工作。接下來(lái)我會(huì)將自己的所見所聞和一些實(shí)用的經(jīng)驗(yàn)和大家探討一下：層級(jí)結(jié)構(gòu)的數(shù)據(jù)保存在平面的數(shù)據(jù)庫(kù)中基本上有兩種常用設(shè)計(jì)方法：毗鄰目錄模式(adjacencylistmodel)預(yù)排序遍歷樹算法(modifiedpreordertreetraversalalgorithm)我不是計(jì)算機(jī)專業(yè)的，也沒有學(xué)過(guò)什么數(shù)據(jù)結(jié)構(gòu)的東西，所以這兩個(gè)名字都是我自己按照字面的意思翻的，如果說(shuō)錯(cuò)了還請(qǐng)多多指教。這兩個(gè)東西聽著好像很嚇人，其實(shí)非常容易理解。二、模型這里我用一個(gè)簡(jiǎn)單食品目錄作為我們的示例數(shù)據(jù)。我們的數(shù)據(jù)結(jié)構(gòu)是這樣的，以下是代碼：1.Food2.13.|—Fruit4.115.| |——Red6.1117.| | |--Cherry8.1|9.| +—Yellow10.||11.| +--Banana12.|13.+——Meat14.|--Beef

+--Pork復(fù)制代碼為了照顧那些英文一塌糊涂的PHP愛好者Food:食物Fruit:水果Red:紅色Cherry:櫻桃Yellow:黃色Banana:香蕉Meat:肉類Beef:牛肉Pork:豬肉復(fù)制代碼三、實(shí)現(xiàn)1、毗鄰目錄模式(adjacencylistmodel)這種模式我們經(jīng)常用到，很多的教程和書中也介紹過(guò)。我們通過(guò)給每個(gè)節(jié)點(diǎn)增加一個(gè)屬性parent來(lái)表示這個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)從而將整個(gè)樹狀結(jié)構(gòu)通過(guò)平面的表描述出來(lái)。根據(jù)這個(gè)原則，例子中的數(shù)據(jù)可以轉(zhuǎn)化成如下的表：以下是代碼：1.+- +2.|parent|name |3 +3. 十■ 十4.|IFood |5.|Food |Fruit |6.|Fruit|Green |7.|Green|Pear |8.|Fruit|Red |9.|Red |Cherry|

10.|Fruit|Yellow|11.|Yellow|Banana|12.|Food |Meat |13.|Meat |Beef |14.|Meat |Pork |15.+-- +復(fù)制代碼我們看到Pear是Green的一個(gè)子節(jié)點(diǎn)，Green是Fruit的一個(gè)子節(jié)點(diǎn)。而根節(jié)點(diǎn)'Food'沒有父節(jié)點(diǎn)。為了簡(jiǎn)單地描述這個(gè)問(wèn)題，這個(gè)例子中只用了name來(lái)表示一個(gè)記錄。在實(shí)際的數(shù)據(jù)庫(kù)中，你需要用數(shù)字的id來(lái)標(biāo)示每個(gè)節(jié)點(diǎn)，數(shù)據(jù)庫(kù)的表結(jié)構(gòu)大概應(yīng)該像這樣：id,parent_id,name,descr。tion有了這樣的表我們就可以通過(guò)數(shù)據(jù)庫(kù)保存整個(gè)多級(jí)樹狀結(jié)構(gòu)了。顯示多級(jí)樹，如果我們需要顯示這樣的一個(gè)多級(jí)結(jié)構(gòu)需要一個(gè)遞歸函數(shù)。以下是代碼：<?php//$parentistheparentofthechildrenwewanttosee//$levelisincreasedwhenwegodeeperintothetree,// usedtodisplayaniceindentedtreefunctiondisplay_children($parent,$level){//獲得一個(gè)父節(jié)點(diǎn)$parent的所有子節(jié)點(diǎn)$result=mysql_query("SELECTnameFROMtreewhereparent='".$parent."'TOC\o"1-5"\h\z;");//顯示每個(gè)子節(jié)點(diǎn)while($row=mysql_fetch_array($result)) {//縮進(jìn)顯示節(jié)點(diǎn)名稱echostr_repeat(' ',$level).$row['name']."\n";//再次調(diào)用這個(gè)函數(shù)顯示子節(jié)點(diǎn)的子節(jié)點(diǎn)}}?>復(fù)制代碼對(duì)整個(gè)結(jié)構(gòu)的根節(jié)點(diǎn)(Food)使用這個(gè)函數(shù)就可以打印出整個(gè)多級(jí)樹結(jié)構(gòu)，由于Food是根節(jié)點(diǎn)它的父節(jié)點(diǎn)是空的，所以這樣調(diào)用:display_children(",O)。將顯示整個(gè)樹的內(nèi)容：1.Food2.Fruit3.Red4.Cherry5.Yellow6.Banana7.Meat8.Beef9.Pork復(fù)制代碼如果你只想顯示整個(gè)結(jié)構(gòu)中的一部分，比如說(shuō)水果部分，就可以這樣調(diào)用display_children('Fruit',0);幾乎使用同樣的方法我們可以知道從根節(jié)點(diǎn)到任意節(jié)點(diǎn)的路徑。比如Cherry1.Food2.Fruit3.Red4.Cherry5.Yellow6.Banana7.Meat8.Beef9.Pork復(fù)制代碼如果你只想顯示整個(gè)結(jié)構(gòu)中的一部分，比如說(shuō)水果部分，就可以這樣調(diào)用display_children('Fruit',0);幾乎使用同樣的方法我們可以知道從根節(jié)點(diǎn)到任意節(jié)點(diǎn)的路徑。比如Cherry的路徑是"Food>;Fruit>;Red"。為了得到這樣的一個(gè)路徑我們需要從最深的一級(jí)"Cherry"開始，查詢得到它的父節(jié)點(diǎn)"Red"把它添加到路徑中，然后我們?cè)俨樵僐ed的父節(jié)點(diǎn)并把它也添加到路徑中，以此類推直到最高層的"Food"，以下是代碼：<?php//$node是那個(gè)最深的節(jié)點(diǎn)functionget_path($node){//查詢這個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)$result=mysql_query("6.SELECTparent8.wherename='".$node."'9.11.$row=mysql_fetch_array($result);12.//用一個(gè)數(shù)組保存路徑13.$path=array();14.//如果不是根節(jié)點(diǎn)則繼續(xù)向上查詢15.//(根節(jié)點(diǎn)沒有父節(jié)點(diǎn))16.if($row['parent']!=''){17.//thelastpartofthepathto$node,isthename18.//oftheparentof$node19.$path[]=$row['parent'];20.//weshouldaddthepathtotheparentofthisnode21.//tothepath22.$path=array_merge(get_path($row['parent']),$path);23.24.//returnthepath8.wherename='".$node."'9.11.$row=mysql_fetch_array($result);12.//用一個(gè)數(shù)組保存路徑13.$path=array();14.//如果不是根節(jié)點(diǎn)則繼續(xù)向上查詢15.//(根節(jié)點(diǎn)沒有父節(jié)點(diǎn))16.if($row['parent']!=''){17.//thelastpartofthepathto$node,isthename18.//oftheparentof$node19.$path[]=$row['parent'];20.//weshouldaddthepathtotheparentofthisnode21.//tothepath22.$path=array_merge(get_path($row['parent']),$path);23.24.//returnthepath25.return$path;26.27.?>;復(fù)制代碼如果對(duì)"Cherry"使用這個(gè)函數(shù)：print_r(get_path('Cherry')),就會(huì)得到這樣的一個(gè)數(shù)組了:1.Array(2.[0]=>Food3.[1]=>Fruit4.[2]=>Red5.)復(fù)制代碼接下來(lái)如何把它打印成你希望的格式，就是你的事情了

缺點(diǎn)：這種方法很簡(jiǎn)單，容易理解，好上手。但是也有一些缺點(diǎn)。主要是因?yàn)檫\(yùn)行速度很慢，由于得到每個(gè)節(jié)點(diǎn)都需要進(jìn)行數(shù)據(jù)庫(kù)查詢，數(shù)據(jù)量大的時(shí)候要進(jìn)行很多查詢才能完成一個(gè)樹。另外由于要進(jìn)行遞歸運(yùn)算，遞歸的每一級(jí)都需要占用一些內(nèi)存所以在空間利用上效率也比較低。2、預(yù)排序遍歷樹算法現(xiàn)在讓我們看一看另外一種不使用遞歸計(jì)算，更加快速的方法，這就是預(yù)排序遍歷樹算法(modifiedpreordertreetraversalalgorithm)這種方法大家可能接觸的比較少，初次使用也不像上面的方法容易理解，但是由于這種方法不使用遞歸查詢算法，有更高的查詢效率。我們首先將多級(jí)數(shù)據(jù)按照下面的方式畫在紙上，在根節(jié)點(diǎn)Food的左側(cè)寫上1然后沿著這個(gè)樹繼續(xù)向下在Fruit的左側(cè)寫上2然后繼續(xù)前進(jìn)，沿著整個(gè)樹的邊緣給每一個(gè)節(jié)點(diǎn)都標(biāo)上左側(cè)和右側(cè)的數(shù)字。最后一個(gè)數(shù)字是標(biāo)在Food右側(cè)的18。在下面的這張圖中你可以看到整個(gè)標(biāo)好了數(shù)字的多級(jí)結(jié)構(gòu)(。沒有看懂？用你的手指指著數(shù)字從1數(shù)到18就明白怎么回事了。還不明白，再數(shù)一遍，注意移動(dòng)你的手指)。這些數(shù)字標(biāo)明了各個(gè)節(jié)點(diǎn)之間的關(guān)系，"Red”的號(hào)是3和6,它是"Food"1-18的子孫節(jié)點(diǎn)。同樣，我們可以看到所有左值大于2和右值小于11的節(jié)點(diǎn)都是”Fruit"2-11的子孫節(jié)點(diǎn)以下是代碼：1.1Food.5.2Fruit1112Meat.2Fruit1112Meat176.8.9.Red67Yellow1013Beef14 15Pork1610.復(fù)制代碼這樣整個(gè)樹狀結(jié)構(gòu)可以通過(guò)左右值來(lái)存儲(chǔ)到數(shù)據(jù)庫(kù)中。繼續(xù)之前，我們看一看下面整理過(guò)的數(shù)據(jù)表。以下是代碼：+ + + + +|parent|name|lft|rgt|+ + + + +4.||Food4.||Food|1I185.|Food |Fruit|2I116.|Fruit|RedI3I67.|Red |CherryI4I58.|Fruit|YellowI7I109.|Yellow|BananaI8I910.|Food |MeatI12I1711.|Meat |BeefI13I1412.|Meat |PorkI15I1613.+II|||||||復(fù)制代碼注意：由于"left"和"right"在SQL中有特殊的意義，所以我們需要用"lft"和"rgt"來(lái)表示左右字段。另外這種結(jié)構(gòu)中不再需要"parent"字段來(lái)表示樹狀結(jié)構(gòu)。也就是說(shuō)下面這樣的表結(jié)構(gòu)就足夠了。以下是代碼：1.+ 十 -+ 十2.InameIlftIrgtI3 丄3. 十■十 -■十 十4.IFoodI1I18I5.IFruitI2I11I6.|Red1316|7.|Cherry141 5 |8.|Yellow1711019.|Banana181 9 |10.|Meat112117 |11.|Beef113114 |12.|Pork115116|13.+-+ -+ +復(fù)制代碼好了我們現(xiàn)在可以從數(shù)據(jù)庫(kù)中獲取數(shù)據(jù)了，例如我們需要得到"Fruit"項(xiàng)下的所有所有節(jié)點(diǎn)就可以這樣寫查詢語(yǔ)句：SELECT*FROMtreeWHERElftBETWEEN2AND11；復(fù)制代碼這個(gè)查詢得到了以下的結(jié)果。以下是代碼：1. +2. |name十 -|lft十 十Irgt|3 i3. 十十 -■十 十4.|Fruit12I11I5.|RedI3I6I6.|CherryI4I5I7.|YellowI7I10I8.|BananaI8I9I9. + + + +復(fù)制代碼看到了吧，只要一個(gè)查詢就可以得到所有這些節(jié)點(diǎn)。為了能夠像上面的遞歸函數(shù)那樣顯示整個(gè)樹狀結(jié)構(gòu)，我們還需要對(duì)這樣的查詢進(jìn)行排序。用節(jié)點(diǎn)的左值進(jìn)行排序：1.SELECT*FROMtreeWHERElftBETWEEN2AND11ORDERBYlftASC；

..7.28.復(fù)制代碼剩下的問(wèn)題如何顯示層級(jí)的縮進(jìn)了。以下是代碼：<?phpfunctiondisplay」ree($root){//得到根節(jié)點(diǎn)的左右值$result=mysql_query("SELECTlft,rgtFROMtreewherename='".$root."'?";);$row=mysql_fetch_array($result);//準(zhǔn)備一個(gè)空的右值堆棧$right=array();//獲得根基點(diǎn)的所有子孫節(jié)點(diǎn)$result=mysql_query("SELECTname,lft,rgtFROMtreeWHERElftBETWEEN'".$row['lft']."'AND'".$row['rgt'].ORDERBYlftASC;";);//顯示每一行while($row=mysql_fetch_array($result)){//onlycheckstackifthereisoneif(count($right)>0){//檢查我們是否應(yīng)該將節(jié)點(diǎn)移出堆棧while($right[count($right)-1]<$row['rgt']){array_pop($right);}

}//縮進(jìn)顯示節(jié)點(diǎn)的名稱echostr_repeat('',count($right)).$row['name']."\n";//將這個(gè)節(jié)點(diǎn)加入到堆棧中$right[]=$row['rgt'];TOC\o"1-5"\h\z}}?>復(fù)制代碼如果你運(yùn)行一下以上的函數(shù)就會(huì)得到和遞歸函數(shù)一樣的結(jié)果。只是我們的這個(gè)新的函數(shù)可能會(huì)更快一些，因?yàn)橹挥?次數(shù)據(jù)庫(kù)查詢。要獲知一個(gè)節(jié)點(diǎn)的路徑就更簡(jiǎn)單了，如果我們想知道Cherry的路徑就利用它的左右值4和5來(lái)做一個(gè)查詢。1.SELECTnameFROMtreeWHERElft<4ANDrgt>;5ORDERBYlftASC；復(fù)制代碼這樣就會(huì)得到以下的結(jié)果：以下是代碼：1.+--2.|name33.十4.|Food5.|Fruit6.|Red7.+--復(fù)制代碼那么某個(gè)節(jié)點(diǎn)到底有多少子孫節(jié)點(diǎn)呢？很簡(jiǎn)單，子孫總數(shù)=(右值-左值-1)/21.descendants=(right-left-1)/2復(fù)制代碼不相信？自己算一算啦。用這個(gè)簡(jiǎn)單的公式，我們可以很快的算出”Fruit2-11”節(jié)點(diǎn)有4個(gè)子孫節(jié)點(diǎn)，而"Banana8-9"節(jié)點(diǎn)沒有子孫節(jié)點(diǎn)，也就是說(shuō)它不是一個(gè)父節(jié)點(diǎn)了。很神奇吧？雖然我已經(jīng)多次用過(guò)這個(gè)方法，但是每次這樣做的時(shí)候還是感到很神奇。這的確是個(gè)很好的辦法，但是有什么辦法能夠幫我們建立這樣有左右值的數(shù)據(jù)表呢？這里再介紹一個(gè)函數(shù)給大家，這個(gè)函數(shù)可以將name和parent結(jié)構(gòu)的表自動(dòng)轉(zhuǎn)換成帶有左右值的數(shù)據(jù)表。以下是代碼：1.<?php2.functionrebuild_tree($parent,$left){3.//therightvalueofthisnodeistheleftvalue+14.$right=$left+1;5.//getallchildrenofthisnode6.$result=mysql_query("7.SELECTname8.FROMtree9.whereparent='".$parent."'10.?";11.12.while($row=mysql_fetch_array($result)){13.//recursiveexecutionofthisfunctionforeach14.//childofthisnode15.//$rightisthecurrentrightvalue,whichis16.//incrementedbytherebuild_treefunction17.$right=rebuild_tree($row['name'],$right);18.}19.//we'vegottheleftvalue,andnowthatwe'veprocessed20.//thechildrenofthisnodewealsoknowtherightvalue21.mysql_query("22.updatetree23.SETWHEREname='".$parent."'TOC\o"1-5"\h\z;"）；//returntherightvalueofthisnode+1return $right +1;}?>復(fù)制代碼當(dāng)然這個(gè)函數(shù)是一個(gè)遞歸函數(shù)，我們需要從根節(jié)點(diǎn)開始運(yùn)行這個(gè)函數(shù)來(lái)重建一個(gè)帶有左右值的樹1.rebuild_tree（'Food',1）;復(fù)制代碼這個(gè)函數(shù)看上去有些復(fù)雜，但是它的作用和手工對(duì)表進(jìn)行編號(hào)一樣，就是將立體多層結(jié)構(gòu)的轉(zhuǎn)換成一個(gè)帶有左右值的數(shù)據(jù)表。那么對(duì)于這樣的結(jié)構(gòu)我們?cè)撊绾卧黾樱潞蛣h除一個(gè)節(jié)點(diǎn)呢？增加一個(gè)節(jié)點(diǎn)一般有兩種方法：第一種，保留原有的name和parent結(jié)構(gòu)，用老方法向數(shù)據(jù)中添加數(shù)據(jù)，每增加一條數(shù)據(jù)以后使用rebuild_tree函數(shù)對(duì)整個(gè)結(jié)構(gòu)重新進(jìn)行一次編號(hào)。第二種，效率更高的辦法是改變所有位于新節(jié)點(diǎn)右側(cè)的數(shù)值。舉例來(lái)說(shuō)：我們想增加一種新的水果"Strawberry"（草莓）它將成為"Red"節(jié)點(diǎn)的最后一個(gè)子節(jié)點(diǎn)。首先我們需要為它騰出一些空間。"Red"的右值應(yīng)當(dāng)從6改成8，"Yellow7-10"的左右值則應(yīng)當(dāng)改成9-12。依次類推我們可以得知，如果要給新的值騰出空間需要給所有左右值大于5的節(jié)點(diǎn)（5是"Red"最后一個(gè)子節(jié)點(diǎn)的右值）加上2。所以我們這樣進(jìn)行數(shù)據(jù)庫(kù)操作：UPDATEtreeSETrgt=rgt+2WHERErgt>5;UPDATEtreeSETlft=lft+2WHERElft>5；復(fù)制代碼這樣就為新插入的值騰出了空間，現(xiàn)在可以在騰出的空間里建立一個(gè)新的數(shù)據(jù)節(jié)點(diǎn)了，它的左右值分別是6和7

復(fù)制代碼再做一次查詢看看吧！怎么樣？很快吧。四、結(jié)語(yǔ)好了，現(xiàn)在你可以用兩種不同的方法設(shè)計(jì)你的多級(jí)數(shù)據(jù)庫(kù)結(jié)構(gòu)了，采用何種方式完全取決于你個(gè)人的判斷，但是對(duì)于層次多數(shù)量大的結(jié)構(gòu)我更喜歡第二種方法。如果查詢量較小但是需要頻繁添加和更新的數(shù)據(jù)，則第一種方法更為簡(jiǎn)便。另外，如果數(shù)據(jù)庫(kù)支持的話你還可以將rebuild_tree（）和騰出空間的操作寫成數(shù)據(jù)庫(kù)端的觸發(fā)器函數(shù)，在插入和更新的時(shí)候自動(dòng)執(zhí)行，這樣可以得到更好的運(yùn)行效率，而且你添加新節(jié)點(diǎn)的SQL語(yǔ)句會(huì)變得更加簡(jiǎn)單。/redirect.php?tid=92550&goto=lastpost本帖最后由小霈于2009-5-1522:54編輯今天，給同學(xué)講課時(shí)，無(wú)意中看到自己幾年前（還在高中時(shí)~~）總結(jié)的一個(gè)無(wú)限分類回想當(dāng)年，逃課去搞PHP 不知道，大家還需要否，覺得當(dāng)時(shí)自己總結(jié)的還不錯(cuò)，發(fā)給大家，希望大家多提提意見啊數(shù)據(jù)庫(kù)結(jié)構(gòu):采用左右值編碼的保存該樹的數(shù)據(jù)記錄如下（設(shè)表名為tree）：c_id|name|left_node|right_node|商品 |1|18|食品|2|11|肉類|3|6TOC\o"1-5"\h\z|豬肉| 4 | 5|菜類| 7 |10|白菜| 8 | 97|電器|2|178|電視|13|149|電棒|15|16第一次看見上面的數(shù)據(jù)記錄，相信大部分人都不清楚左值(left_node)和右值(right_node)是根據(jù)什么規(guī)則計(jì)算出來(lái)的，而且，這種表設(shè)計(jì)似乎沒有保存父節(jié)點(diǎn)的信息。下面把左右值和樹結(jié)合起來(lái)，請(qǐng)看：1商品18+ +2食品11 12電器17+ +13電視+ +13電視1415電棒163肉類6 7菜類104豬肉5 8白菜9請(qǐng)用手指指著上圖中的數(shù)字，從1數(shù)到18，學(xué)習(xí)過(guò)數(shù)據(jù)結(jié)構(gòu)的朋友肯定會(huì)發(fā)現(xiàn)什么吧？對(duì)你手指移動(dòng)的順序就是對(duì)這棵樹的進(jìn)行先序遍歷的順序。接下來(lái)，讓我講述一下如何利用節(jié)點(diǎn)的左右值，得到該節(jié)點(diǎn)的父節(jié)點(diǎn)，子孫節(jié)點(diǎn)數(shù)量，及自己在樹中的層數(shù)。采用左右值編碼的設(shè)計(jì)方案，在進(jìn)行類別樹的遍歷時(shí)，由于只需進(jìn)行2次查詢，消除了遞歸，再加上查詢條件都為數(shù)字比較，效率極高，類別樹的記錄條目越多，執(zhí)行效率越高。(上面的部分應(yīng)該時(shí)我在網(wǎng)上COPY的吧?=.=???！)下面的應(yīng)用部分就是原創(chuàng)嘍~~)應(yīng)用某個(gè)節(jié)點(diǎn)到底有多少子孫節(jié)點(diǎn)？子孫總數(shù)=（父節(jié)點(diǎn)的右值-父節(jié)點(diǎn)的左值-1）/2以節(jié)點(diǎn)“食品”舉例，其子孫總數(shù)=（11-2-1）/2=4如何判斷某一節(jié)點(diǎn)下有沒有子節(jié)點(diǎn)？當(dāng)該節(jié)點(diǎn)左值-1等于其右值時(shí)，其下沒有子節(jié)點(diǎn)檢索某一父節(jié)點(diǎn)的所有子節(jié)點(diǎn)？假定我們要對(duì)節(jié)點(diǎn)“食品”及其子孫節(jié)點(diǎn)進(jìn)行先序遍歷的列表，只需使用如下一條sql語(yǔ)句：SELECT*FROM'tree'WHERE'left_node'BETWEEN2AND11ORDERBY'left_node'ASC如何取得父類？SELECT*FROM'tree'WHERE'left_node'<$left_nodeAND'right_node'>$right_node檢索之后如何列表？當(dāng)左值+1==右值時(shí)，該節(jié)點(diǎn)沒有子節(jié)點(diǎn)，則下一節(jié)點(diǎn)不為其子節(jié)點(diǎn)若下一節(jié)點(diǎn)的左值==上一節(jié)點(diǎn)右值+1，則2個(gè)節(jié)點(diǎn)是同級(jí)關(guān)系若下一節(jié)點(diǎn)的左值==上一節(jié)點(diǎn)的左值+1時(shí)，則第2個(gè)節(jié)點(diǎn)應(yīng)是第一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)若下一節(jié)點(diǎn)的左值-上一節(jié)點(diǎn)的右值>1時(shí)，則下一節(jié)點(diǎn)比上一節(jié)點(diǎn)高（下一節(jié)點(diǎn)的左值-上一節(jié)點(diǎn)的右值）級(jí)在某一父節(jié)點(diǎn)下添加一個(gè)子節(jié)點(diǎn)？1.要求該子節(jié)點(diǎn)為該父節(jié)點(diǎn)下排序第一的節(jié)點(diǎn)，則$left_node=父節(jié)點(diǎn)left_node+1,$right_node=$left_node+1;要求該節(jié)點(diǎn)位于父節(jié)點(diǎn)下一個(gè)子節(jié)點(diǎn)A后面，貝l」$left_node=節(jié)點(diǎn)A的right_node+l,$right_node=$left_node+1;要求該節(jié)點(diǎn)是位于父節(jié)點(diǎn)下排序最后一位的節(jié)點(diǎn)，貝$left_node=父節(jié)點(diǎn)right_node,$right_node=$left_node+l;Sql:UPDATE'tree'SET'right_node'='right_node'+2WHERE'right_node'>=$left_nodeUPDATE'tree'SET'left_node'='left_node'+2WHERE'left_node'>=$left_nodeINSERTINTO'tree'('name','left_node','right_node')VALUES('名字',$left_node,$right_node)移動(dòng)節(jié)點(diǎn)，包括其子節(jié)點(diǎn)至節(jié)點(diǎn)A下？設(shè)該節(jié)點(diǎn)左值$left_node,右值$right_node其子節(jié)點(diǎn)的數(shù)目為$count=($right_node-$left_node-1)/2,節(jié)點(diǎn)A左值為$A」eft_node,UPDATE'tree'SET'right_node'='right_node'-$right_node-$left_node-lWHERE'right_node'>$right_nodeAND'right_node'<$A_left_nodeUPDATE'tree'SET'left_node'='left_node'-$right_node-$left_node-1WHERE'left_node'>$right_nodeAND'left_node'<=$A_left_nodeUPDATE'tree'SET'left_node'='left_node'+$A_left_node-$right_node,'right_node'='right_node'+$A_left_node-$right_nodeWHERE'left_node'>=$left_nodeAND'right_node'<=$right_node刪除所有子節(jié)點(diǎn)？DELETEFROM'tree'WHERE'left_node'＞父節(jié)點(diǎn)的左值A(chǔ)ND'right_node'＞父節(jié)點(diǎn)的右值刪除一個(gè)節(jié)點(diǎn)及其子節(jié)點(diǎn)？在上例中的＜號(hào)＞號(hào)后面各加一個(gè)=號(hào)http://www.cublog.en/u/11995/showart527781.html<?php/***基于左右值排序的無(wú)限分類算法*數(shù)據(jù)庫(kù)結(jié)果為CREATETABLEom_catagory(CatagoryIDint(10)unsignedNOTNULLauto_increment,Namevarchar(50)default'',Lftint(10)unsignedNOTNULLdefault'0',Rgtint(10)unsignedNOTNULLdefault'0',PRIMARYKEY(id),KEYlft(lft),KEYrgt(rgt))*更多的關(guān)于左右值排序的例子*/jh/27/239532.html(/tech-resources/articles/hierarchical-data.html)*@author[email]psdshow@[/email]*@version1.0*@copyrightpsdshow*歡迎光臨我的個(gè)人日志*/classsortclass{/***Description*@var*@since1.0*@accessprivate*/var$db;/***Description*@var*@since1.0*@accessprivate*/var$tablefix;/***Shortdescription.*構(gòu)造函數(shù),引入數(shù)據(jù)庫(kù)操作類函數(shù)*Detaildescription*@paramnone*@globalnone*@since1.0*@accessprivate*@returnvoid*@updatedatetime*/functionsortclass(){global$db;$this->db=$db;$this->tablefix="om_";}//endfunc/***Shortdescription.*增加新的分類*Detaildescription*@paramnone*@globalnone*@since1.0*@accessprivate*@returnvoid*@updatedatetime*/functionaddsort($CatagoryID,$SortName){if($CatagoryID==0){$Lft=0;$Rgt=1;}else{$Result=$this->checkcatagory($CatagoryID);//取得父類的左值,右值$Lft=$Result['Lft'];$Rgt=$Result['Rgt'];$this->db->query("UPDATE、".$this->tablefix."catagory、SET、Lft、二'Lft'+2WHERE'Lft、>$Rgt〃)；$this->db->query("UPDATE'".$this-〉tablefix."catagory、SET、Rgt、二'Rgt'+2WHERE'Rgt'>=$Rgt")；}//插入if($this->db->query("INSERTINTO、".$this-〉tablefix."catagory、SET、Lft、二,$Rgt',、Rgt、='$Rgt'+l,、Name、='$SortName'")){//$this->referto("成功增加新的類別","JAVASCRIPT:HISTORY.BACK(1)",3);return1;}else{//$this->referto("增加新的類別失敗了","JAVASCRIPT:HISTORY.BACK(1)",3);return-1;}}//endfunc/**Shortdescription.刪除類別Detaildescription@param none@global none@since 1.0@access private@return void@update datetime*/functiondeletesort($CatagoryID){//取得被刪除類別的左右值,檢測(cè)是否有子類,如果有就一起刪除$Result=$this->checkcatagory($CatagoryID);$Lft=$Result[,Lft,];$Rgt=$Result[,Rgt,];//執(zhí)行刪除if($this->db->query("DELETEFROM、".$this-〉tablefix."catagory、WHERE'Lft'>=$LftAND'Rgt'<=$Rgt")){$Value=$Rgt-$Lft+1;//更新左右值$this->db->query("UPDATE'".$this->tablefix."catagory'SET'Lft'='Lft'-$ValueWHERE'Lft'>$Lft");$this->db->query("UPDATE'".$this->tablefix."catagory'SET'Rgt'='Rgt'-$ValueWHERE'Rgt'>$Rgt");//$this->referto("成功刪除類別","javascript:history.back(l)",3);return1;}else{//$this->referto("刪除類別失敗了","javascript:history.back(l)",3);return-1;}}//endfunc/**Shortdescription.1,所有子類,不包含自己;2包含自己的所有子類;3不包含自己所有父類4;包含自己所有父類Detaildescription@param none@global none@since 1.0@access private@return void@update datetime*/functiongetcatagory($CatagoryID,$type=1){$Result=$this->checkcatagory($CatagoryID);$Lft=$Result['Lft'];$Rgt=$Result['Rgt'];$SeekSQL二"SELECT*FROM'".$this-〉tablefix.〃catagory'WHERE";switch($type){case"1":$condition="'Lft'>$LftAND'Rgt'<$Rgt";break;case"2":$condition="'Lft'>=$LftAND'Rgt'<=$Rgt";break;case"3":$condition="'Lft'<$LftAND'Rgt'>$Rgt";break;case"4":$condition="'Lft'<=$LftAND'Rgt'>=$Rgt";break;default:$condition="'Lft'>$LftAND'Rgt'<$Rgt";}$SeekSQL.=$condition."ORDERBY'Lft'ASC〃;$Sorts=$this->db->getrows($SeekSQL);return$Sorts;}//endfunc/**Shortdescription.取得直屬父類Detaildescription@param none@global none@since 1.0@access private@return void@update datetime*/functiongetparent($CatagoryID){$Parent=$this->getcatagory($CatagoryID,3);return$Parent;}//endfunc/**Shortdescription.移動(dòng)類,如果類有子類也一并移動(dòng)Detaildescription@param none@global none@since 1.0@access private@return void@update datetime*/functionmovecatagory($SelfCatagoryID,$ParentCatagoryID){$SelfCatagory=$this->checkcatagory($SelfCatagoryID);$NewCatagory=$this->checkcatagory($ParentCatagoryID);$SelfLft=$SelfCatagory['Lft'];$SelfRgt=$SelfCatagory['Rgt'];$Value=$SelfRgt-$SelfLft;//取得所有分類的ID方便更新左右值$CatagoryIDS=$this->getcatagory($SelfCatagoryID,2);foreach($CatagoryIDSas$v){$IDS[]=$v['CatagoryID'];}$InIDS=implode(",",$IDS);$ParentLft=$NewCatagory['Lft'];$ParentRgt=$NewCatagory['Rgt'];//print_r($InIDS);//print_r($NewCatagory);//print_r($SelfCatagory);//exit;if($ParentRgt>$SelfRgt){$UpdateLeftSQL二"UPDATE、".$this-〉tablefix."catagory、SET、Lft、二、Lft、-$Value-lWHERE'Lft、>$SelfRgtAND'Rgt'<=$ParentRgt";$UpdateRightSQL二"UPDATE'".$this-〉tablefix."catagory、SET'Rgt'二、Rgt'-$Value-1WHERE'Rgt'>$SelfRgtAND'Rgt'<$ParentRgt";$TmpValue=$ParentRgt-$SelfRgt-1;$UpdateSelfSQL="UPDATE'".$this->tablefix."catagory'SET'Lft'='Lft'+$TmpValue,'Rgt'='Rgt'+$TmpValueWHERE'CatagoryID'IN($InIDS)";}else{$UpdateLeftSQL="UPDATE'".$this->tablefix."catagory'SET'Lft'='Lft'+$Value+1WHERE'Lft'>$ParentRgtAND'Lft'<$SelfLft";$UpdateRightSQL="UPDATE'".$this->tablefix."catagory'SET'Rgt'='Rgt'+$Value+1WHERE'Rgt'>=$ParentRgtAND'Rgt'<$SelfLft";$TmpValue=$SelfLft-$ParentRgt;$UpdateSelfSQL="UPDATE'".$this->tablefix."catagory'SET'Lft'='Lft'-$TmpValue,'Rgt'='Rgt'-$TmpValueWHERE'CatagoryID'IN($InIDS)";}$this->db->query($UpdateLeftSQL);$this->db->query($UpdateRightSQL);$this->db->query($UpdateSelfSQL);//$this->referto("成功移動(dòng)類別","javascript:history.back(l)",3);return1;}//endfunc/**Shortdescription.**Detaildescription*@paramnone*@globalnone*@since1.0*@accessprivate*@returnvoid*@updatedatetime*/functioncheckcatagory($CatagoryID){//檢測(cè)父類ID是否存在$SQL二"SELECT*FROM'〃.$this-〉tablefix.〃catagory'WHERE'CatagorylD、二'$CatagoryID'LIMIT1";$Result=$this->db->getrow($SQL);if(count($Result)<1){$this->referto("父類ID不存在，請(qǐng)檢查","javascript:history.back(1)",3);}return$Result;}//endfunc/**Shortdescription.*Detaildescription@par