您好,登錄后才能下訂單哦!
今天就跟大家聊聊有關(guān)如何實(shí)現(xiàn)一個(gè)左右值無限分類算法,可能很多人都不太了解,為了讓大家更加了解,小編給大家總結(jié)了以下內(nèi)容,希望大家根據(jù)這篇文章可以有所收獲。
一、引言
產(chǎn)品分類,多級(jí)的樹狀結(jié)構(gòu)的論壇,郵件列表等許多地方我們都會(huì)遇到這樣的問題:如何存儲(chǔ)多級(jí)結(jié)構(gòu)的數(shù)據(jù)?在PHP的應(yīng)用中,提供后臺(tái)數(shù)據(jù)存儲(chǔ)的通常是關(guān)系型數(shù)據(jù)庫,它能夠保存大量的數(shù)據(jù),提供高效的數(shù)據(jù)檢索和更新服務(wù)。然而關(guān)系型數(shù)據(jù)的基本形式是縱橫交錯(cuò)的表,是一個(gè)平面的結(jié)構(gòu),如果要將多級(jí)樹狀結(jié)構(gòu)存儲(chǔ)在關(guān)系型數(shù)據(jù)庫里就需要進(jìn)行合理的翻譯工作。接下來我會(huì)將自己的所見所聞和一些實(shí)用的經(jīng)驗(yàn)和大家探討一下:
層級(jí)結(jié)構(gòu)的數(shù)據(jù)保存在平面的數(shù)據(jù)庫中基本上有兩種常用設(shè)計(jì)方法:
* 毗鄰目錄模式(adjacency list model)
* 預(yù)排序遍歷樹算法(modified preorder tree traversal algorithm)
我不是計(jì)算機(jī)專業(yè)的,也沒有學(xué)過什么數(shù)據(jù)結(jié)構(gòu)的東西,所以這兩個(gè)名字都是我自己按照字面的意思翻的,如果說錯(cuò)了還請多多指教。這兩個(gè)東西聽著好像很嚇人,其實(shí)非常容易理解。
二、模型
這里我用一個(gè)簡單食品目錄作為我們的示例數(shù)據(jù)。
我們的數(shù)據(jù)結(jié)構(gòu)是這樣的,以下是代碼:
復(fù)制代碼 代碼如下:
Food
|---Fruit
| |---Red
| | |--Cherry
| +---Yellow
| +--Banana
+---Meat
|--Beef
+--Pork
為了照顧那些英文一塌糊涂的PHP愛好者
復(fù)制代碼 代碼如下:
Food : 食物
Fruit : 水果
Red : 紅色
Cherry: 櫻桃
Yellow: 黃色
Banana: 香蕉
Meat : 肉類
Beef : 牛肉
Pork : 豬肉
三、實(shí)現(xiàn)
1、毗鄰目錄模式(adjacency list model)
這種模式我們經(jīng)常用到,很多的教程和書中也介紹過。我們通過給每個(gè)節(jié)點(diǎn)增加一個(gè)屬性 parent 來表示這個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)從而將整個(gè)樹狀結(jié)構(gòu)通過平面的表描述出來。根據(jù)這個(gè)原則,例子中的數(shù)據(jù)可以轉(zhuǎn)化成如下的表:
以下是代碼:
復(fù)制代碼 代碼如下:
+-----------------------+
| parent | name |
+-----------------------+
| | Food |
| Food | Fruit |
| Fruit | Green |
| Green | Pear |
| Fruit | Red |
| Red | Cherry |
| Fruit | Yellow |
| Yellow | Banana |
| Food | Meat |
| Meat | Beef |
| Meat | Pork |
+-----------------------+
我們看到 Pear 是Green的一個(gè)子節(jié)點(diǎn),Green是Fruit的一個(gè)子節(jié)點(diǎn)。而根節(jié)點(diǎn)'Food'沒有父節(jié)點(diǎn)。 為了簡單地描述這個(gè)問題,這個(gè)例子中只用了name來表示一個(gè)記錄。 在實(shí)際的數(shù)據(jù)庫中,你需要用數(shù)字的id來標(biāo)示每個(gè)節(jié)點(diǎn),數(shù)據(jù)庫的表結(jié)構(gòu)大概應(yīng)該像這樣:id, parent_id, name, descrīption。
有了這樣的表我們就可以通過數(shù)據(jù)庫保存整個(gè)多級(jí)樹狀結(jié)構(gòu)了。
顯示多級(jí)樹,如果我們需要顯示這樣的一個(gè)多級(jí)結(jié)構(gòu)需要一個(gè)遞歸函數(shù)。
以下是代碼:
復(fù)制代碼 代碼如下:
<?php
// $parent is the parent of the children we want to see
// $level is increased when we go deeper into the tree,
// used to display a nice indented tree
function display_children($parent, $level) {
// 獲得一個(gè) 父節(jié)點(diǎn) $parent 的所有子節(jié)點(diǎn)
$result = mysql_query("
SELECT name
FROM tree
WHERE parent = '" . $parent . "'
;"
);
// 顯示每個(gè)子節(jié)點(diǎn)
while ($row = mysql_fetch_array($result)) {
// 縮進(jìn)顯示節(jié)點(diǎn)名稱
echo str_repeat(' ', $level) . $row['name'] . "\n";
//再次調(diào)用這個(gè)函數(shù)顯示子節(jié)點(diǎn)的子節(jié)點(diǎn)
display_children($row['name'], $level+1);
}
}
?>
對整個(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('',0)。將顯示整個(gè)樹的內(nèi)容:
復(fù)制代碼 代碼如下:
Food
Fruit
Red
Cherry
Yellow
Banana
Meat
Beef
Pork
如果你只想顯示整個(gè)結(jié)構(gòu)中的一部分,比如說水果部分,就可以這樣調(diào)用:display_children('Fruit',0);
幾乎使用同樣的方法我們可以知道從根節(jié)點(diǎn)到任意節(jié)點(diǎn)的路徑。比如 Cherry 的路徑是 "Food >; Fruit >; Red"。 為了得到這樣的一個(gè)路徑我們需要從最深的一級(jí)"Cherry"開始, 查詢得到它的父節(jié)點(diǎn)"Red"把它添加到路徑中,然后我們再查詢Red的父節(jié)點(diǎn)并把它也添加到路徑中,以此類推直到最高層的"Food",以下是代碼:
復(fù)制代碼 代碼如下:
<?php
// $node 是那個(gè)最深的節(jié)點(diǎn)
function get_path($node) {
// 查詢這個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)
$result = mysql_query("
SELECT parent
FROM tree
WHERE name = '" . $node ."'
;"
);
$row = mysql_fetch_array($result);
// 用一個(gè)數(shù)組保存路徑
$path = array();
// 如果不是根節(jié)點(diǎn)則繼續(xù)向上查詢
// (根節(jié)點(diǎn)沒有父節(jié)點(diǎn))
if ($row['parent'] != '') {
// the last part of the path to $node, is the name
// of the parent of $node
$path[] = $row['parent'];
// we should add the path to the parent of this node
// to the path
$path = array_merge(get_path($row['parent']), $path);
}
// return the path
return $path;
}
?>;
如果對"Cherry"使用這個(gè)函數(shù):print_r(get_path('Cherry')),就會(huì)得到這樣的一個(gè)數(shù)組了:
復(fù)制代碼 代碼如下:
Array (
[0] => Food
[1] => Fruit
[2] => Red
)
接下來如何把它打印成你希望的格式,就是你的事情了。
缺點(diǎn):
這種方法很簡單,容易理解,好上手。但是也有一些缺點(diǎn)。主要是因?yàn)檫\(yùn)行速度很慢,由于得到每個(gè)節(jié)點(diǎn)都需要進(jìn)行數(shù)據(jù)庫查詢,數(shù)據(jù)量大的時(shí)候要進(jìn)行很多查詢才能完成一個(gè)樹。另外由于要進(jìn)行遞歸運(yùn)算,遞歸的每一級(jí)都需要占用一些內(nèi)存所以在空間利用上效率也比較低。
2、預(yù)排序遍歷樹算法
現(xiàn)在讓我們看一看另外一種不使用遞歸計(jì)算,更加快速的方法,這就是預(yù)排序遍歷樹算法(modified preorder tree traversal algorithm)
這種方法大家可能接觸的比較少,初次使用也不像上面的方法容易理解,但是由于這種方法不使用遞歸查詢算法,有更高的查詢效率。
我們首先將多級(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)
以下是代碼:
復(fù)制代碼 代碼如下:
1 Food 18
+------------------------------+
2 Fruit 11 12 Meat 17
+-------------+ +------------+
3 Red 6 7 Yellow 10 13 Beef 14 15 Pork 16
4 Cherry 5 8 Banana 9
這樣整個(gè)樹狀結(jié)構(gòu)可以通過左右值來存儲(chǔ)到數(shù)據(jù)庫中。繼續(xù)之前,我們看一看下面整理過的數(shù)據(jù)表。
以下是代碼:
復(fù)制代碼 代碼如下:
+----------+------------+-----+-----+
| parent | name | lft | rgt |
+----------+------------+-----+-----+
| | Food | 1 | 18 |
| Food | Fruit | 2 | 11 |
| Fruit | Red | 3 | 6 |
| Red | Cherry | 4 | 5 |
| Fruit | Yellow | 7 | 10 |
| Yellow | Banana | 8 | 9 |
| Food | Meat | 12 | 17 |
| Meat | Beef | 13 | 14 |
| Meat | Pork | 15 | 16 |
+----------+------------+-----+-----+
注意:由于"left"和"right"在 SQL中有特殊的意義,所以我們需要用"lft"和"rgt"來表示左右字段。 另外這種結(jié)構(gòu)中不再需要"parent"字段來表示樹狀結(jié)構(gòu)。也就是 說下面這樣的表結(jié)構(gòu)就足夠了。
以下是代碼:
復(fù)制代碼 代碼如下:
+------------+-----+-----+
| name | lft | rgt |
+------------+-----+-----+
| Food | 1 | 18 |
| Fruit | 2 | 11 |
| Red | 3 | 6 |
| Cherry | 4 | 5 |
| Yellow | 7 | 10 |
| Banana | 8 | 9 |
| Meat | 12 | 17 |
| Beef | 13 | 14 |
| Pork | 15 | 16 |
+------------+-----+-----+
好了我們現(xiàn)在可以從數(shù)據(jù)庫中獲取數(shù)據(jù)了,例如我們需要得到"Fruit"項(xiàng)下的所有所有節(jié)點(diǎn)就可以這樣寫查詢語句:
復(fù)制代碼 代碼如下:
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;
這個(gè)查詢得到了以下的結(jié)果。
以下是代碼:
復(fù)制代碼 代碼如下:
+------------+-----+-----+
| name | lft | rgt |
+------------+-----+-----+
| Fruit | 2 | 11 |
| Red | 3 | 6 |
| Cherry | 4 | 5 |
| Yellow | 7 | 10 |
| Banana | 8 | 9 |
+------------+-----+-----+
看到了吧,只要一個(gè)查詢就可以得到所有這些節(jié)點(diǎn)。為了能夠像上面的遞歸函數(shù)那樣顯示整個(gè)樹狀結(jié)構(gòu),我們還需要對這樣的查詢進(jìn)行排序。用節(jié)點(diǎn)的左值進(jìn)行排序:
復(fù)制代碼 代碼如下:
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;
剩下的問題如何顯示層級(jí)的縮進(jìn)了。
以下是代碼:
復(fù)制代碼 代碼如下:
<?php
function display_tree($root) {
// 得到根節(jié)點(diǎn)的左右值
$result = mysql_query("
SELECT lft, rgt
FROM tree
WHERE name = '" . $root . "'
;"
);
$row = mysql_fetch_array($result);
// 準(zhǔn)備一個(gè)空的右值堆棧
$right = array();
// 獲得根基點(diǎn)的所有子孫節(jié)點(diǎn)
$result = mysql_query("
SELECT name, lft, rgt
FROM tree
WHERE lft BETWEEN '" . $row['lft'] . "' AND '" . $row['rgt'] ."'
ORDER BY lft ASC
;"
);
// 顯示每一行
while ($row = mysql_fetch_array($result)) {
// only check stack if there is one
if (count($right) > 0) {
// 檢查我們是否應(yīng)該將節(jié)點(diǎn)移出堆棧
while ($right[count($right) - 1] < $row['rgt']) {
array_pop($right);
}
}
// 縮進(jìn)顯示節(jié)點(diǎn)的名稱
echo str_repeat(' ',count($right)) . $row['name'] . "\n";
// 將這個(gè)節(jié)點(diǎn)加入到堆棧中
$right[] = $row['rgt'];
}
}
?>
如果你運(yùn)行一下以上的函數(shù)就會(huì)得到和遞歸函數(shù)一樣的結(jié)果。只是我們的這個(gè)新的函數(shù)可能會(huì)更快一些,因?yàn)橹挥?次數(shù)據(jù)庫查詢。
要獲知一個(gè)節(jié)點(diǎn)的路徑就更簡單了,如果我們想知道Cherry 的路徑就利用它的左右值4和5來做一個(gè)查詢。
復(fù)制代碼 代碼如下:
SELECT name FROM tree WHERE lft < 4 AND rgt >; 5 ORDER BY lft ASC;
這樣就會(huì)得到以下的結(jié)果:
以下是代碼:
復(fù)制代碼 代碼如下:
+------------+
| name |
+------------+
| Food |
| Fruit |
| Red |
+------------+
那么某個(gè)節(jié)點(diǎn)到底有多少子孫節(jié)點(diǎn)呢?很簡單,子孫總數(shù)=(右值-左值-1)/2
復(fù)制代碼 代碼如下:
descendants = (right – left - 1) / 2
不相信?自己算一算啦。
用這個(gè)簡單的公式,我們可以很快的算出"Fruit 2-11"節(jié)點(diǎn)有4個(gè)子孫節(jié)點(diǎn),而"Banana 8-9"節(jié)點(diǎn)沒有子孫節(jié)點(diǎn),也就是說它不是一個(gè)父節(jié)點(diǎn)了。
很神奇吧?雖然我已經(jīng)多次用過這個(gè)方法,但是每次這樣做的時(shí)候還是感到很神奇。
這的確是個(gè)很好的辦法,但是有什么辦法能夠幫我們建立這樣有左右值的數(shù)據(jù)表呢?這里再介紹一個(gè)函數(shù)給大家,這個(gè)函數(shù)可以將name和parent結(jié)構(gòu)的表自動(dòng)轉(zhuǎn)換成帶有左右值的數(shù)據(jù)表。
以下是代碼:
復(fù)制代碼 代碼如下:
<?php
function rebuild_tree($parent, $left) {
// the right value of this node is the left value + 1
$right = $left+1;
// get all children of this node
$result = mysql_query("
SELECT name
FROM tree
WHERE parent = '" . $parent . "'
;"
);
while ($row = mysql_fetch_array($result)) {
// recursive execution of this function for each
// child of this node
// $right is the current right value, which is
// incremented by the rebuild_tree function
$right = rebuild_tree($row['name'], $right);
}
// we've got the left value, and now that we've processed
// the children of this node we also know the right value
mysql_query("
UPDATE tree
SET
lft = '" . $left . "',
rgt= '" . $right . "'
WHERE name = '" . $parent . "'
;"
);
// return the right value of this node + 1
return $right + 1;
}
?>
當(dāng)然這個(gè)函數(shù)是一個(gè)遞歸函數(shù),我們需要從根節(jié)點(diǎn)開始運(yùn)行這個(gè)函數(shù)來重建一個(gè)帶有左右值的樹
復(fù)制代碼 代碼如下:
rebuild_tree('Food',1);
這個(gè)函數(shù)看上去有些復(fù)雜,但是它的作用和手工對表進(jìn)行編號(hào)一樣,就是將立體多層結(jié)構(gòu)的轉(zhuǎn)換成一個(gè)帶有左右值的數(shù)據(jù)表。
那么對于這樣的結(jié)構(gòu)我們該如何增加,更新和刪除一個(gè)節(jié)點(diǎn)呢?
增加一個(gè)節(jié)點(diǎn)一般有兩種方法:
第一種,保留原有的name 和parent結(jié)構(gòu),用老方法向數(shù)據(jù)中添加數(shù)據(jù),每增加一條數(shù)據(jù)以后使用rebuild_tree函數(shù)對整個(gè)結(jié)構(gòu)重新進(jìn)行一次編號(hào)。
第二種,效率更高的辦法是改變所有位于新節(jié)點(diǎn)右側(cè)的數(shù)值。舉例來說:我們想增加一種新的水果"Strawberry"(草莓)它將成為"Red"節(jié)點(diǎn)的最后一個(gè)子節(jié)點(diǎn)。首先我們需要為它騰出一些空間。"Red"的右值應(yīng)當(dāng)從6改成8,"Yellow 7-10 "的左右值則應(yīng)當(dāng)改成 9-12。依次類推我們可以得知,如果要給新的值騰出空間需要給所有左右值大于5的節(jié)點(diǎn) (5 是"Red"最后一個(gè)子節(jié)點(diǎn)的右值) 加上2。所以我們這樣進(jìn)行數(shù)據(jù)庫操作:
復(fù)制代碼 代碼如下:
UPDATE tree SET rgt = rgt + 2 WHERE rgt > 5;
UPDATE tree SET lft = lft + 2 WHERE lft > 5;
這樣就為新插入的值騰出了空間,現(xiàn)在可以在騰出的空間里建立一個(gè)新的數(shù)據(jù)節(jié)點(diǎn)了, 它的左右值分別是6和7
復(fù)制代碼 代碼如下:
INSERT INTO tree SET lft=6, rgt=7, name='Strawberry';
看完上述內(nèi)容,你們對如何實(shí)現(xiàn)一個(gè)左右值無限分類算法有進(jìn)一步的了解嗎?如果還想了解更多知識(shí)或者相關(guān)內(nèi)容,請關(guān)注億速云行業(yè)資訊頻道,感謝大家的支持。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。