﻿ php:树形结构的算法-PHP编程_网络编程-脚本宝典

# php:树形结构的算法

## php:树形结构的算法

php:树形结构的算法

Food
|
|---Fruit
| |
| |---Red
| | |
| | |--Cherry
| |
| |---Yellow
| |
| |--Banana
|
|---Meat

|--Beef
|
|--Pork

Food:食物
Fruit:水果
Red:红色
Cherry:樱桃
Yellow:黄色
Banana:香蕉
Meat:肉类
Beef:牛肉
Pork:猪肉

+-----------------------+
| parent | name |
+-----------------------+
| | Food |
| Food | Fruit |
| Fruit | Green |
| Green | Pear |
| Fruit | Red |
| Red | Cherry |
| Fruit | Yellow |
| Yellow | Banana |
| Food | Meat |
| Meat | Beef |
| Meat | Pork |
+-----------------------+

<?php
// \$parent is the parent of the children we want to see
// \$level is increased when we go deeper into the tree,
// used to display a nice indented tree

function display_children(\$parent, \$level)

// 获得一个 父节点 \$parent 的所有子节点
\$result = mysql_query('SELECT name FROM tree '.
'WHERE parent="'.\$parent.'";');

// 显示每个子节点
while (\$row = mysql_fetch_array(\$result))

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

//再次调用这个函数显示子节点的子节点

display_children(\$row['name'], \$level+1);

}
?>

Food
Fruit
Red
Cherry
Yellow
Banana
Meat
Beef
Pork

display_children('Fruit',0);

<?php
// \$node 是那个最深的节点
function get_path(\$node)

// 查询这个节点的父节点
\$result = mysql_query('SELECT parent FROM tree '.
'WHERE name="'.\$node.'";');
\$row = mysql_fetch_array(\$result);

// 用一个数组保存路径
\$path = array();

// 如果不是根节点则继续向上查询
// (根节点没有父节点)
if (\$row['parent']!='')

// the last part of the path to \$node, is the name
// of the parent of \$node
\$path[] = \$row['parent'];

// we should add the path to the parent of this node
// to the path
\$path = array_merge(get_path(\$row['parent']), \$path);
}

// return the path
return \$path;
}
?>

Array
(
[0] => Food
[1] => Fruit
[2] => Red
)

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

+-----------------------+-----+-----+
| parent | name | lft | rgt |
+-----------------------+-----+-----+
| | Food | 1 | 18 |
| Food | Fruit | 2 | 11 |
| Fruit | Red | 3 | 6 |
| Red | Cherry | 4 | 5 |
| Fruit | Yellow | 7 | 10 |
| Yellow | Banana | 8 | 9 |
| Food | Meat | 12 | 17 |
| Meat | Beef | 13 | 14 |
| Meat | Pork | 15 | 16 |
+-----------------------+-----+-----+

+------------+-----+-----+
| 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 |
+------------+-----+-----+

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

}
?>

SELECT name FROM tree WHERE lft < 4 AND rgt > 5 ORDER BY lft ASC;

+------------+
| name |
+------------+
| Food |
| Fruit |
| Red |
+------------+

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

rebuild_tree('Food',1);

UPDATE tree SET rgt=rgt+2 WHERE rgt>5;
UPDATE tree SET lft=lft+2 WHERE lft>5;

INSERT INTO tree SET lft=6, rgt=7, name='Strawberry';

Posted by 访客 on 2004, May 31 - 9:18am.

Posted by 访客 on 2004, March 17 - 8:30pm.
仔细研究了一下这篇文章，觉得受益非浅，但后来又想了想，觉得有一下问题（为了好记忆，毗邻目录模式我称为递归的方法，预排序遍历树算法我称为预排序树的方法）：

1、两种方法比较大的区别是递归是在查询的时候要用到堆栈进行递归，预排序树则是在更新节点时要进行半数（指所插入节点的后半部分）节点的更新。虽然您也说了，如果节点多了，更新又频繁，预排序树效率会降低，采用递归会好些，而如果节点层次较多的话，首先递归会导致堆栈溢出，再者递归本身效率就不高，加上每一层递归都要操作数据库，总体效果也不会理想。我目前的做法是一次性把数据全取出来，然后对数组进行递归操作，会好一些；再进一步改进的话，可以为每行记录增加一个ROOT根节点（目前是只记录相邻的父节点），这样在查找分支树时效率就会比较高了，更新树的时候也是十分便捷的，应该是一种比较好的方式。

2、改进递归的方式，文章中在计算预排序树节点的左右值的时候其实也用到了一种遍历方式，通过数组替代堆栈，手工实现压栈和弹出；这种方法如果引用到递归算法中，在进行递归的时候也用数组替代堆栈的话，也可以提高递归的效率的。

3、并发，如果考虑到并发的情况，尤其是更新树的时候，预排序树大面积更新节点信息的方法需要额外注意采用加锁和事务的机制保证数据一致性。

4、多根节点或者多父节点的情况，在这种情况下，显然就不是一个标准的二叉树或者多叉树了，预排序树算法需要进行比较大的改进才能适应，而递归的方法则应用自如，所以在这种情况下，递归的适应性较强。这是当然的了，因为递归的方法就是链表的一种形式，树、图都可以用链表来表达，当然适应力强了。

5、直观，如果不用程序操作，直接观察数据库中存储的数据的话，显然递归方式下存储的数据比较直观，而预排序树的数据很难直接阅读（针对层次关系来说），这在数据交换中是不是会有影响呢？

