解析左右值無限分類的實現算法

2020-03-22 20:24:25

字體：大中小

來源：轉載

供稿：網友

一、引言
產品分類，多級的樹狀結構的論壇，郵件列表等許多地方我們都會遇到這樣的問題：如何存儲多級結構的數據？在PHP的應用中，提供后臺數據存儲的通常是關系型數據庫，它能夠保存大量的數據，提供高效的數據檢索和更新服務。然而關系型數據的基本形式是縱橫交錯的表，是一個平面的結構，如果要將多級樹狀結構存儲在關系型數據庫里就需要進行合理的翻譯工作。接下來我會將自己的所見所聞和一些實用的經驗和大家探討一下：
層級結構的數據保存在平面的數據庫中基本上有兩種常用設計方法：
* 毗鄰目錄模式(adjacency list model)
* 預排序遍歷樹算法(modified preorder tree traversal algorithm)
我不是計算機專業的，也沒有學過什么數據結構的東西，所以這兩個名字都是我自己按照字面的意思翻的，如果說錯了還請多多指教。這兩個東西聽著好像很嚇人，其實非常容易理解。二、模型
這里我用一個簡單食品目錄作為我們的示例數據。
我們的數據結構是這樣的，以下是代碼：
復制代碼代碼如下:
Food

|---Fruit

| |---Red

| | |--Cherry

| +---Yellow

| +--Banana

+---Meat
|--Beef
+--Pork

為了照顧那些英文一塌糊涂的PHP愛好者
復制代碼代碼如下:
Food : 食物
Fruit : 水果
Red : 紅色
Cherry: 櫻桃
Yellow: 黃色
Banana: 香蕉
Meat : 肉類
Beef : 牛肉
Pork : 豬肉

三、實現
1、毗鄰目錄模式(adjacency list model)
這種模式我們經常用到，很多的教程和書中也介紹過。我們通過給每個節點增加一個屬性 parent 來表示這個節點的父節點從而將整個樹狀結構通過平面的表描述出來。根據這個原則，例子中的數據可以轉化成如下的表：
以下是代碼：
復制代碼代碼如下:
+-----------------------+
| 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的一個子節點，Green是Fruit的一個子節點。而根節點'Food'沒有父節點。為了簡單地描述這個問題，這個例子中只用了name來表示一個記錄。在實際的數據庫中，你需要用數字的id來標示每個節點，數據庫的表結構大概應該像這樣：id, parent_id, name, descrīption。
有了這樣的表我們就可以通過數據庫保存整個多級樹狀結構了。
顯示多級樹，如果我們需要顯示這樣的一個多級結構需要一個遞歸函數。
以下是代碼：
復制代碼代碼如下:
?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) {
// 獲得一個父節點 $parent 的所有子節點
$result = mysql_query("
SELECT name
FROM tree
WHERE parent = '" . $parent . "'
;"
);
// 顯示每個子節點
while ($row = mysql_fetch_array($result)) {
// 縮進顯示節點名稱
echo str_repeat(' ', $level) . $row['name'] . "/n";
//再次調用這個函數顯示子節點的子節點
display_children($row['name'], $level+1);
}
}
?

對整個結構的根節點（Food）使用這個函數就可以打印出整個多級樹結構，由于Food是根節點它的父節點是空的，所以這樣調用: display_children('',0)。將顯示整個樹的內容：
復制代碼代碼如下:
Food
Fruit
Red
Cherry
Yellow
Banana
Meat
Beef
Pork

