轉(zhuǎn)的地址忘了碟贾，如有侵權(quán)請@
預(yù)排序遍歷樹算法
現(xiàn)在讓我們看一看另外一種不使用遞歸計算锐墙，更加快速的方法织咧，這就是預(yù)排序遍歷樹算法(modified preorder tree traversal algorithm) 這種方法大家可能接觸的比較少八秃，初次使用也不像上面的方法容易理解薛闪，但是由于這種方法不使用遞歸查詢算法，有更高的查詢效率吱抚。
我們首先將多級數(shù)據(jù)按照下面的方式畫在紙上百宇，在根節(jié)點Food的左側(cè)寫上 1 然后沿著這個樹繼續(xù)向下 在 Fruit 的左側(cè)寫上 2 然后繼續(xù)前進，沿著整個樹的邊緣給每一個節(jié)點都標(biāo)上左側(cè)和右側(cè)的數(shù)字秘豹。最后一個數(shù)字是標(biāo)在Food 右側(cè)的 18携御。 在下面的這張圖中你可以看到整個標(biāo)好了數(shù)字的多級結(jié)構(gòu)。（沒有看懂既绕？用你的手指指著數(shù)字從1數(shù)到18就明白怎么回事了啄刹。還不明白，再數(shù)一遍凄贩，注意移動你的手指）誓军。
這些數(shù)字標(biāo)明了各個節(jié)點之間的關(guān)系，"Red"的號是3和6疲扎，它是 "Food" 1-18 的子孫節(jié)點昵时。 同樣，我們可以看到 所有左值大于2和右值小于11的節(jié)點 都是"Fruit" 2-11 的子孫節(jié)點
這樣整個樹狀結(jié)構(gòu)可以通過左右值來存儲到數(shù)據(jù)庫中椒丧。繼續(xù)之前债查，我們看一看下面整理過的數(shù)據(jù)表。
注意：由于"left"和"right"在 SQL中有特殊的意義瓜挽，所以我們需要用"lft"和"rgt"來表示左右字段。 另外這種結(jié)構(gòu)中不再需要"parent"字段來表示樹狀結(jié)構(gòu)征绸。也就是 說下面這樣的表結(jié)構(gòu)就足夠了久橙。
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;
看到了吧，只要一個查詢就可以得到所有這些節(jié)點管怠。為了能夠像上面的遞歸函數(shù)那樣顯示整個樹狀結(jié)構(gòu)淆衷，我們還需要對這樣的查詢進行排序。用節(jié)點的左值進行排序：
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;
那么某個節(jié)點到底有多少子孫節(jié)點呢渤弛？很簡單祝拯，子孫總數(shù)=(右值-左值-1)/2
descendants = (right – left - 1) / 2 ，如果不是很清楚這個公式，那就去翻下書佳头，我們在上數(shù)據(jù)結(jié)構(gòu)寫的很清楚鹰贵！
添加同一層次的節(jié)點的方法如下:
LOCK TABLES nested_category WRITE;
SELECT @myRight := rgt
FROM nested_category
WHERE name = 'Cherry';
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 ('Strawberry', @myRight + 1, @myRight + 2);
UNLOCK TABLES;
添加樹的子節(jié)點的方法如下：
LOCK TABLES nested_category WRITE;
SELECT @myLeft := lft
FROM nested_category
WHERE name = 'Beef';
UPDATE nested_category
SET rgt = rgt + 2
WHERE rgt > @myLeft;
UPDATE nested_category
SET lft = lft + 2
WHERE lft > @myLeft;
INSERT INTO nested_category (name, lft, rgt)
VALUES ('charqui', @myLeft + 1, @myLeft + 2);
UNLOCK TABLES;
每次插入節(jié)點之后都可以用以下SQL進行查看驗證：
SELECT CONCAT(REPEAT(' ', COUNT(parent.name) - 1), node.name) AS name
FROM nested_category node, nested_category parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
ORDER BY node.lft;
刪除節(jié)點的方法，稍微有點麻煩是有個中間變量,如下：
LOCK TABLES nested_category WRITE;
SELECT @myLeft := lft, @myRight := rgt
, @myWidth := rgt - lft + 1
FROM nested_category
WHERE name = 'Cherry';
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;
