PHP技巧實(shí)例：樹(shù)形結(jié)構(gòu)的算法

2024-09-08 23:18:44

字體：大中小

供稿：網(wǎng)友

從喜悅村上轉(zhuǎn)載，以前也讀過(guò)此文，講述得還是比較清楚的。
產(chǎn)品分類，多級(jí)的樹(shù)狀結(jié)構(gòu)的論壇，郵件列表等許多地方我們都會(huì)遇到這樣的問(wèn)題：如何存儲(chǔ)多級(jí)結(jié)構(gòu)的數(shù)據(jù)？

在php的應(yīng)用中，提供后臺(tái)數(shù)據(jù)存儲(chǔ)的通常是關(guān)系型數(shù)據(jù)庫(kù)，它能夠保存大量的數(shù)據(jù)，提供高效的數(shù)據(jù)檢索和更新服務(wù)。然而關(guān)系型數(shù)據(jù)的基本形式是縱橫交錯(cuò)的表，是一個(gè)平面的結(jié)構(gòu)，如果要將多級(jí)樹(shù)狀結(jié)構(gòu)存儲(chǔ)在關(guān)系型數(shù)據(jù)庫(kù)里就需要進(jìn)行合理的翻譯工作。接下來(lái)我會(huì)將自己的所見(jiàn)所聞和一些實(shí)用的經(jīng)驗(yàn)和大家探討一下。

層級(jí)結(jié)構(gòu)的數(shù)據(jù)保存在平面的數(shù)據(jù)庫(kù)中基本上有兩種常用設(shè)計(jì)方法：

毗鄰目錄模式(adjacency list model)
預(yù)排序遍歷樹(shù)算法(modified preorder tree traversal algorithm)
我不是計(jì)算機(jī)專業(yè)的，也沒(méi)有學(xué)過(guò)什么數(shù)據(jù)結(jié)構(gòu)的東西，所以這兩個(gè)名字都是我自己按照字面的意思翻的，如果說(shuō)錯(cuò)了還請(qǐng)多多指教。

這兩個(gè)東西聽(tīng)著好像很嚇人，其實(shí)非常容易理解。這里我用一個(gè)簡(jiǎn)單食品目錄作為我們的示例數(shù)據(jù)。我們的數(shù)據(jù)結(jié)構(gòu)是這樣的:

food:食物
fruit:水果
red:紅色
cherry:櫻桃
yellow:黃色
banana:香蕉
meat:肉類
beef:牛肉
pork:豬肉

毗鄰目錄模式(adjacency list model)

這種模式我們經(jīng)常用到，很多的教程和書(shū)中也介紹過(guò)。我們通過(guò)給每個(gè)節(jié)點(diǎn)增加一個(gè)屬性 parent 來(lái)表示這個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)從而將整個(gè)樹(shù)狀結(jié)構(gòu)通過(guò)平面的表描述出來(lái)。根據(jù)這個(gè)原則，例子中的數(shù)據(jù)可以轉(zhuǎn)化成如下的表：

顯示多級(jí)樹(shù)
如果我們需要顯示這樣的一個(gè)多級(jí)結(jié)構(gòu)需要一個(gè)遞歸函數(shù)。

<?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í)樹(shù)結(jié)構(gòu)，由于food是根節(jié)點(diǎn)它的父節(jié)點(diǎn)是空的，所以這樣調(diào)用: display_children('',0)。將顯示整個(gè)樹(shù)的內(nèi)容：

food
fruit
red
cherry
yellow
banana
meat
beef
pork
如果你只想顯示整個(gè)結(jié)構(gòu)中的一部分，比如說(shuō)水果部分，就可以這樣調(diào)用：

display_children('fruit',0);

幾乎使用同樣的方法我們可以知道從根節(jié)點(diǎn)到任意節(jié)點(diǎn)的路徑。比如 cherry 的路徑是　"food > fruit > red"。為了得到這樣的一個(gè)路徑我們需要從最深的一級(jí)"cherry"開(kāi)始，查詢得到它的父節(jié)點(diǎn)"red"把它添加到路徑中，然后我們?cè)俨樵價(jià)ed的父節(jié)點(diǎn)并把它也添加到路徑中，以此類推直到最高層的"food"

