无法在这个位置找到: "head.htm"
新闻资讯
您所在的位置:首页 / 新闻资讯 / 公牛新闻

电脑培训学校新闻

php:树形结构的算法1

时间2018-09-20 15:25  来源:未知  点击数:  作者:admin

     

  产品分类,多级的树状结构的论坛,邮件列表等许多地方我们都会遇到这样的问题:如何存储多级结构的数据?

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

  我不是计算机专业的,也没有学过什么数据结构的东西,所以这两个名字都是我自己按照字面的意思翻的,如果说错了还请多多指教。

  这两个东西听着好像很吓人,其实非常容易理解。这里我用一个简单食品目录作为我们的示例数据。 我们的数据结构是这样的:

  这种模式我们经常用到,很多的教程和书中也介绍过。我们通过给每个节点增加一个属性 parent 来表示这个节点的父节点从而将整个树状结构通过平面的表描述出来。根据这个原则,例子中的数据可以转化成如下的表:

  我们看到 Pear 是Green的一个子节点,Green是Fruit的一个子节点。而根节点Food没有父节点。 为了简单地描述这个问题, 这个例子中只用了name来表示一个记录。 在实际的数据库中,你需要用数字的id来标示每个节点,数据库的表结构大概应该像这样:id, parent_id, name, description。有了这样的表我们就可以通过数据库保存整个多级树状结构了。

  对整个结构的根节点(Food)使用这个函数就可以打印出整个多级树结构,由于Food是根节点它的父节点是空的,所以这样调用: display_children(,0)。将显示整个树的内容:

  几乎使用同样的方法我们可以知道从根节点到任意节点的路径。比如 Cherry 的路径是Food>

  Fruit>

  Red。 为了得到这样的一个路径我们需要从最深的一级Cherry开始, 查询得到它的父节点Red把它添加到路径中, 然后我们再查询Red的父节点并把它也添加到路径中,以此类推直到最高层的Food

  缺点:这种方法很简单,容易理解,好上手。但是也有一些缺点。主要是因为运行速度很慢,由于得到每个节点都需要进行数据库查询,数据量大的时候要进行很多查询才能完成一个树。另外由于要进行递归运算,递归的每一级都需要占用一些内存所以在空间利用上效率也比较低。

  现在让我们看一看另外一种不使用递归计算,更加快速的方法,这就是预排序遍历树算法(modified preorder tree traversal algorithm) 这种方法大家可能接触的比较少,初次使用也不像上面的方法容易理解,但是由于这种方法不使用递归查询算法,有更高的查询效率。

  我们首先将多级数据按照下面的方式画在纸上,在根节点Food的左侧写上 1 然后沿着这个树继续向下 在 Fruit 的左侧写上 2 然后继续前进,沿着整个树的边缘给每一个节点都标上左侧和右侧的数字。最后一个数字是标在Food 右侧的 18。 在下面的这张图中你可以看到整个标好了数字的多级结构。(没有看懂?用你的手指指着数字从1数到18就明白怎么回事了。还不明白,再数一遍,注意要移动你的手指)。

  这些数字标明了各个节点之间的关系,Red的号是3和6,它是 Food 1-18 的子孙节点。 同样,我们可以看到 所有左值大于2和右值小于11的节点 都是Fruit 2-11 的子孙节点

下一篇:下一篇:如何使用PHP开发比特币详解

友情链接:
  • 广州电脑维修
  • 国际学校
  • 梅州淘屋网
  • 硅酸盐防爆泄压板
  • 滨州搜房网
  • 壹诺网站优化
  • 网站地图 ©电脑培训学校,株洲it培训,php工程师