总体来说，我个人比较喜欢用递归的方法，但一直担心递归对效率的影响，所幸还没有接触过规模较大的分类层次，递归用数组替代堆栈会是一种比较好的改进方法。而预排序树不失为一种解决简单树的高效方法，用习惯了，也应该是非常出色的，尤其是它从叶子节点到根节点的反向查找非常方便。

Fwolf

Posted by shuke on 2004, March 18 - 5:47am.

Posted by 访客 on 2004, March 25 - 10:10pm.

<?php
/**
* 显示列表
* @access public
*/
function DispList()

//不缩进的显示方式
// \$this->mIsDispListIndex = true;
// echo('<p align="right"><a href="http://www.php1.cn/">//
// \$this->mListTitle = "用户角色列表";
// \$this->SetDataOption('list');
//
// \$this->SetQueryTable( array(\$this->mTableUserRole) );
//
// //查询顺序
// \$this->SetQueryOrder( 'asc', \$this->mTableUserRole, 'sequence' );
//
// \$this->Query('list');
// parent::DispList();

// //另外一种显示方式，用数组作为堆栈，A: 压栈时存role，压完就删除source
// \$this->CheckProperty('mrDb');
// \$this->CheckProperty('mrSql');
// \$this->mrSql->Select('role, title, parent');
// \$this->mrSql->From(\$this->mTableUserRole);
// \$this->mrSql->Orderby('parent, sequence');
// \$this->mRs = \$this->mrDb->Execute(\$this->mrSql->Sql());
// if (0 < count(\$this->mRs))
// {
// \$source = & \$this->mRs->GetArray(); //数字索引
// \$stack = array(''); //堆栈
// \$stacki = array(-1); //和堆栈对应，记录堆栈中数据在树中的层次
// \$target = array();
// while (0 < count(\$stack))
// {
// \$item = array_shift(\$stack);
// \$lev = array_shift(\$stacki);
// if (!empty(\$item))
// {
// //在这里把加工过的数据放到target数组
// array_push(\$target, str_repeat(' ', \$lev) . \$item);
// //\$s1 = str_repeat(' ', \$lev) . \$item;
// }
// \$del = array(); //要从\$source中删除的节点
// \$ar = array(); //需要添加到堆栈中的节点
// foreach (\$source as \$key=>\$val)
// {
// //寻找匹配的子节点
// if (empty(\$item))
// {
// \$find = empty(\$source[\$key]['parent']);
// }
// else
// {
// \$find = (\$item == \$source[\$key]['parent']);
// }
// if (\$find)
// {
// array_unshift(\$ar, \$source[\$key]['role']);
// \$del[] = \$key;
// }
// }
// foreach (\$ar as \$val)
// {
// array_unshift(\$stack, \$val);
// array_unshift(\$stacki, \$lev + 1);
// }
// foreach (\$del as \$val)
// {
// unset(\$source[\$val]);
// }
// echo(implode(', ', \$stack) . '<br />' . implode(', ', \$stacki) . '<br />' . implode(', ', \$target) . '<br /><br />');
// }
// debug_array();
// }
// else
// {
// echo('<center>没有检索到数据</center>');
// }

//另外一种显示方式，用数组作为堆栈，B: 压栈时存数组索引，出栈并使用完后再删除source
\$this->CheckProperty('mrDb');
\$this->CheckProperty('mrSql');
\$this->mrSql->Select('role, title, parent');
\$this->mrSql->From(\$this->mTableUserRole);
\$this->mrSql->Orderby('parent, sequence');
\$this->mRs = \$this->mrDb->Execute(\$this->mrSql->Sql());
if (!empty(\$this->mRs) && !\$this->mRs->EOF)

\$source = & \$this->mRs->GetArray(); //数字索引
\$stack = array(-1); //堆栈
\$stacki = array(-1); //和堆栈对应，记录堆栈中数据在树中的层次
\$target = array();
while (0 < count(\$stack))

\$item = array_shift(\$stack);
\$lev = array_shift(\$stacki);
if (-1 != \$item)

//在这里把加工过的数据放到target数组
\$s1 = str_repeat('  ', \$lev) . '<a href="http://www.php1.cn/">\$s2 = '<a href="http://www.php1.cn/">array_push(\$target, array(\$s1, \$s2));

\$del = array(); //要从\$source中删除的节点
\$ar = array(); //需要添加到堆栈中的节点
foreach (\$source as \$key=>\$val)

//寻找匹配的子节点
if (-1 == \$item)

\$find = empty(\$source[\$key]['parent']);

else

\$find = (\$source[\$item]['role'] == \$source[\$key]['parent']);

if (\$find)

array_unshift(\$ar, \$key);

foreach (\$ar as \$val)

array_unshift(\$stack, \$val);
array_unshift(\$stacki, \$lev + 1);

//从source中删除
unset(\$source[\$item]);
//echo(implode(', ', \$stack) . '<br />' . implode(', ', \$stacki) . '<br />' . implode(', ', \$target) . '<br /><br />');

//输出
echo('<p align="right"><a href="http://www.php1.cn/">array_unshift(\$target, array('角色', '操作'));
\$this->CheckProperty('mrLt');
\$this->mrLt->SetData(\$target);
\$this->mrLt->mListTitle = "用户角色列表";
\$this->mrLt->mIsDispIndex = false;
\$this->mrLt->Disp();

else

echo('<center>没有检索到数据</center>');

} // end of function DispList
?>

Tags：

﻿
<