<?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)沒(méi)有父節(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ù)組了：

array
(
[0] => food
[1] => fruit
[2] => red
)
接下來(lái)如何把它打印成你希望的格式，就是你的事情了。
缺點(diǎn)：這種方法很簡(jiǎn)單，容易理解，好上手。但是也有一些缺點(diǎn)。主要是因?yàn)檫\(yùn)行速度很慢，由于得到每個(gè)節(jié)點(diǎn)都需要進(jìn)行數(shù)據(jù)庫(kù)查詢，數(shù)據(jù)量大的時(shí)候要進(jìn)行很多查詢才能完成一個(gè)樹(shù)。另外由于要進(jìn)行遞歸運(yùn)算，遞歸的每一級(jí)都需要占用一些內(nèi)存所以在空間利用上效率也比較低。

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

我們首先將多級(jí)數(shù)據(jù)按照下面的方式畫(huà)在紙上，在根節(jié)點(diǎn)food的左側(cè)寫(xiě)上 1 然后沿著這個(gè)樹(shù)繼續(xù)向下在 fruit 的左側(cè)寫(xiě)上 2 然后繼續(xù)前進(jìn)，沿著整個(gè)樹(shù)的邊緣給每一個(gè)節(jié)點(diǎn)都標(biāo)上左側(cè)和右側(cè)的數(shù)字。最后一個(gè)數(shù)字是標(biāo)在food 右側(cè)的 18。在下面的這張圖中你可以看到整個(gè)標(biāo)好了數(shù)字的多級(jí)結(jié)構(gòu)。（沒(méi)有看懂？用你的手指指著數(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)

這樣整個(gè)樹(shù)狀結(jié)構(gòu)可以通過(guò)左右值來(lái)存儲(chǔ)到數(shù)據(jù)庫(kù)中。繼續(xù)之前，我們看一看下面整理過(guò)的數(shù)據(jù)表。

+-----------------------+-----+-----+
| 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"來(lái)表示左右字段。另外這種結(jié)構(gòu)中不再需要"parent"字段來(lái)表示樹(shù)狀結(jié)構(gòu)。也就是說(shuō)下面這樣的表結(jié)構(gòu)就足夠了。

+------------+-----+-----+
| 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ù)庫(kù)中獲取數(shù)據(jù)了，例如我們需要得到"fruit"項(xiàng)下的所有所有節(jié)點(diǎn)就可以這樣寫(xiě)查詢語(yǔ)句： select * from tree where lft between 2 and 11; 這個(gè)查詢得到了以下的結(jié)果。

+------------+-----+-----+
| name | lft | rgt |
+------------+-----+-----+
| fruit | 2 | 11 |
| red | 3 | 6 |
| cherry | 4 | 5 |
| yellow | 7 | 10 |
| banana | 8 | 9 |
+------------+-----+-----+
看到了吧，只要一個(gè)查詢就可以得到所有這些節(jié)點(diǎn)。為了能夠像上面的遞歸函數(shù)那樣顯示整個(gè)樹(shù)狀結(jié)構(gòu)，我們還需要對(duì)這樣的查詢進(jìn)行排序。用節(jié)點(diǎn)的左值進(jìn)行排序：

select * from tree where lft between 2 and 11 order by lft asc;
剩下的問(wèn)題如何顯示層級(jí)的縮進(jìn)了。

<?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ù)庫(kù)查詢。要獲知一個(gè)節(jié)點(diǎn)的路徑就更簡(jiǎn)單了，如果我們想知道cherry 的路徑就利用它的左右值4和5來(lái)做一個(gè)查詢。

select name from tree where lft < 4 and rgt > 5 order by lft asc;
這樣就會(huì)得到以下的結(jié)果：

