php:树形结构的算法

rebuild_tree(''Food'',1);
这个函数看上去有些复杂，但是它的作用和手工对表进行编号一样，就是将立体多层结构的转换成一个带有左右值的数据表。

那么对于这样的结构我们该如何增加，更新和删除一个节点呢？ 增加一个节点一般有两种方法：

保留原有的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、多根节点或者多父节点的情况，在这种情况下，显然就不是一个标准的二叉树或者多叉树了，预排序树算

凌众科技专业提供服务器租用、服务器托管、企业邮局、虚拟主机等服务，公司网站：http://www.lingzhong.cn 为了给广大客户了解更多的技术信息，本技术文章收集来源于网络,凌众科技尊重文章作者的版权，如果有涉及你的版权有必要删除你的文章，请和我们联系。以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息，谢谢!