字体:  

树操作算法,非递归方法

sentrychen 发表于: 2008-10-01 12:24 来源: PHPChina 开源社区门户

前些日子和一些朋友讨论关于无限分类的算法问题,其中提到了利用PHP数组进行操作的想法。其实无限分类算法就是树的算法。
利用数据库存储数据加递归搜索似乎是目前很流行的一种方法,但这种方法的效率低下,并增加了不少数据库的负担。
我这个算法采用文本方式存储数据,效率应该还可以。由于时间关系,算法是匆匆完成没有经过严格测试就放上来了,大家有兴趣的话就测试一下,找找其中的bug,或改善一下算法的性能。
提醒一点,如果你的PHP可利用的内存不到1G,请不要尝试去创建一个具有100万个节点的树。。。
树的操作算法是各种高级数据结构算法的基础,估计不少同学在大学的时候都学烂了,所以我就不必细讲了。现在要讨论的是如何在PHP这个编程环境里面如果实现该算法最大的性能。
好吧,我来抛砖引玉。
因时间关系没有写注释,看不懂的同学可以提问。


[ 本帖最后由 sentrychen 于 2008-10-3 11:08 编辑 ]

Tree.rar
(2008-10-03 11:08:41, Size: 2.9 KB, Downloads: 77)

最新回复

sentrychen at 2008-10-01 14:43:57
功能测试
sentrychen at 2008-10-01 17:45:29
删除子数和插入子树操作。


[ 本帖最后由 sentrychen 于 2008-10-1 17:47 编辑 ]
sentrychen at 2008-10-01 18:14:10
//性能测试,感觉还不是很满意。构造一棵10万个结点的树,然后遍历,保存
sentrychen at 2008-10-03 10:25:17
呵呵,没人感兴趣,也许是太基础了或者我写得太烂
把牛人问倒 at 2008-10-03 10:28:20
LZ高手  能打包成附件下载吗
naodai at 2008-10-05 00:52:40
先站位,慢慢研究!!
lxylxy888666 at 2008-10-05 01:26:21
值得好好看看,
但实际运用,
犹豫了,
怕怕
sentrychen at 2008-10-05 08:45:56

QUOTE:

原帖由 lxylxy888666 于 2008-10-5 01:26 发表
值得好好看看,
但实际运用,
犹豫了,
怕怕
呵呵,怕啥呢?
lxylxy888666 at 2008-10-05 10:07:58
不知道你花了多少时间,,,
如果用数据库,我只要一两个小时,
而这样写。我一两天就写不出来。。
sentrychen at 2008-10-05 10:20:43

QUOTE:

原帖由 lxylxy888666 于 2008-10-5 10:07 发表
不知道你花了多少时间,,,
如果用数据库,我只要一两个小时,
而这样写。我一两天就写不出来。。
花了一个上午的时间写,再花一个下午的时间调试。
lxylxy888666 at 2008-10-05 10:40:12
我的哥啊,强啊
七月十五 at 2008-10-05 15:28:44
算法精妙,可以应用在很多实际场合,受益良多。
非常感谢楼主分享。
建议加精,以资鼓励。
shanji at 2008-10-05 15:38:44
五五说好,就是好!
sentrychen at 2008-10-05 17:51:01

QUOTE:

原帖由 七月十五 于 2008-10-5 15:28 发表
算法精妙,可以应用在很多实际场合,受益良多。
非常感谢楼主分享。
建议加精,以资鼓励。
呵呵,谢谢加精,这个算法我也没有在实际场合应用过,可能还有很多地方会有bug。
有空我再写一个二叉树的算法,二叉树有4种遍历方式,估计也有很多地方需要用到的。
lsnow at 2008-10-06 15:16:15
这么长,哪看得懂啊。

把你的思路写出来就可以了。
ajaxer at 2008-10-06 16:09:46
学习,mark
liyong98847 at 2008-10-15 12:15:22
我狂顶!!!!!
ws00377531 at 2008-10-22 09:19:24
老话题 到底是把逻辑操作交给数据库 还是交给自己的代码!
pylong at 2008-10-22 10:02:25
具体问题具体分析
如果是数据库负荷大的系统,尽量减轻数据库负担,减少数据库中的运算
naodai at 2008-10-22 10:26:23
恩,同意楼上的!
看过phper上的一个文章为啥php是草根,
觉得我们应该解放数据库,
提高自己了!