+------------+
| name |
+------------+
| food |
| fruit |
| red |
+------------+
那么某個(gè)節(jié)點(diǎn)到底有多少子孫節(jié)點(diǎn)呢？很簡(jiǎn)單，子孫總數(shù)=(右值-左值-1)/2 descendants = (right – left - 1) / 2 不相信？自己算一算啦。用這個(gè)簡(jiǎn)單的公式，我們可以很快的算出"fruit 2-11"節(jié)點(diǎn)有4個(gè)子孫節(jié)點(diǎn)，而"banana 8-9"節(jié)點(diǎn)沒(méi)有子孫節(jié)點(diǎn)，也就是說(shuō)它不是一個(gè)父節(jié)點(diǎn)了。
很神奇吧？雖然我已經(jīng)多次用過(guò)這個(gè)方法，但是每次這樣做的時(shí)候還是感到很神奇。

這的確是個(gè)很好的辦法，但是有什么辦法能夠幫我們建立這樣有左右值的數(shù)據(jù)表呢？這里再介紹一個(gè)函數(shù)給大家，這個(gè)函數(shù)可以將name和parent結(jié)構(gòu)的表自動(dòng)轉(zhuǎn)換成帶有左右值的數(shù)據(jù)表。

<?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)開(kāi)始運(yùn)行這個(gè)函數(shù)來(lái)重建一個(gè)帶有左右值的樹(shù)

rebuild_tree('food',1);
這個(gè)函數(shù)看上去有些復(fù)雜，但是它的作用和手工對(duì)表進(jìn)行編號(hào)一樣，就是將立體多層結(jié)構(gòu)的轉(zhuǎn)換成一個(gè)帶有左右值的數(shù)據(jù)表。

那么對(duì)于這樣的結(jié)構(gòu)我們?cè)撊绾卧黾?，更新和刪除一個(gè)節(jié)點(diǎn)呢？增加一個(gè)節(jié)點(diǎn)一般有兩種方法：

保留原有的name 和parent結(jié)構(gòu)，用老方法向數(shù)據(jù)中添加數(shù)據(jù)，每增加一條數(shù)據(jù)以后使用rebuild_tree函數(shù)對(duì)整個(gè)結(jié)構(gòu)重新進(jìn)行一次編號(hào)。
效率更高的辦法是改變所有位于新節(jié)點(diǎn)右側(cè)的數(shù)值。舉例來(lái)說(shuō)：我們想增加一種新的水果"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ù)庫(kù)操作：

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

insert into tree set lft=6, rgt=7, name='strawberry';

再做一次查詢看看吧！怎么樣？很快吧。
好了，現(xiàn)在你可以用兩種不同的方法設(shè)計(jì)你的多級(jí)數(shù)據(jù)庫(kù)結(jié)構(gòu)了，采用何種方式完全取決于你個(gè)人的判斷，但是對(duì)于層次多數(shù)量大的結(jié)構(gòu)我更喜歡第二種方法。如果查詢量較小但是需要頻繁添加和更新的數(shù)據(jù)，則第一種方法更為簡(jiǎn)便。

另外，如果數(shù)據(jù)庫(kù)支持的話你還可以將 rebuild_tree() 和騰出空間的操作寫(xiě)成數(shù)據(jù)庫(kù)端的觸發(fā)器函數(shù)，在插入和更新的時(shí)候自動(dòng)執(zhí)行，這樣可以得到更好的運(yùn)行效率，而且你添加新節(jié)點(diǎn)的sql語(yǔ)句會(huì)變得更加簡(jiǎn)單。
類遞歸法
posted by 訪客 on 2004, may 31 - 9:18am.
我用類遞歸法寫(xiě)了段程序，跟文章中的遞歸不完全一樣
正準(zhǔn)備移植到 xoops 中:
http://dev.xoops.org/modules/xfmod/project/?ulink

已經(jīng)出現(xiàn)內(nèi)存溢出現(xiàn)象
不過(guò)準(zhǔn)備繼續(xù)采用遞歸法，只是需要繼續(xù)改進(jìn)