如果你只想顯示整個結構中的一部分，比如說水果部分，就可以這樣調用：display_children('Fruit',0);
幾乎使用同樣的方法我們可以知道從根節點到任意節點的路徑。比如 Cherry 的路徑是 "Food Fruit Red"。為了得到這樣的一個路徑我們需要從最深的一級"Cherry"開始，查詢得到它的父節點"Red"把它添加到路徑中，然后我們再查詢Red的父節點并把它也添加到路徑中，以此類推直到最高層的"Food",以下是代碼：
復制代碼代碼如下:
?php
// $node 是那個最深的節點
function get_path($node) {
// 查詢這個節點的父節點
$result = mysql_query("
SELECT parent
FROM tree
WHERE name = '" . $node ."'
;"
);
$row = mysql_fetch_array($result);
// 用一個數組保存路徑
$path = array();
// 如果不是根節點則繼續向上查詢
// (根節點沒有父節點)
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"使用這個函數：print_r(get_path('Cherry'))，就會得到這樣的一個數組了：
復制代碼代碼如下:
Array (
[0] = Food
[1] = Fruit
[2] = Red
)

接下來如何把它打印成你希望的格式，就是你的事情了。
缺點：
這種方法很簡單，容易理解，好上手。但是也有一些缺點。主要是因為運行速度很慢，由于得到每個節點都需要進行數據庫查詢，數據量大的時候要進行很多查詢才能完成一個樹。另外由于要進行遞歸運算，遞歸的每一級都需要占用一些內存所以在空間利用上效率也比較低。

2、預排序遍歷樹算法
現在讓我們看一看另外一種不使用遞歸計算，更加快速的方法，這就是預排序遍歷樹算法(modified preorder tree traversal algorithm)
這種方法大家可能接觸的比較少，初次使用也不像上面的方法容易理解，但是由于這種方法不使用遞歸查詢算法，有更高的查詢效率。

我們首先將多級數據按照下面的方式畫在紙上，在根節點Food的左側寫上 1 然后沿著這個樹繼續向下在 Fruit 的左側寫上 2 然后繼續前進，沿著整個樹的邊緣給每一個節點都標上左側和右側的數字。最后一個數字是標在Food 右側的 18。在下面的這張圖中你可以看到整個標好了數字的多級結構。（沒有看懂？用你的手指指著數字從1數到18就明白怎么回事了。還不明白，再數一遍，注意移動你的手指）。
這些數字標明了各個節點之間的關系，"Red"的號是3和6，它是 "Food" 1-18 的子孫節點。同樣，我們可以看到所有左值大于2和右值小于11的節點都是"Fruit" 2-11 的子孫節點
以下是代碼：
復制代碼代碼如下:
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

這樣整個樹狀結構可以通過左右值來存儲到數據庫中。繼續之前，我們看一看下面整理過的數據表。
以下是代碼：
復制代碼代碼如下:
+----------+------------+-----+-----+
| 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"來表示左右字段。另外這種結構中不再需要"parent"字段來表示樹狀結構。也就是說下面這樣的表結構就足夠了。
以下是代碼：
復制代碼代碼如下:
+------------+-----+-----+
| 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 |
+------------+-----+-----+

好了我們現在可以從數據庫中獲取數據了，例如我們需要得到"Fruit"項下的所有所有節點就可以這樣寫查詢語句：
復制代碼代碼如下:
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;

這個查詢得到了以下的結果。
以下是代碼：
復制代碼代碼如下:
+------------+-----+-----+
| name | lft | rgt |
+------------+-----+-----+
| Fruit | 2 | 11 |
| Red | 3 | 6 |
| Cherry | 4 | 5 |
| Yellow | 7 | 10 |
| Banana | 8 | 9 |
+------------+-----+-----+

看到了吧，只要一個查詢就可以得到所有這些節點。為了能夠像上面的遞歸函數那樣顯示整個樹狀結構，我們還需要對這樣的查詢進行排序。用節點的左值進行排序：
復制代碼代碼如下:
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;

剩下的問題如何顯示層級的縮進了。
以下是代碼：
復制代碼代碼如下:
?php
function display_tree($root) {
// 得到根節點的左右值
$result = mysql_query("
SELECT lft, rgt
FROM tree
WHERE name = '" . $root . "'
;"
);
$row = mysql_fetch_array($result);
// 準備一個空的右值堆棧
$right = array();
// 獲得根基點的所有子孫節點
$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) {
// 檢查我們是否應該將節點移出堆棧
while ($right[count($right) - 1] $row['rgt']) {
array_pop($right);
}
}
// 縮進顯示節點的名稱
echo str_repeat(' ',count($right)) . $row['name'] . "/n";
// 將這個節點加入到堆棧中
$right[] = $row['rgt'];
}
}
?

