三、實(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)。 為了簡(jiǎ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); } } ?
對(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('',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"把它添加到路徑中，然后我們?cè)俨樵僐ed的父節(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; } ?
如果對(duì)"Cherry"使用這個(gè)函數(shù)：print_r(get_path('Cherry'))，就會(huì)得到這樣的一個(gè)數(shù)組了： 復(fù)制代碼 代碼如下: Array ( [0] = Food [1] = Fruit [2] = Red )
好了我們現(xiàn)在可以從數(shù)據(jù)庫中獲取數(shù)據(jù)了，例如我們需要得到"Fruit"項(xiàng)下的所有所有節(jié)點(diǎn)就可以這樣寫查詢語句： 復(fù)制代碼 代碼如下: SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;
看到了吧，只要一個(gè)查詢就可以得到所有這些節(jié)點(diǎn)。為了能夠像上面的遞歸函數(shù)那樣顯示整個(gè)樹狀結(jié)構(gòu)，我們還需要對(duì)這樣的查詢進(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)的路徑就更簡(jiǎ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ǎn)單的公式，我們可以很快的算出"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 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; } ?