希望有機(jī)會(huì)跟各位討論cms
» reply to this comment
還是兩種方法之比較
posted by 訪客 on 2004, march 17 - 8:30pm.
　　仔細(xì)研究了一下這篇文章，覺(jué)得受益非淺，但后來(lái)又想了想，覺(jué)得有一下問(wèn)題（為了好記憶，毗鄰目錄模式我稱為遞歸的方法，預(yù)排序遍歷樹(shù)算法我稱為預(yù)排序樹(shù)的方法）：

1、兩種方法比較大的區(qū)別是遞歸是在查詢的時(shí)候要用到堆棧進(jìn)行遞歸，預(yù)排序樹(shù)則是在更新節(jié)點(diǎn)時(shí)要進(jìn)行半數(shù)（指所插入節(jié)點(diǎn)的后半部分）節(jié)點(diǎn)的更新。雖然您也說(shuō)了，如果節(jié)點(diǎn)多了，更新又頻繁，預(yù)排序樹(shù)效率會(huì)降低，采用遞歸會(huì)好些，而如果節(jié)點(diǎn)層次較多的話，首先遞歸會(huì)導(dǎo)致堆棧溢出，再者遞歸本身效率就不高，加上每一層遞歸都要操作數(shù)據(jù)庫(kù)，總體效果也不會(huì)理想。我目前的做法是一次性把數(shù)據(jù)全取出來(lái)，然后對(duì)數(shù)組進(jìn)行遞歸操作，會(huì)好一些；再進(jìn)一步改進(jìn)的話，可以為每行記錄增加一個(gè)root根節(jié)點(diǎn)（目前是只記錄相鄰的父節(jié)點(diǎn)），這樣在查找分支樹(shù)時(shí)效率就會(huì)比較高了，更新樹(shù)的時(shí)候也是十分便捷的，應(yīng)該是一種比較好的方式。

2、改進(jìn)遞歸的方式，文章中在計(jì)算預(yù)排序樹(shù)節(jié)點(diǎn)的左右值的時(shí)候其實(shí)也用到了一種遍歷方式，通過(guò)數(shù)組替代堆棧，手工實(shí)現(xiàn)壓棧和彈出；這種方法如果引用到遞歸算法中，在進(jìn)行遞歸的時(shí)候也用數(shù)組替代堆棧的話，也可以提高遞歸的效率的。

3、并發(fā)，如果考慮到并發(fā)的情況，尤其是更新樹(shù)的時(shí)候，預(yù)排序樹(shù)大面積更新節(jié)點(diǎn)信息的方法需要額外注意采用加鎖和事務(wù)的機(jī)制保證數(shù)據(jù)一致性。

4、多根節(jié)點(diǎn)或者多父節(jié)點(diǎn)的情況，在這種情況下，顯然就不是一個(gè)標(biāo)準(zhǔn)的二叉樹(shù)或者多叉樹(shù)了，預(yù)排序樹(shù)算法需要進(jìn)行比較大的改進(jìn)才能適應(yīng)，而遞歸的方法則應(yīng)用自如，所以在這種情況下，遞歸的適應(yīng)性較強(qiáng)。這是當(dāng)然的了，因?yàn)檫f歸的方法就是鏈表的一種形式，樹(shù)、圖都可以用鏈表來(lái)表達(dá)，當(dāng)然適應(yīng)力強(qiáng)了。

5、直觀，如果不用程序操作，直接觀察數(shù)據(jù)庫(kù)中存儲(chǔ)的數(shù)據(jù)的話，顯然遞歸方式下存儲(chǔ)的數(shù)據(jù)比較直觀，而預(yù)排序樹(shù)的數(shù)據(jù)很難直接閱讀（針對(duì)層次關(guān)系來(lái)說(shuō)），這在數(shù)據(jù)交換中是不是會(huì)有影響呢？

　　總體來(lái)說(shuō)，我個(gè)人比較喜歡用遞歸的方法，但一直擔(dān)心遞歸對(duì)效率的影響，所幸還沒(méi)有接觸過(guò)規(guī)模較大的分類層次，遞歸用數(shù)組替代堆棧會(huì)是一種比較好的改進(jìn)方法。而預(yù)排序樹(shù)不失為一種解決簡(jiǎn)單樹(shù)的高效方法，用習(xí)慣了，也應(yīng)該是非常出色的，尤其是它從葉子節(jié)點(diǎn)到根節(jié)點(diǎn)的反向查找非常方便。

