php:树形结构的算法

+------------+-----+-----+
| name | lft | rgt |
+------------+-----+-----+
| Fruit | 2 | 11 |
| Red | 3 | 6 |
| Cherry | 4 | 5 |
| Yellow | 7 | 10 |
| Banana | 8 | 9 |
+------------+-----+-----+
看到了吧，只要一个查询就可以得到所有这些节点。为了能够像上面的递归函数那样显示整个树状结构，我们还需要对这样的查询进行排序。用节点的左值进行排序：

SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;
剩下的问题如何显示层级的缩进了。

<?php
function display_tree($root)
{
// 得到根节点的左右值
$result = mysql_query(''SELECT lft, rgt FROM tree ''.''WHERE name="''.$root.''";'');
$row = mysql_fetch_array($result);

// 准备一个空的右值堆栈
$right = array();

// 获得根基点的所有子孙节点
$result = mysql_query(''SELECT name, lft, rgt FROM tree ''.
''WHERE lft BETWEEN ''.$row[''lft''].'' AND ''.
$row[''rgt''].'' ORDER BY lft ASC;'');

// 显示每一行
while ($row = mysql_fetch_array($result))
{
// only check stack if there is one
if (count($right)>0)
{
// 检查我们是否应该将节点移出堆栈
while ($right[count($right)-1]<$row[''rgt''])
{
array_pop($right);
}
}

// 缩进显示节点的名称
echo str_repeat('' '',count($right)).$row[''name'']."n";

// 将这个节点加入到堆栈中
$right[] = $row[''rgt''];
}
}
?>
如果你运行一下以上的函数就会得到和递归函数一样的结果。只是我们的这个新的函数可能会更快一些，因为只有2次数据库查询。 要获知一个节点的路径就更简单了，如果我们想知道Cherry 的路径就利用它的左右值4和5来做一个查询。

SELECT name FROM tree WHERE lft < 4 AND rgt > 5 ORDER BY lft ASC;
这样就会得到以下的结果：

+------------+
| name |
+------------+
| Food |
| Fruit |
| Red |
+------------+
那么某个节点到底有多少子孙节点呢？很简单，子孙总数=(右值-左值-1)/2 descendants = (right – left - 1) / 2 不相信？自己算一算啦。用这个简单的公式，我们可以很快的算出"Fruit 2-11"节点有4个子孙节点，而"Banana 8-9"节点没有子孙节点，也就是说它不是一个父节点了。
很神奇吧？虽然我已经多次用过这个方法，但是每次这样做的时候还是感到很神奇。

这的确是个很好的办法，但是有什么办法能够帮我们建立这样有左右值的数据表呢？这里再介绍一个函数给大家，这个函数可以将name和parent结构的表自动转换成带有左右值的数据表。

<?php
function rebuild_tree($parent, $left) {
// the right value of this node is the left value + 1
$right = $left+1;

// get all children of this node
$result = mysql_query(''SELECT name FROM tree ''.
''WHERE parent="''.$parent.''";'');
while ($row = mysql_fetch_array($result)) {
// recursive execution of this function for each
// child of this node
// $right is the current right value, which is
// incremented by the rebuild_tree function
$right = rebuild_tree($row[''name''], $right);
}

// we''ve got the left value, and now that we''ve processed
// the children of this node we also know the right value
mysql_query(''UPDATE tree SET lft=''.$left.'', rgt=''.
$right.'' WHERE name="''.$parent.''";'');

// return the right value of this node + 1
return $right+1

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