PHP技巧实例：树形结构的算法

16-01-06 来源：[db:作者]

收藏我要投稿

从喜悦村上转载，以前也读过此文，讲述得还是比拟明白的。
产品分类，多级的树状结构的论坛，邮件列表等很多处所我们都会碰到这样的标题：如何存储多级结构的数据？

在PHP的利用中，供给后台数据存储的通常是关系型数据库，它能够保留大批的数据，供给高效的数据检索和更新服务。然而关系型数据的基础情势是纵横交错的表，是一个平面的结构，假如要将多级树状结构存储在关系型数据库里就需要进行公平的翻译工作。接下来我会将自己的所见所闻和一些实用的经验和大家探讨一下。

层级结构的数据保留在平面的数据库中基础上有两种常用设计方法：

毗邻目录模式(adjacency list model)
预排序遍历树算法(modified preorder tree traversal algorithm)
我不是盘算机专业的，也没有学过什么数据结构的东西，所以这两个名字都是我自己按照字面的意思翻的，假如说错了还请多多指教。

这两个东西听着似乎很吓人，实在非常轻易懂得。这里我用一个简略食品目录作为我们的示例数据。我们的数据结构是这样的:

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

毗邻目录模式(adjacency list model)

这种模式我们经常用到，很多的教程和书中也先容过。我们通过给每个节点增加一个属性 parent 来表现这个节点的父节点从而将全部树状结构通过平面的表描写出来。根据这个原则，例子中的数据可以转化成如下的表：

显示多级树
假如我们需要显示这样的一个多级结构需要一个递回函数。

// $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）应用这个函数就可以打印出全部多级树结构，由于Food是根节点它的父节点是空的，所以这样调用: display_children('',0)。将显示全部树的内容：

Food
Fruit
Red
Cherry
Yellow
Banana
Meat
Beef
Pork
假如你只想显示全部结构中的一部分，比如说水果部分，就可以这样调用：

display_children('Fruit',0);

几乎应用同样的方法我们可以知道从根节点到任意节点的路径。比如 Cherry 的路径是　'Food > Fruit > Red'。为了得到这样的一个路径我们需要从最深的一级'Cherry'开端，查询得到它的父节点'Red'把它添加到路径中，然后我们再查询Red的父节点并把它也添加到路径中，以此类推直到最高层的'Food'

// $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;
}
?>
假如对'Cherry'应用这个函数：print_r(get_path('Cherry'))，就会得到这样的一个数组了：

Array
(
[0] => Food
[1] => Fruit
[2] => Red
)
接下来如何把它打印成你盼看的格局，就是你的事情了。
毛病：这种方法很简略，轻易懂得，好上手。但是也有一些毛病。重要是由于运行速度很慢，由于得到每个节点都需要进行数据库查询，数据量大的时候要进行很多查询才干完成一个树。另外由于要进行递回运算，递回的每一级都需要占用一些内存所以在空间利用上效率也比拟低。

现在让我们看一看另外一种不应用递回盘算，更加快速的方法，这就是预排序遍历树算法(modified preorder tree traversal algorithm) 这种方法大家可能接触的比拟少，初次应用也不像上面的方法轻易懂得，但是由于这种方法不应用递回查询算法，有更高的查询效率。

我们首先将多级数据按照下面的方法画在纸上，在根节点Food的左侧写上 1 然后沿着这个树持续向下在 Fruit 的左侧写上 2 然后持续前进，沿着全部树的边缘给每一个节点都标上左侧和右侧的数字。最后一个数字是标在Food 右侧的 18。在下面的这张图中你可以看到全部标好了数字的多级结构。（没有看懂？用你的手指指着数字从1数到18就明白怎么回事了。还不明白，再数一遍，留心要移动你的手指）。

这些数字标明了各个节点之间的关系，'Red'的号是3和6，它是 'Food' 1-18 的子孙节点。同样，我们可以看到所有左值大于2和右值小于11的节点都是'Fruit' 2-11 的子孙节点

这样全部树状结构可以通过左右值来存储到数据库中。持续之前，我们看一看下面收拾过的数据表。