如果你運行一下以上的函數就會得到和遞歸函數一樣的結果。只是我們的這個新的函數可能會更快一些，因為只有2次數據庫查詢。
要獲知一個節點的路徑就更簡單了，如果我們想知道Cherry 的路徑就利用它的左右值4和5來做一個查詢。
復制代碼代碼如下:
SELECT name FROM tree WHERE lft 4 AND rgt 5 ORDER BY lft ASC;

這樣就會得到以下的結果：
以下是代碼：
復制代碼代碼如下:
+------------+
| name |
+------------+
| Food |
| Fruit |
| Red |
+------------+

那么某個節點到底有多少子孫節點呢？很簡單，子孫總數=(右值-左值-1)/2
復制代碼代碼如下:
descendants = (right – left - 1) / 2

不相信？自己算一算啦。
用這個簡單的公式，我們可以很快的算出"Fruit 2-11"節點有4個子孫節點，而"Banana 8-9"節點沒有子孫節點，也就是說它不是一個父節點了。
很神奇吧？雖然我已經多次用過這個方法，但是每次這樣做的時候還是感到很神奇。
這的確是個很好的辦法，但是有什么辦法能夠幫我們建立這樣有左右值的數據表呢？這里再介紹一個函數給大家，這個函數可以將name和parent結構的表自動轉換成帶有左右值的數據表。
以下是代碼：
復制代碼代碼如下:
?php
function rebuild_tree($parent, $left) {
// the right html' target='_blank'>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;
}
?

當然這個函數是一個遞歸函數，我們需要從根節點開始運行這個函數來重建一個帶有左右值的樹
復制代碼代碼如下:
rebuild_tree('Food',1);

這個函數看上去有些復雜，但是它的作用和手工對表進行編號一樣，就是將立體多層結構的轉換成一個帶有左右值的數據表。
那么對于這樣的結構我們該如何增加，更新和刪除一個節點呢？
增加一個節點一般有兩種方法：
第一種，保留原有的name 和parent結構，用老方法向數據中添加數據，每增加一條數據以后使用rebuild_tree函數對整個結構重新進行一次編號。
第二種，效率更高的辦法是改變所有位于新節點右側的數值。舉例來說：我們想增加一種新的水果"Strawberry"（草莓）它將成為"Red"節點的最后一個子節點。首先我們需要為它騰出一些空間。"Red"的右值應當從6改成8，"Yellow 7-10 "的左右值則應當改成 9-12。依次類推我們可以得知，如果要給新的值騰出空間需要給所有左右值大于5的節點（5 是"Red"最后一個子節點的右值）加上2。所以我們這樣進行數據庫操作：
復制代碼代碼如下:
UPDATE tree SET rgt = rgt + 2 WHERE rgt
UPDATE tree SET lft = lft + 2 WHERE lft

這樣就為新插入的值騰出了空間，現在可以在騰出的空間里建立一個新的數據節點了，它的左右值分別是6和7
復制代碼代碼如下:
INSERT INTO tree SET lft=6, rgt=7, name='Strawberry';

再做一次查詢看看吧！怎么樣？很快吧。四、結語
好了，現在你可以用兩種不同的方法設計你的多級數據庫結構了，采用何種方式完全取決于你個人的判斷，但是對于層次多數量大的結構我更喜歡第二種方法。如果查詢量較小但是需要頻繁添加和更新的數據，則第一種方法更為簡便。
另外，如果數據庫支持的話你還可以將rebuild_tree()和騰出空間的操作寫成數據庫端的觸發器函數，在插入和更新的時候自動執行，這樣可以得到更好的運行效率，而且你添加新節點的SQL語句會變得更加簡單。
PHP教程

鄭重聲明：本文版權歸原作者所有，轉載文章僅為傳播更多信息之目的，如作者信息標記有誤，請第一時間聯系我們修改或刪除，多謝。

上一篇：PHP簡單選擇排序算法學習

下一篇：php排序算法：php快速排序的算法原理及算法實現