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

  產(chǎn)品分類，多級的樹狀結(jié)構(gòu)的論壇，郵件列表等許多地方我們都會遇到這樣的問題：如何存儲多級結(jié)構(gòu)的數(shù)據(jù)？
  
  在php的應(yīng)用中，提供后臺數(shù)據(jù)存儲的通常是關(guān)系型數(shù)據(jù)庫，它能夠保存大量的數(shù)據(jù)，提供高效的數(shù)據(jù)檢索和更新服務(wù)。然而關(guān)系型數(shù)據(jù)的基本形式是縱橫交錯的表，是一個平面的結(jié)構(gòu)，如果要將多級樹狀結(jié)構(gòu)存儲在關(guān)系型數(shù)據(jù)庫里就需要進(jìn)行合理的翻譯工作。接下來我會將自己的所見所聞和一些實(shí)用的經(jīng)驗(yàn)和大家探討一下。
  
  層級結(jié)構(gòu)的數(shù)據(jù)保存在平面的數(shù)據(jù)庫中基本上有兩種常用設(shè)計方法：
  
  毗鄰目錄模式(adjacency list model)
  預(yù)排序遍歷樹算法(modified preorder tree traversal algorithm)
  我不是計算機(jī)專業(yè)的，也沒有學(xué)過什么數(shù)據(jù)結(jié)構(gòu)的東西，所以這兩個名字都是我自己按照字面的意思翻的，如果說錯了還請多多指教。
  
  這兩個東西聽著好像很嚇人，其實(shí)非常容易理解。這里我用一個簡單食品目錄作為我們的示例數(shù)據(jù)。 我們的數(shù)據(jù)結(jié)構(gòu)是這樣的:
  
  
  food
  |
  |---fruit
  | |
  | |---red
  | | |
  | | |--cherry
  | |
  | |---yellow
  | |
  | |--banana
  |
  |---meat
  |
  |--beef
  |
  |--pork
  為了照顧那些英文一塌糊涂的php愛好者
  
  food:食物
  fruit:水果
  red:紅色
  cherry:櫻桃
  yellow:黃色
  banana:香蕉
  meat:肉類
  beef:牛肉
  pork:豬肉
  
  毗鄰目錄模式(adjacency list model)
  
  這種模式我們經(jīng)常用到，很多的教程和書中也介紹過。我們通過給每個節(jié)點(diǎn)增加一個屬性 parent 來表示這個節(jié)點(diǎn)的父節(jié)點(diǎn)從而將整個樹狀結(jié)構(gòu)通過平面的表描述出來。根據(jù)這個原則，例子中的數(shù)據(jù)可以轉(zhuǎn)化成如下的表：
  
  +-----------------------+
  | 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é)點(diǎn)，green是fruit的一個子節(jié)點(diǎn)。而根節(jié)點(diǎn)'food'沒有父節(jié)點(diǎn)。 為了簡單地描述這個問題， 這個例子中只用了name來表示一個記錄。 在實(shí)際的數(shù)據(jù)庫中，你需要用數(shù)字的id來標(biāo)示每個節(jié)點(diǎn)，數(shù)據(jù)庫的表結(jié)構(gòu)大概應(yīng)該像這樣：id, parent_id, name, description。有了這樣的表我們就可以通過數(shù)據(jù)庫保存整個多級樹狀結(jié)構(gòu)了。
  
  顯示多級樹
  如果我們需要顯示這樣的一個多級結(jié)構(gòu)需要一個遞歸函數(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)
  {
  // 獲得一個 父節(jié)點(diǎn) $parent 的所有子節(jié)點(diǎn)
  $result = mysql_query('select name from tree '.
  'where parent="'.$parent.'";');
  
  // 顯示每個子節(jié)點(diǎn)
  while ($row = mysql_fetch_array($result))
  {
  // 縮進(jìn)顯示節(jié)點(diǎn)名稱
  echo str_repeat(' ',$level).$row['name']."n";
  
  //再次調(diào)用這個函數(shù)顯示子節(jié)點(diǎn)的子節(jié)點(diǎn)
  
  display_children($row['name'], $level+1);
  }
  }
  ?>
  對整個結(jié)構(gòu)的根節(jié)點(diǎn)（food）使用這個函數(shù)就可以打印出整個多級樹結(jié)構(gòu)，由于food是根節(jié)點(diǎn)它的父節(jié)點(diǎn)是空的，所以這樣調(diào)用: display_children('',0)。將顯示整個樹的內(nèi)容：
  
  
  food
  fruit
  red
  cherry
  yellow
  banana
  meat
  beef
  pork
  如果你只想顯示整個結(jié)構(gòu)中的一部分，比如說水果部分，就可以這樣調(diào)用：
  
  display_children('fruit',0);
  
  幾乎使用同樣的方法我們可以知道從根節(jié)點(diǎn)到任意節(jié)點(diǎn)的路徑。比如 cherry 的路徑是　"food > fruit > red"。 為了得到這樣的一個路徑我們需要從最深的一級"cherry"開始， 查詢得到它的父節(jié)點(diǎn)"red"把它添加到路徑中， 然后我們再查詢red的父節(jié)點(diǎn)并把它也添加到路徑中，以此類推直到最高層的"food"
  
  <?php
  // $node 是那個最深的節(jié)點(diǎn)
  function get_path($node)
  {
  // 查詢這個節(jié)點(diǎn)的父節(jié)點(diǎn)
  $result = mysql_query('select parent from tree '.
  'where name="'.$node.'";');
  $row = mysql_fetch_array($result);
  
  // 用一個數(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;
  }
  ?>
  如果對"cherry"使用這個函數(shù)：print_r(get_path('cherry'))，就會得到這樣的一個數(shù)組了：
  
  
  array
  (
  [0] => food
  [1] => fruit
  [2] => red
  )
  接下來如何把它打印成你希望的格式，就是你的事情了。
  缺點(diǎn)：這種方法很簡單，容易理解，好上手。但是也有一些缺點(diǎn)。主要是因?yàn)檫\(yùn)行速度很慢，由于得到每個節(jié)點(diǎn)都需要進(jìn)行數(shù)據(jù)庫查詢，數(shù)據(jù)量大的時候要進(jìn)行很多查詢才能完成一個樹。另外由于要進(jìn)行遞歸運(yùn)算，遞歸的每一級都需要占用一些內(nèi)存所以在空間利用上效率也比較低。
  
  現(xiàn)在讓我們看一看另外一種不使用遞歸計算，更加快速的方法，這就是預(yù)排序遍歷樹算法(modified preorder tree traversal algorithm) 這種方法大家可能接觸的比較少，初次使用也不像上面的方法容易理解，但是由于這種方法不使用遞歸查詢算法，有更高的查詢效率。
  
  我們首先將多級數(shù)據(jù)按照下面的方式畫在紙上，在根節(jié)點(diǎn)food的左側(cè)寫上 1 然后沿著這個樹繼續(xù)向下 在 fruit 的左側(cè)寫上 2 然后繼續(xù)前進(jìn)，沿著整個樹的邊緣給每一個節(jié)點(diǎn)都標(biāo)上左側(cè)和右側(cè)的數(shù)字。最后一個數(shù)字是標(biāo)在food 右側(cè)的 18。 在下面的這張圖中你可以看到整個標(biāo)好了數(shù)字的多級結(jié)構(gòu)。（沒有看懂？用你的手指指著數(shù)字從1數(shù)到18就明白怎么回事了。還不明白，再數(shù)一遍，注意要移動你的手指）。
  這些數(shù)字標(biāo)明了各個節(jié)點(diǎn)之間的關(guān)系，"red"的號是3和6，它是 "food" 1-18 的子孫節(jié)點(diǎn)。 同樣，我們可以看到 所有左值大于2和右值小于11的節(jié)點(diǎn) 都是"fruit" 2-11 的子孫節(jié)點(diǎn)