fwolf
www.fwolf.com
» reply to this comment
非常高興看到你的回復(fù)
posted by shuke on 2004, march 18 - 5:47am.
非常高興你這么認(rèn)真的讀完這篇文章。這篇文章其實(shí)是原來(lái)發(fā)表在sitepoint.com上的，我把它翻譯了一下，希望給希望初學(xué)入門(mén)的朋友介紹一些方法，拋磚引玉。你的方法也很好，有機(jī)會(huì)我會(huì)試一下的。（如果你有興趣的話，何不就上面的例子把你的方法和具體實(shí)現(xiàn)的代碼也寫(xiě)成教程發(fā)出來(lái)吧，這樣大家就用更加實(shí)際的例子來(lái)模仿了）如果你對(duì)數(shù)據(jù)庫(kù)中保存多級(jí)結(jié)構(gòu)有興趣研究的話，這里還有兩個(gè)連接也很不錯(cuò)可以作為參考：
介紹了常見(jiàn)的4中方法
一次查詢，數(shù)組排序的腳本我想你的腳本肯定比這個(gè)強(qiáng)。
另外我看到你也用drupal，它還有一個(gè)高級(jí)功能叫分布式用戶驗(yàn)證系統(tǒng)，只要在任何一個(gè)drupal的站點(diǎn)注冊(cè)以后就可以登錄訪問(wèn)其它的drupal站點(diǎn)了。挺有意思的。
祝好！
» reply to this comment
用循環(huán)來(lái)建樹(shù)已經(jīng)實(shí)現(xiàn)了
posted by 訪客 on 2004, march 25 - 10:10pm.
你上次提供的資料我已經(jīng)都看過(guò)了，不過(guò)老實(shí)說(shuō)，第一篇文章里沒(méi)有太多新東西，或許是我沒(méi)看太明白吧，第二個(gè)居然是php3寫(xiě)的，程序結(jié)構(gòu)沒(méi)有細(xì)看，用到太多的函數(shù)交叉。
正好我在一個(gè)系統(tǒng)中用戶角色要用到分級(jí)，按照數(shù)組的思路就把遍歷寫(xiě)了下來(lái)，沒(méi)有時(shí)間整理，先放到這里你看看吧，數(shù)據(jù)庫(kù)用的是adodb，程序是直接從系統(tǒng)中摘出來(lái)的，希望能夠描述得清楚，主要是利用了php強(qiáng)大的數(shù)組操作，用循環(huán)來(lái)進(jìn)行遞歸。注釋里是一種相近的方法，只是處理結(jié)果的時(shí)機(jī)不同而已。

