多数大学生出来选择的工作和专业无关
首页 > 专业知识

PHP技巧实例树形结构的算法

时间:2017-07-21 18:02:28 [来源]:郑州PHP培训学校

   PHP技巧实例树形结构的算法

  产品分类,多级的树状结构的论坛,邮件列表等很多处所我们都会碰到这样的标题:如何存储多级结构的数据?
  在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。有了这样的表我们就可以通过数据库保留全部多级树状结构了。
  显示多级树
  假如我们需要显示这样的一个多级结构需要一个递回函数。
  // $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'
  // $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) 这种方法大家可能接触的比拟少,初次应用也不像上面的方法轻易懂得,但是由于这种方法不应用递回查询算法,有更高的查询效率。

上一篇:PHP代码重用和文件引用

下一篇:PHP快速的MySQL本地和远程密码破解