修改先序樹遍歷的路徑

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;