php:树形结构的算法

时间:2010-01-20 08:24:33  来源:第二电脑网  作者:第二电脑网

  第二电脑网导读:后台数据存储的通常是关系型数据库,它能够保存大量的数据,提供高效的数据检索和更新服务。然而关系型数据的基础形式是纵横交错的表,是一个平面的结构,如果要将多级树状结构存储在关系型数据库里就需要进行合理的翻译工作。接下来我会将自己的所见所闻和一些实用的经验和大家探讨一下。      层级结构的数据保存在平面的数据库中基础上有两种常用设计...
  正文:

 从喜悦村上转载,以前也读过此文,讲述得还是比较清楚的。
  产品分类,多级的树状结构的论坛,邮件列表等许多地方我们都会遇到这样的问题:如何存储多级结构的数据?
  
  在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";
  
  //再次调用这个函数显示子节点的子节点 "php:树形结构的算法"由第二电脑网原创提供,转载请注明:http://www.002pc.com/master/College/Programming/PHP/12067.html

 1/4    1 2 3 4 下一页 尾页


关键字:

关于《php:树形结构的算法》文章的评论

站内搜索: 高级搜索

热门搜索: Windows style 系统 tr IP QQ CPU 安装 function 注册 if td