php:树形结构的算法 2

2024-09-08 23:18:45

字体：大中小

来源：转载

供稿：网友

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);
  这个函数看上去有些复杂，但是它的作用和手工对表进行编号一样，就是将立体多层结构的转换成一个带有左右值的数据表。

注册会员，创建你的web开发资料库，

上一篇：php:树形结构的算法1

下一篇：php:树形结构的算法 3