php:树形结构的算法 3

落辰姑娘_7569

落辰姑娘_7569

2016-06-21

1189人浏览

原创

html5酷炫线条背景动画特效
html5酷炫线条背景动画特效

5种酷炫的网格线条动画特效。使用three.meshline库创建的动画WebGL线。设置动画并构建这些线条创建自己的动画效果集合文字,形成一个酷炫的线条背景动画特效。

下载

    那么对于这样的结构我们该如何增加,更新和删除一个节点呢? 增加一个节点一般有两种方法:
  
  保留原有的name 和parent结构,用老方法向数据中添加数据,每增加一条数据以后使用rebuild_tree函数对整个结构重新进行一次编号。
  效率更高的办法是改变所有位于新节点右侧的数值。举例来说:我们想增加一种新的水果"strawberry"(草莓)它将成为"red"节点的最后一个子节点。首先我们需要为它腾出一些空间。"red"的右值应当从6改成8,"yellow 7-10 "的左右值则应当改成 9-12。 依次类推我们可以得知,如果要给新的值腾出空间需要给所有左右值大于5的节点 (5 是"red"最后一个子节点的右值) 加上2。 所以我们这样进行数据库操作:
  
  update tree set rgt=rgt+2 where rgt>5;
  update tree set lft=lft+2 where lft>5;
  这样就为新插入的值腾出了空间,现在可以在腾出的空间里建立一个新的数据节点了, 它的左右值分别是6和7
  
  insert into tree set lft=6, rgt=7, name='strawberry';
  
  再做一次查询看看吧!怎么样?很快吧。
  好了,现在你可以用两种不同的方法设计你的多级数据库结构了,采用何种方式完全取决于你个人的判断,但是对于层次多数量大的结构我更喜欢第二种方法。如果查询量较小但是需要频繁添加和更新的数据,则第一种方法更为简便。
  
  另外,如果数据库支持的话 你还可以将 rebuild_tree() 和 腾出空间的操作写成数据库端的触发器函数, 在插入和更新的时候自动执行, 这样可以得到更好的运行效率, 而且你添加新节点的sql语句会变得更加简单。
  类递归法
  posted by 访客 on 2004, may 31 - 9:18am.
  我用类 递归法 写了段程序,跟文章中的递归不完全一样
  正准备移植到 xoops 中:
  http://dev.xoops.org/modules/xfmod/project/?ulink
  
  已经出现内存溢出现象
  不过准备继续采用递归法,只是需要继续改进
  
  希望有机会跟各位讨论cms
  » reply to this comment
  还是两种方法之比较
  posted by 访客 on 2004, march 17 - 8:30pm.
    仔细研究了一下这篇文章,觉得受益非浅,但后来又想了想,觉得有一下问题(为了好记忆,毗邻目录模式我称为递归的方法,预排序遍历树算法我称为预排序树的方法):
  
  1、两种方法比较大的区别是递归是在查询的时候要用到堆栈进行递归,预排序树则是在更新节点时要进行半数(指所插入节点的后半部分)节点的更新。虽然您也说了,如果节点多了,更新又频繁,预排序树效率会降低,采用递归会好些,而如果节点层次较多的话,首先递归会导致堆栈溢出,再者递归本身效率就不高,加上每一层递归都要操作数据库,总体效果也不会理想。我目前的做法是一次性把数据全取出来,然后对数组进行递归操作,会好一些;再进一步改进的话,可以为每行记录增加一个root根节点(目前是只记录相邻的父节点),这样在查找分支树时效率就会比较高了,更新树的时候也是十分便捷的,应该是一种比较好的方式。
  
  2、改进递归的方式,文章中在计算预排序树节点的左右值的时候其实也用到了一种遍历方式,通过数组替代堆栈,手工实现压栈和弹出;这种方法如果引用到递归算法中,在进行递归的时候也用数组替代堆栈的话,也可以提高递归的效率的。
  
  3、并发,如果考虑到并发的情况,尤其是更新树的时候,预排序树大面积更新节点信息的方法需要额外注意采用加锁和事务的机制保证数据一致性。
  
  4、多根节点或者多父节点的情况,在这种情况下,显然就不是一个标准的二叉树或者多叉树了,预排序树算法需要进行比较大的改进才能适应,而递归的方法则应用自如,所以在这种情况下,递归的适应性较强。这是当然的了,因为递归的方法就是链表的一种形式,树、图都可以用链表来表达,当然适应力强了。
  
  5、直观,如果不用程序操作,直接观察数据库中存储的数据的话,显然递归方式下存储的数据比较直观,而预排序树的数据很难直接阅读(针对层次关系来说),这在数据交换中是不是会有影响呢?
  
    总体来说,我个人比较喜欢用递归的方法,但一直担心递归对效率的影响,所幸还没有接触过规模较大的分类层次,递归用数组替代堆栈会是一种比较好的改进方法。而预排序树不失为一种解决简单树的高效方法,用习惯了,也应该是非常出色的,尤其是它从叶子节点到根节点的反向查找非常方便。
  
  fwolf
  www.fwolf.com
  » reply to this comment
  非常高兴看到你的回复
  posted by shuke on 2004, march 18 - 5:47am.
  非常高兴你这么认真的读完这篇文章。这篇文章其实是原来发表在sitepoint.com上的,我把它翻译了一下,希望给希望初学入门的朋友介绍一些方法,抛砖引玉。你的方法也很好,有机会我会试一下的。(如果你有兴趣的话,何不就上面的例子把你的方法和具体实现的代码也写成教程发出来吧,这样大家就用更加实际的例子来模仿了)如果你对数据库中保存多级结构有兴趣研究的话,这里还有两个连接也很不错可以作为参考:
  介绍了常见的4中方法
  一次查询,数组排序的脚本我想你的脚本肯定比这个强。
  另外我看到你也用drupal,它还有一个高级功能叫分布式用户验证系统,只要在任何一个drupal的站点注册以后就可以登录访问其它的drupal站点了。挺有意思的。
  祝好!
  » reply to this comment
  用循环来建树已经实现了
  posted by 访客 on 2004, march 25 - 10:10pm.
  你上次提供的资料我已经都看过了,不过老实说,第一篇文章里没有太多新东西,或许是我没看太明白吧,第二个居然是php3写的,程序结构没有细看,用到太多的函数交叉。
  正好我在一个系统中用户角色要用到分级,按照数组的思路就把遍历写了下来,没有时间整理,先放到这里你看看吧,数据库用的是adodb,程序是直接从系统中摘出来的,希望能够描述得清楚,主要是利用了php强大的数组操作,用循环来进行递归。注释里是一种相近的方法,只是处理结果的时机不同而已。