<?php
/**
* 顯示列表
* @access public
*/
function displist()
{
//不縮進(jìn)的顯示方式
// $this->misdisplistindex = true;
// echo('<a href="?action=new&part=role">增加新角色</a>　　'); _fcksavedurl=""?action=new&part=role">增加新角色</a>　　');"
//
// $this->mlisttitle = '用戶角色列表';
// $this->setdataoption('list');
//
// $this->setquerytable( array($this->mtableuserrole) );
//
// //查詢順序
// $this->setqueryorder( 'asc', $this->mtableuserrole, 'sequence' );
//
// $this->query('list');
// parent::displist();

// //另外一種顯示方式，用數(shù)組作為堆棧，a: 壓棧時(shí)存role，壓完就刪除source
// $this->checkproperty('mrdb');
// $this->checkproperty('mrsql');
// $this->mrsql->select('role, title, parent');
// $this->mrsql->from($this->mtableuserrole);
// $this->mrsql->orderby('parent, sequence');
// $this->mrs = $this->mrdb->execute($this->mrsql->sql());
// if (0 < count($this->mrs))
// {
// $source = & $this->mrs->getarray(); //數(shù)字索引
// $stack = array(''); //堆棧
// $stacki = array(-1); //和堆棧對(duì)應(yīng)，記錄堆棧中數(shù)據(jù)在樹(shù)中的層次
// $target = array();
// while (0 < count($stack))
// {
// $item = array_shift($stack);
// $lev = array_shift($stacki);
// if (!empty($item))
// {
// //在這里把加工過(guò)的數(shù)據(jù)放到target數(shù)組
// array_push($target, str_repeat(' ', $lev) . $item);
// //$s1 = str_repeat(' ', $lev) . $item;
// }
// $del = array(); //要從$source中刪除的節(jié)點(diǎn)
// $ar = array(); //需要添加到堆棧中的節(jié)點(diǎn)
// foreach ($source as $key=>$val)
// {
// //尋找匹配的子節(jié)點(diǎn)
// if (empty($item))
// {
// $find = empty($source[$key]['parent']);
// }
// else
// {
// $find = ($item == $source[$key]['parent']);
// }
// if ($find)
// {
// array_unshift($ar, $source[$key]['role']);
// $del[] = $key;
// }
// }
// foreach ($ar as $val)
// {
// array_unshift($stack, $val);
// array_unshift($stacki, $lev + 1);
// }
// foreach ($del as $val)
// {
// unset($source[$val]);
// }
// echo(implode(', ', $stack) . ' ' . implode(', ', $stacki) . ' ' . implode(', ', $target) . ' ');
// }
// debug_array();
// }
// else
// {
// echo('<center>沒(méi)有檢索到數(shù)據(jù)</center>');
// }

//另外一種顯示方式，用數(shù)組作為堆棧，b: 壓棧時(shí)存數(shù)組索引，出棧并使用完后再刪除source
$this->checkproperty('mrdb');
$this->checkproperty('mrsql');
$this->mrsql->select('role, title, parent');
$this->mrsql->from($this->mtableuserrole);
$this->mrsql->orderby('parent, sequence');
$this->mrs = $this->mrdb->execute($this->mrsql->sql());
if (!empty($this->mrs) && !$this->mrs->eof)
{
$source = & $this->mrs->getarray(); //數(shù)字索引
$stack = array(-1); //堆棧
$stacki = array(-1); //和堆棧對(duì)應(yīng)，記錄堆棧中數(shù)據(jù)在樹(shù)中的層次
$target = array();
while (0 < count($stack))
{
$item = array_shift($stack);
$lev = array_shift($stacki);
if (-1 != $item)
{
//在這里把加工過(guò)的數(shù)據(jù)放到target數(shù)組
$s1 = str_repeat(' ', $lev) . '<a href="?action=disp&part=role&role=' . $source[$item]['role'] . '">' . $source[$item]['title'] . '</a>';
$s2 = '<a href="?action=edit&part=role&role=' . $source[$item]['role'] . '">編輯</a>　<a href="?action=delete&part=role&role=' . $source[$item]['role'] . '">刪除</a>';
array_push($target, array($s1, $s2));
}
$del = array(); //要從$source中刪除的節(jié)點(diǎn)
$ar = array(); //需要添加到堆棧中的節(jié)點(diǎn)
foreach ($source as $key=>$val)
{
//尋找匹配的子節(jié)點(diǎn)
if (-1 == $item)
{
$find = empty($source[$key]['parent']);
}
else
{
$find = ($source[$item]['role'] == $source[$key]['parent']);
}
if ($find)
{
array_unshift($ar, $key);
}
}
foreach ($ar as $val)
{
array_unshift($stack, $val);
array_unshift($stacki, $lev + 1);
}
//從source中刪除
unset($source[$item]);
//echo(implode(', ', $stack) . ' ' . implode(', ', $stacki) . ' ' . implode(', ', $target) . ' ');
}
//輸出
echo('<a href="?action=new&part=role">增加新角色</a>　　');
array_unshift($target, array('角色', '操作'));
$this->checkproperty('mrlt');
$this->mrlt->setdata($target);
$this->mrlt->mlisttitle = '用戶角色列表';
$this->mrlt->misdispindex = false;
$this->mrlt->disp();
}
else
{
echo('<center>沒(méi)有檢索到數(shù)據(jù)</center>');
}
} // end of function displist
?>