三、實現(xiàn) 1、毗鄰目錄模式(adjacency list model) 這種模式我們經(jīng)常用到，很多的教程和書中也介紹過。我們通過給每個節(jié)點增加一個屬性 parent 來表示這個節(jié)點的父節(jié)點從而將整個樹狀結(jié)構(gòu)通過平面的表描述出來。根據(jù)這個原則，例子中的數(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的一個子節(jié)點，Green是Fruit的一個子節(jié)點。而根節(jié)點'Food'沒有父節(jié)點。 為了簡單地描述這個問題，這個例子中只用了name來表示一個記錄。 在實際的數(shù)據(jù)庫中，你需要用數(shù)字的id來標(biāo)示每個節(jié)點，數(shù)據(jù)庫的表結(jié)構(gòu)大概應(yīng)該像這樣：id, parent_id, name, descrīption。 有了這樣的表我們就可以通過數(shù)據(jù)庫保存整個多級樹狀結(jié)構(gòu)了。 顯示多級樹，如果我們需要顯示這樣的一個多級結(jié)構(gòu)需要一個遞歸函數(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) { // 獲得一個 父節(jié)點 $parent 的所有子節(jié)點 $result = mysql_query(" SELECT name FROM tree WHERE parent = '" . $parent . "' ;" ); // 顯示每個子節(jié)點 while ($row = mysql_fetch_array($result)) { // 縮進(jìn)顯示節(jié)點名稱 echo str_repeat(' ', $level) . $row['name'] . "/n"; //再次調(diào)用這個函數(shù)顯示子節(jié)點的子節(jié)點 display_children($row['name'], $level+1); } } ?
對整個結(jié)構(gòu)的根節(jié)點（Food）使用這個函數(shù)就可以打印出整個多級樹結(jié)構(gòu)，由于Food是根節(jié)點它的父節(jié)點是空的，所以這樣調(diào)用: display_children('',0)。將顯示整個樹的內(nèi)容： 復(fù)制代碼 代碼如下: Food Fruit Red Cherry Yellow Banana Meat Beef Pork
如果你只想顯示整個結(jié)構(gòu)中的一部分，比如說水果部分，就可以這樣調(diào)用：display_children('Fruit',0); 幾乎使用同樣的方法我們可以知道從根節(jié)點到任意節(jié)點的路徑。比如 Cherry 的路徑是 "Food Fruit Red"。 為了得到這樣的一個路徑我們需要從最深的一級"Cherry"開始， 查詢得到它的父節(jié)點"Red"把它添加到路徑中，然后我們再查詢Red的父節(jié)點并把它也添加到路徑中，以此類推直到最高層的"Food",以下是代碼： 復(fù)制代碼 代碼如下: ?php // $node 是那個最深的節(jié)點 function get_path($node) { // 查詢這個節(jié)點的父節(jié)點 $result = mysql_query(" SELECT parent FROM tree WHERE name = '" . $node ."' ;" ); $row = mysql_fetch_array($result); // 用一個數(shù)組保存路徑 $path = array(); // 如果不是根節(jié)點則繼續(xù)向上查詢 // (根節(jié)點沒有父節(jié)點) 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"使用這個函數(shù)：print_r(get_path('Cherry'))，就會得到這樣的一個數(shù)組了： 復(fù)制代碼 代碼如下: Array ( [0] = Food [1] = Fruit [2] = Red )
看到了吧，只要一個查詢就可以得到所有這些節(jié)點。為了能夠像上面的遞歸函數(shù)那樣顯示整個樹狀結(jié)構(gòu)，我們還需要對這樣的查詢進(jìn)行排序。用節(jié)點的左值進(jìn)行排序： 復(fù)制代碼 代碼如下: SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;
剩下的問題如何顯示層級的縮進(jìn)了。 以下是代碼： 復(fù)制代碼 代碼如下: ?php function display_tree($root) { // 得到根節(jié)點的左右值 $result = mysql_query(" SELECT lft, rgt FROM tree WHERE name = '" . $root . "' ;" ); $row = mysql_fetch_array($result); // 準(zhǔn)備一個空的右值堆棧 $right = array(); // 獲得根基點的所有子孫節(jié)點 $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é)點移出堆棧 while ($right[count($right) - 1] $row['rgt']) { array_pop($right); } } // 縮進(jìn)顯示節(jié)點的名稱 echo str_repeat(' ',count($right)) . $row['name'] . "/n"; // 將這個節(jié)點加入到堆棧中 $right[] = $row['rgt']; } } ?
如果你運(yùn)行一下以上的函數(shù)就會得到和遞歸函數(shù)一樣的結(jié)果。只是我們的這個新的函數(shù)可能會更快一些，因為只有2次數(shù)據(jù)庫查詢。 要獲知一個節(jié)點的路徑就更簡單了，如果我們想知道Cherry 的路徑就利用它的左右值4和5來做一個查詢。 復(fù)制代碼 代碼如下: SELECT name FROM tree WHERE lft 4 AND rgt 5 ORDER BY lft ASC;
這樣就會得到以下的結(jié)果： 以下是代碼： 復(fù)制代碼 代碼如下: +------------+ | name | +------------+ | Food | | Fruit | | Red | +------------+
不相信？自己算一算啦。 用這個簡單的公式，我們可以很快的算出"Fruit 2-11"節(jié)點有4個子孫節(jié)點，而"Banana 8-9"節(jié)點沒有子孫節(jié)點，也就是說它不是一個父節(jié)點了。 很神奇吧？雖然我已經(jīng)多次用過這個方法，但是每次這樣做的時候還是感到很神奇。 這的確是個很好的辦法，但是有什么辦法能夠幫我們建立這樣有左右值的數(shù)據(jù)表呢？這里再介紹一個函數(shù)給大家，這個函數(shù)可以將name和parent結(jié)構(gòu)的表自動轉(zhuǎn)換成帶有左右值的數(shù)據(jù)表。 以下是代碼： 復(fù)制代碼 代碼如下: ?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; } ?