php免费学习视频:立即使用
踏上前端学习之旅,开启通往精通之路!从前端基础到项目实战,循序渐进,一步一个脚印,迈向巅峰!

相关文章

PHP速学教程(入门到精通)
PHP速学教程(入门到精通)

PHP怎么学习?PHP怎么入门?PHP在哪学?PHP怎么学才快?不用担心,这里为大家提供了PHP速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
Go-Zero API开发使用教程
Go-Zero API开发使用教程

本专题聚焦Go-Zero的API开发,拆解.api描述文件的语法结构、路由与分组定义、参数绑定与校验规则,说明统一响应体、JWT鉴权、跨域与接口文档生成的落地方式,并给出网关聚合与接口测试的实践建议。

2026.11.12

140

15

Go-Zero安装与goctl环境配置教程
Go-Zero安装与goctl环境配置教程

本专题围绕Go-Zero的安装与工具链配置展开,讲清Go版本要求、goctl安装方式、代理镜像、protoc依赖与环境变量设置,说明多版本共存、升级回退与CI流水线安装的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.12

100

15

Go-Zero零基础入门教程
Go-Zero零基础入门教程

本专题整理Go-Zero的入门知识,从框架定位、环境准备到跑通第一个API服务,讲清目录分层、配置加载、日志与中间件的基本用法,并对比Gin、Kratos的差异,帮助Go开发者建立整体认知,判断它是否适合当前项目。

2026.11.12

80

15

Postman身份认证怎么配置
Postman身份认证怎么配置

本专题从实际API接口调试场景出发,讲解Postman身份认证的完整配置流程,包括常见认证协议介绍、授权参数设置、访问令牌填写、OAuth 2.0授权及认证失败排查,帮助用户正确完成接口授权与访问验证。

2026.11.06

160

12

Postman请求头Headers怎么设置
Postman请求头Headers怎么设置

围绕Postman HTTP请求头配置展开,讲解Headers选项的具体使用方式,包括Key和Value参数填写、请求头信息添加、常见Header字段设置及请求头修改方法,帮助用户解决接口调试过程中遇到的请求头配置问题。

2026.11.06

140

13

Postman接口请求发送教程
Postman接口请求发送教程

详细介绍Postman接口请求的创建与发送方法,涵盖GET和POST请求、URL配置、请求参数、Headers请求头、Body请求体设置以及响应结果查看,帮助用户掌握Postman接口请求的完整操作流程。

2026.11.06

120

10

DBeaver怎么导入数据
DBeaver怎么导入数据

DBeaver数据导入专题,整理Excel、CSV、SQL、TXT等常见文件的数据导入方法,涵盖目标数据库选择、数据表创建、字段映射、数据类型设置及导入参数配置等操作,帮助用户将本地文件中的数据写入数据库,并了解批量导入、重复数据处理和导入失败等常见问题的解决方法。

2026.11.05

120

12

DBeaver安全防护教程大全
DBeaver安全防护教程大全

DBeaver安全防护专题,围绕数据库连接安全、账号密码保护和访问权限管理展开,整理SSL/TLS加密连接、SSH隧道、数据库凭据保存及证书验证等配置方法,同时介绍敏感信息保护、远程连接风险和高权限账号使用等注意事项,帮助用户提高数据库日常管理的安全性。

2026.11.05

100

12

DBeaver连接创建与配置教程
DBeaver连接创建与配置教程

本专题聚焦DBeaver数据库连接配置与管理,覆盖从新建连接、选择数据库类型到填写连接参数和验证连接的完整流程。针对MySQL、PostgreSQL、SQL Server等常见数据库,整理相应的连接设置方法,并提供驱动缺失、认证失败和连接异常等问题的排查方向。

2026.11.04

120

16

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
燕十八Nginx视频教程
燕十八Nginx视频教程

共23课时 | 6.4万人学习