从祖先列表中构建树的最简单方法

Question

在我的心里,我觉得必须有一个超级简单的递归解决方案,但我不能立即理解它.

我有一个存储在SQL中的树作为闭包表.树看起来像:(1(2(3),4)),语言是MySQL的SQL和PHP 5.3.

因此,闭包表是:

+----------+------------+
| ancestor | descendant |
+----------+------------+
|        1 |          1 | 
|        2 |          2 | 
|        3 |          3 | 
|        4 |          4 | 
|        1 |          2 | 
|        1 |          3 | 
|        1 |          4 | 
|        2 |          3 | 
+----------+------------+

我可以很容易地查询祖先:

 SELECT descendant AS id, GROUP_CONCAT(ancestor) as ancestors FROM
 closure GROUP BY (descendant);

 +----+-----------+
 | id | ancestors |
 +----+-----------+
 |  1 | 1         | 
 |  2 | 2,1       | 
 |  3 | 3,1,2     | 
 |  4 | 4,1       | 
 +----+-----------+

如何使用这些数据在PHP中轻松构建树？我可以使用更智能的查询从MySQL中提取更多数据吗？

Answer 1

第一个关键是按祖先的数量对 SQL 结果进行排序。我在 PHP 中这样做是因为我避免了多位数的复杂性。

这提供了一个节点列表，按照可以有效插入的顺序排列。

Array
(
    [1] => Array
        (
            [0] => 1
        )

    [4] => Array
        (
            [0] => 4
            [1] => 1
        )

    [2] => Array
        (
            [0] => 2
            [1] => 1
        )

    [3] => Array
        (
            [0] => 3
            [1] => 1
            [2] => 2
        )

)

此时，我不关心密钥，只关心祖先列表。可以在可用节点和剩余祖先的交集之间找到穿过树的路径。

  function add_node($ancestors, &$tree) {
    if (count($ancestors) == 1) {
      $tree[array_pop($ancestors)] = array();
      return;
    }   
    $next_node = array_intersect($ancestors, array_keys($tree));
    $this->add_node(
        array_diff($ancestors, $next_node) , 
        $tree[array_pop($next_node)]
        );  
  }