标签存档: 树算法

[转]树形结构算法—预排序遍历树算法

预排序遍历树算法(modified preorder tree traversal algorithm),比递归查询更效率。

树结构:
Food
|
|—Fruit
| |
| |—Red
| | |
| | |–Cherry
| |
| |—Yellow
| |
| |–Banana
|
|—Meat
| |
| |–Beef
| |
| |–Pork

预排序遍历树算法:
1 Food 18
|
+—————————————+
| |
2 Fruit 11 12 Meat 17
| |
+————————+ +———————+
| | | |
3 Red 6 7 Yellow 10 13 Beef 14 15 Pork 16
| |
4 Cherry 5 8 Banana 9

表结构:
+————+—–+—–+
| name | lft | rgt |
+————+—–+—–+
| Food | 1 | 18 |
| Fruit | 2 | 11 |
| Red | 3 | 6 |
| Cherry | 4 | 5 |
| Yellow | 7 | 10 |
| Banana | 8 | 9 |
| Meat | 12 | 17 |
| Beef | 13 | 14 |
| Pork | 15 | 16 |
+————+—–+—–+
例如:我们需要得到”Fruit”项下的所有所有节点就可以这样写查询语句: SELECT * FROM tree WHERE lft BETWEEN 2 AND 11; 这个查询得到了以下的结果。
+————+—–+—–+
| 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;
剩下的问题如何显示层级的缩进了。

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'];
}
}

将name和parent结构的表自动转换成带有左右值的数据表的函数:

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;
}

当然这个函数是一个递归函数,我们需要从根节点开始运行这个函数来重建一个带有左右值的树

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';
第 1 页,共 1 页1