從喜悅村上轉載，以前也讀過此文，講述得還是比較清楚的。

  產品分類，多級的樹狀結構的論壇，郵件列表等許多地方我們都會遇到這樣的問題：如何存儲多級結構的數據？
  
  在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:豬肉
  
  毗鄰目錄模式(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, 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 的子孫節點