三、实现 1、毗邻目录模式(adjacency list model) 这种模式我们经常用到，很多的教程和书中也介绍过。我们通过给每个节点增加一个属性 parent 来表示这个节点的父节点从而将整个树状结构通过平面的表描述出来。根据这个原则，例子中的数据可以转化成如下的表： 以下是代码： 复制代码 代码如下: +-----------------------+ | parent | name | +-----------------------+ | | Food | | Food | Fruit | | Fruit | Green | | Green | Pear | | Fruit | Red | | Red | Cherry | | Fruit | Yellow | | Yellow | Banana | | Food | Meat | | Meat | Beef | | Meat | Pork | +-----------------------+
我们看到 Pear 是Green的一个子节点，Green是Fruit的一个子节点。而根节点'Food'没有父节点。 为了简单地描述这个问题，这个例子中只用了name来表示一个记录。 在实际的数据库中，你需要用数字的id来标示每个节点，数据库的表结构大概应该像这样：id, parent_id, name, descrīption。 有了这样的表我们就可以通过数据库保存整个多级树状结构了。 显示多级树，如果我们需要显示这样的一个多级结构需要一个递归函数。 以下是代码： 复制代码 代码如下: ?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）使用这个函数就可以打印出整个多级树结构，由于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",以下是代码： 复制代码 代码如下: ?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; } ?
如果对"Cherry"使用这个函数：print_r(get_path('Cherry'))，就会得到这样的一个数组了： 复制代码 代码如下: Array ( [0] = Food [1] = Fruit [2] = Red )
看到了吧，只要一个查询就可以得到所有这些节点。为了能够像上面的递归函数那样显示整个树状结构，我们还需要对这样的查询进行排序。用节点的左值进行排序： 复制代码 代码如下: 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 | +------------+
不相信？自己算一算啦。 用这个简单的公式，我们可以很快的算出"Fruit 2-11"节点有4个子孙节点，而"Banana 8-9"节点没有子孙节点，也就是说它不是一个父节点了。 很神奇吧？虽然我已经多次用过这个方法，但是每次这样做的时候还是感到很神奇。 这的确是个很好的办法，但是有什么办法能够帮我们建立这样有左右值的数据表呢？这里再介绍一个函数给大家，这个函数可以将name和parent结构的表自动转换成带有左右值的数据表。 以下是代码： 复制代码 代码如下: ?php function rebuild_tree($parent, $left) { // the right html' target='_blank'>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; } ?
