修改先序树遍历的路径

Question

我已经实现了修改先序树遍历as explained here。我的树是这样的：

+-------+-----------+-----+-----+ 
| ref | name  | lft | rgt | 
+-------+-----------+-----+-----+ 
| NULL | base  | 1 | 8 | 
|  2 | basic  | 2 | 3 | 
| NULL | listener | 4 | 7 | 
|  1 | test  | 5 | 6 | 
+-------+-----------+-----+-----+ 

一切都OK了，但现在我试图执行基于路径上的PHP搜索功能，它是这样的：

$result = searchTree('base.listener.test'); 
// Now $result is an array with node {1, test} 

这意味着， searchTree根据给定的路径返回一个子树。如果路径不存在，它将返回一个空数组。

我目前的实现是加载树成PHP数组，然后将其拆分路径，并通过阵列走一个循环的功能。它似乎是一个不可扩展的实现......任何更好的实现（可能使用mySQL查询？）。

我目前的实现是这样的。首先，我得到整个树（SELECT * FROM树），然后我执行此功能以使从这个数据的多维数组：

function create_tree($results) { 
    $return = $results[0]; 
    array_shift($results); 

    if ($return['lft'] + 1 == $return['rgt']) 
     $return['leaf'] = true; 
    else { 
     foreach ($results as $key => $result) { 
      if ($result['lft'] > $return['rgt']) 
       break; 
      if ($rgt > $result['lft']) 
       continue; 
      $return['children'][] = create_tree(array_values($results)); 
      foreach ($results as $child_key => $child) { 
       if ($child['rgt'] < $result['rgt']) 
        unset($results[$child_key]); 
      } 
      $rgt = $result['rgt']; 
      unset($results[$key]); 
     } 
    } 

    unset($return['lft'],$return['rgt']); 
    return $return; 
} 

然后我在$树数组变量和执行这一块代码：

$t3 = $tree; 
$parts = explode('.', $path); 
while (isset($parts[0]) && count($parts) > 1 && isset($t3['children']) && $parts[0] == $t3['name']) { 
    array_shift($parts); 
    for ($i = 0; $i < count($tree['children']) && $tree['children'][$i]['name'] != $parts[0]; $i++); 
    $t3 = $tree['children'][$i]; 
} 

return isset($t3) && count($parts) == 1 && $parts[0] == $t3['name']? $t3['children'] : array(); 

如果此路径不存在最后一行返回由$路径指向的节点（即“base.listener.test”）或空数组。

Answer 1

如果我明白你在找什么，你要拨打：

$result = searchTree('test'); 

，并得到搜索数据库为父母？

SELECT p.name 
    FROM tree c 
    INNER JOIN tree p ON p.lft < c.lft AND p.rgt > c.rgt 
    WHERE c.name = 'test' 
    ORDER BY p.lft;