php:樹形結構的算法 2 - php語言 -

php:樹形結構的算法 2

時間:2013-05-29 13:47:30   來源:   評論:加載中...   點擊:加載中...
1 Food 18 | +---------------------------------------+ | |...
  1 Food 18
  |
  +---------------------------------------+
  | |
  2 Fruit 11 12 Meat 17
  | |
  +------------------------+ +---------------------+
  | | | |
  3 Red 6 7 Yellow 10 13 Beef 14 15 Pork 16
  | |
  4 Cherry 5 8 Banana 9
  
  這樣整個樹狀結構可以通過左右值來存儲到數據庫中。繼續之前,我們看一看下面整理過的數據表。
  
  
  +-----------------------+-----+-----+
  | 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"來表示左右字段。 另外這種結構中不再需要"parent"字段來表示樹狀結構。也就是 說下面這樣的表結構就足夠了。
  
  +------------+-----+-----+
  | 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 |
  +------------+-----+-----+
  好了我們現在可以從數據庫中獲取數據了,例如我們需要得到"Fruit"項下的所有所有節點就可以這樣寫查詢語句: SELECT * FROM tree WHERE lft BETWEEN 2 AND 11; 這個查詢得到了以下的結果。
  
  
  +------------+-----+-----+
  | name | lft | rgt |
  +------------+-----+-----+
  | Fruit | 2 | 11 |
  | Red | 3 | 6 |
  | Cherry | 4 | 5 |
  | Yellow | 7 | 10 |
  | Banana | 8 | 9 |
  +------------+-----+-----+
  看到了吧,只要一個查詢就可以得到所有這些節點。為了能夠像上面的遞歸函數那樣顯示整個樹狀結構,我們還需要對這樣的查詢進行排序。用節點的左值進行排序:
  
  SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;
  剩下的問題如何顯示層級的縮進了。
  
  <?php
  function display_tree($root)
  {
  // 得到根節點的左右值
  $result = mysql_query('SELECT lft, rgt FROM tree '.'WHERE name="'.$root.'";');
  $row = mysql_fetch_array($result);
  
  // 準備一個空的右值堆棧
  $right = array();
  
  // 獲得根基點的所有子孫節點
  $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)
  {
  // 檢查我們是否應該將節點移出堆棧
  while ($right[count($right)-1]<$row['rgt'])
  {
  array_pop($right);
  }
  }
  
  // 縮進顯示節點的名稱
  echo str_repeat(' ',count($right)).$row['name']."n";
  
  // 將這個節點加入到堆棧中
  $right[] = $row['rgt'];
  }
  }
  ?>
  如果你運行一下以上的函數就會得到和遞歸函數一樣的結果。只是我們的這個新的函數可能會更快一些,因為只有2次數據庫查詢。 要獲知一個節點的路徑就更簡單了,如果我們想知道Cherry 的路徑就利用它的左右值4和5來做一個查詢。
  
  SELECT name FROM tree WHERE lft < 4 AND rgt > 5 ORDER BY lft ASC;
  這樣就會得到以下的結果:
  
  +------------+
  | name |
  +------------+
  | Food |
  | Fruit |
  | Red |
  +------------+
  那么某個節點到底有多少子孫節點呢?很簡單,子孫總數=(右值-左值-1)/2 descendants = (right – left - 1) / 2 不相信?自己算一算啦。用這個簡單的公式,我們可以很快的算出"Fruit 2-11"節點有4個子孫節點,而"Banana 8-9"節點沒有子孫節點,也就是說它不是一個父節點了。
  很神奇吧?雖然我已經多次用過這個方法,但是每次這樣做的時候還是感到很神奇。
  
  這的確是個很好的辦法,但是有什么辦法能夠幫我們建立這樣有左右值的數據表呢?這里再介紹一個函數給大家,這個函數可以將name和parent結構的表自動轉換成帶有左右值的數據表。
  
  
  <?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;
  }
  ?>
  當然這個函數是一個遞歸函數,我們需要從根節點開始運行這個函數來重建一個帶有左右值的樹
  
  rebuild_tree('Food',1);
  這個函數看上去有些復雜,但是它的作用和手工對表進行編號一樣,就是將立體多層結構的轉換成一個帶有左右值的數據表。


相關熱詞搜索:

 
上一篇:php:樹形結構的算法1
下一篇:php:樹形結構的算法 3
收藏 將此文推薦給朋友
分享到:
10个数复式三中三多少组公式