php:树形结构的算法1

       从喜悦村上转载，以前也读过此文，讲述得还是比较清楚的。

  产品分类，多级的树状结构的论坛，邮件列表等许多地方我们都会遇到这样的问题：如何存储多级结构的数据？
  
  在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 的子孙节点