SQL 语句是简单了，但我们所希望的缩进显示却是个问题。什么时候应该显示缩进？缩进多少单位？解决这个问题，需要使用堆栈，即后进先出（LIFO），每到一个节点，将其右边的数字压入堆栈中。我们知道，所有节点右边的值都比其父节点右边的值小，那么将当前节点右边的值和堆栈最上边的右边值进行比较，如果当前节点比堆栈最上边的值小，表示当前堆栈里边剩下的都是父节点了，这时可以显示缩进，堆栈的元素数量即是缩进深度。PHP 代码实现如下：
复制代码 代码如下:
<?php
/**
* @param $root_id 需要显示的树/子树根节点 id。
*/
function show_tree($root_id = 1)
{
// 获取当前根节点的左右数值
$result = mysql_query('SELECT lft, rgt FROM tree WHERESELECT name, lft, rgt FROM tree WHERE lft BETWEEN '.$row['lft'].' AND '.$row['rgt'].' ORDER BY lft ASC');
// 显示树的每个节点
while ($row = mysql_fetch_array($result)) {
if (count($stack)>0) { //仅当堆栈非空的时候检测
// 如果当前节点右边的值比堆栈最上边的值大，则移除堆栈最上边的值，因为这个值对应的节点不是当前节点的父节点
while ($row['rgt'] > $stack[count($stack)-1]) {
array_pop($stack);
} //while 循环结束之后，堆栈里边只剩下当前节点的父节点了
}
// 现在可以显示缩进了
echo '<div>'.$row['name'].'</div>';
// 将当前的节点压入堆栈里边，为循环后边的节点缩进显示做好准备
array_push($stack, $row['rgt']);
}
}
?>
获取整个树调用 show_tree()，获取“Database”子树调用show_tree(2)。在这个函数中，我们总算不需要用到递归了，呵呵。
接下来是显示从根节点到某节点的路径，这比起领接表方式来说也简单了很多，只需要一句 SQL 就行，不用递归 比如获取“ORACLE”这个节点的路径，其左右值分别是 7 和 10，则 SQL 语句为：
复制代码 代码如下:
SELECT name FROM tree WHERE lft <= 7 AND rgt >= 10 ORDER BY lft ASC;
PHP 函数实现如下：
复制代码 代码如下:
<?php
/**
* @param $node_id 需要获取路径的节点 id
*/
function get_path2($node_id) {
// 获取当前节点的左右值
$result = mysql_query('SELECT lft, rgt FROM tree WHERESELECT name FROM tree WHERE lft <= '.$row['lft'].' AND rgt >= '.$row['rgt'].' ORDER BY lft ASC');
$path = array();
while ($row = mysql_fetch_array($result)) {
$path[] = $row['name'];
}
return $path;
}
?>
显示树和路径都没问题了，现在需要了解一下如何插入一个节点。插入新节点之前，首先要给这个节点腾出空位来，假设我们现在要在“ORACLE 9i”这个节点右边增加一个“ORACLE 10”，则腾位的 SQL 语句如下（“ORACLE 9i”的右边值为 9）：
复制代码 代码如下:
UPDATE tree SET rgt=rgt+2 WHERE rgt>9;
UPDATE tree SET lft=lft+2 WHERE lft>9;
位置空出来了，开始插入新节点吧：
复制代码 代码如下:
INSERT INTO tree SET lft=10, rgt=11,;
调用 show_tree() 看看结果对不对 具体的 PHP 实现代码这里就不写了。
现在总结一下预排序遍历树方式的优缺点。缺点是算法比较抽象，不容易理解，增加节点的时候虽然只用了几条 SQL 语句，但可能会需要更新很多记录，从而造成阻塞。优点是树的构造，路径获取方面性能都比领接表方式好很多。也就是说，这个算法牺牲了一些写的性能来换取读的性能，在 WEB 应用中，读数据库的比例远大于写数据库的比例，所以预排序遍历树方式比领接表方式更加受欢迎，更加实用，很多应用中都能看到 MPTT 的影子，通常所用的表里都有字段 lft 和 rgt。
您可能感兴趣的文章: