1、鄰接表(adjacency list model)
2、預排序遍歷樹算法(modified preorder tree traversal algorithm)
用壹下的例子討論這兩種方法的差異：
現有壹棵樹如下：
鄰接表模式：
這種模式我們經常用到，很多的教程和書中也介紹過。我們通過給每個節點增加壹個屬性 parent 來表示這個節點的父節點從而將整個樹狀結構通過平面的表描述出來。根據這個原則，例子中的數據可以轉化成如下的表:
我們看到 Pear 是Green的壹個子節點，Green是Fruit的壹個子節點。而根節點'Food'沒有父節點。 為了簡單地描述這個問題， 這個例子中只用了name來表示壹個記錄。 在實際的數據庫中，妳需要用數字的id來標示每個節點，數據庫的表結構大概應該像這樣：id, parent_id, name, description。
以下是代碼：
<?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
)
接下來如何把它打印成妳希望的格式，就是妳的事情了。
缺點：
這種方法很簡單，容易理解，好上手。但是也有壹些缺點。主要是因為運行速度很慢，由於得到每個節點都需要進行數據庫查詢，數據量大的時候要進行很多查詢才能完成壹個樹。另外由於要進行遞歸運算，遞歸的每壹級都需要占用壹些內存所以在空間利用上效率也比較低。
預排序遍歷樹算法
現在讓我們看壹看另外壹種不使用遞歸計算，更加快速的方法，這就是預排序遍歷樹算法(modified preorder tree traversal algorithm) 這種方法大家可能接觸的比較少，初次使用也不像上面的方法容易理解，但是由於這種方法不使用遞歸查詢算法，有更高的查詢效率。
我們首先將多級數據按照下面的方式畫在紙上，在根節點Food的左側寫上 1 然後沿著這個樹繼續向下 在 Fruit 的左側寫上 2 然後繼續前進，沿著整個樹的邊緣給每壹個節點都標上左側和右側的數字。最後壹個數字是標在Food 右側的 18。 在下面的這張圖中妳可以看到整個標好了數字的多級結構。（沒有看懂？用妳的手指指著數字從1數到18就明白怎麽回事了。還不明白，再數壹遍，註意移動妳的手指）。
這些數字標明了各個節點之間的關系，"Red"的號是3和6，它是 "Food" 1-18 的子孫節點。 同樣，我們可以看到 所有左值大於2和右值小於11的節點 都是"Fruit" 2-11 的子孫節點
這樣整個樹狀結構可以通過左右值來存儲到數據庫中。繼續之前，我們看壹看下面整理過的數據表。
註意：由於"left"和"right"在 SQL中有特殊的意義，所以我們需要用"lft"和"rgt"來表示左右字段。 另外這種結構中不再需要"parent"字段來表示樹狀結構。也就是 說下面這樣的表結構就足夠了。
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;
看到了吧，只要壹個查詢就可以得到所有這些節點。為了能夠像上面的遞歸函數那樣顯示整個樹狀結構，我們還需要對這樣的查詢進行排序。用節點的左值進行排序：
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;