php:樹形結(jié)構(gòu)的算法 2

2024-09-08 23:18:45

字體：大中小

供稿：網(wǎng)友

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

  這樣整個(gè)樹狀結(jié)構(gòu)可以通過左右值來存儲(chǔ)到數(shù)據(jù)庫中。繼續(xù)之前，我們看一看下面整理過的數(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"來表示左右字段。另外這種結(jié)構(gòu)中不再需要"parent"字段來表示樹狀結(jié)構(gòu)。也就是說下面這樣的表結(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ù)庫中獲取數(shù)據(jù)了，例如我們需要得到"fruit"項(xiàng)下的所有所有節(jié)點(diǎn)就可以這樣寫查詢語句： 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è)樹狀結(jié)構(gòu)，我們還需要對這樣的查詢進(jìn)行排序。用節(jié)點(diǎn)的左值進(jìn)行排序：

  select * from tree where lft between 2 and 11 order by lft asc;
  剩下的問題如何顯示層級(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ù)庫查詢。要獲知一個(gè)節(jié)點(diǎn)的路徑就更簡單了，如果我們想知道cherry 的路徑就利用它的左右值4和5來做一個(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)呢？很簡單，子孫總數(shù)=(右值-左值-1)/2 descendants = (right – left - 1) / 2 不相信？自己算一算啦。用這個(gè)簡單的公式，我們可以很快的算出"fruit 2-11"節(jié)點(diǎn)有4個(gè)子孫節(jié)點(diǎn)，而"banana 8-9"節(jié)點(diǎn)沒有子孫節(jié)點(diǎn)，也就是說它不是一個(gè)父節(jié)點(diǎn)了。
  很神奇吧？雖然我已經(jīng)多次用過這個(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)開始運(yùn)行這個(gè)函數(shù)來重建一個(gè)帶有左右值的樹

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

注冊會(huì)員，創(chuàng)建你的web開發(fā)資料庫，

上一篇：php:樹形結(jié)構(gòu)的算法1

下一篇：php:樹形結(jié)構(gòu)的算法 3