----------------------- ----- -----
| 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 |
----------------------- ----- -----
留心：由于'left'和'right'在 SQL中有特别的意义，所以我们需要用'lft'和'rgt'来表现左右字段。另外这种结构中不再需要'parent'字段来表现树状结构。也就是说下面这样的表结构就足够了。

------------ ----- -----
| 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'];
}
}
?>
假如你运行一下以上的函数就会得到和递回函数一样的成果。只是我们的这个新的函数可能会更快一些，由于只有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结构的表主动转换成带有左右值的数据表。

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

再做一次查询看看吧！怎么样？很快吧。
好了，现在你可以用两种不同的方法设计你的多级数据库结构了，采用何种方法完整取决于你个人的判定，但是对于层次多数目大的结构我更爱好第二种方法。假如查询量较小但是需要频繁添加和更新的数据，则第一种方法更为简便。

另外，假如数据库支撑的话你还可以将 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、多根节点或者多父节点的情况，在这种情况下，显然就不是一个尺度的二叉树或者多叉树了，预排序树算法需要进行比拟大的改良才干适应，而递回的方法则利用自如，所以在这种情况下，递回的适应性较强。这是当然的了，由于递回的方法就是链表的一种情势，树、图都可以用链表来表达，当然适应力强了。

5、直观，假如不用程序把持，直接观察数据库中存储的数据的话，显然递回方法下存储的数据比拟直观，而预排序树的数据很难直接浏览（针对层次关系来说），这在数据交换中是不是会有影响呢？

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

Fwolf
www.fwolf.com
? reply to this comment
非常高兴看到你的回复
Posted by shuke on 2004, March 18 - 5:47am.
非常高兴你这么认真的读完这篇文章。这篇文章实在是本来发表在sitepoint.com上的，我把它翻译了一下，盼看给盼看初学进门的朋友先容一些方法，抛砖引玉。你的方法也很好，有机会我会试一下的。（假如你有爱好的话，何不就上面的例子把你的方法和具体实现的代码也写成教程发出来吧，这样大家就用更加实际的例子来模仿了）假如你对数据库中保留多级结构有爱好研究的话，这里还有两个连接也很不错可以作为参考：
先容了常见的4中方法
一次查询，数组排序的脚本我想你的脚本确定比这个强。
另外我看到你也用drupal，它还有一个高级功效叫散布式用户验证系统，只要在任何一个drupal的站点注册以后就可以登录拜访其它的drupal站点了。挺有意思的。
祝好！
? reply to this comment
用循环来建树已经实现了
Posted by 访客 on 2004, March 25 - 10:10pm.
你上次供给的材料我已经都看过了，不过诚实说，第一篇文章里没有太多新东西，或许是我没看太明白吧，第二个居然是PHP3写的，程序结构没有细看，用到太多的函数交叉。
正好我在一个系统中用户角色要用到分级，按照数组的思路就把遍历写了下来，没有时间收拾，先放到这里你看看吧，数据库用的是ADODB，程序是直接从系统中摘出来的，盼看能够描写得明白，重要是利用了PHP强盛的数组把持，用循环来进行递回。注释里是一种相近的方法，只是处理成果的机会不同而已。

/**
* 显示列表
* @access public
*/
function DispList()
{
//不缩进的显示方法
// $this->mIsDispListIndex = true;

// echo('

//
// $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) . '
' . implode(', ', $stacki) . '
' . implode(', ', $target) . '

');
// }
// debug_array();
// }
// else
// {
// echo('

没有检索到数据');
// }

//另外一种显示方法，用数组作为堆栈，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) . ' $s2 = ' 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) . '
' . implode(', ', $stacki) . '
' . implode(', ', $target) . '

');
}
//输出
echo('

array_unshift($target, array('角色', '把持'));
$this->CheckProperty('mrLt');
$this->mrLt->SetData($target);
$this->mrLt->mListTitle = '用户角色列表';
$this->mrLt->mIsDispIndex = false;
$this->mrLt->Disp();
}
else
{
echo('

没有检索到数据');
}
} // end of function DispList
?>

点击复制链接与好友分享!回本站首页