最简单的方法从祖先列表建立一棵树 [英] Easiest way to build a tree from a list of Ancestors

问题描述

在我心里，我觉得必须有一个超简单的递归解决方案，但是我不能马上解决它。

In my heart, I feel that there must be a super simple recursive solution to this, but I cannot immediately grok it.

我有一个树存储在SQL作为闭合表。该树看起来像：（1（2（3），4）），并且语言是MySQL的SQL和PHP 5.3。

I have a tree stored in SQL as a closure table. The tree looks like: (1 (2 (3), 4)), and the languages are MySQL's SQL and PHP 5.3.

p>

The closure table is thus:

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

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

I can query the ancestors quite easily with:

 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中获取更多的数据吗？

How can I easily build a tree in PHP with this data? Can I use a smarter query to pull more of the data from MySQL?

推荐答案

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

The first key is to sort the SQL results by the number of ancestors. I did this in PHP since I avoid the complexities of multi-digit numbers.

这提供了一个顺序中的节点列表，可以有效地插入它们。 p>

This provides a list of nodes in an order in which they can be validly inserted.

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
        )

)

在这一点上，我不在乎键，只有祖先的名单。通过树的路径可以在可用节点和剩余祖先的交集之间找到。

At this point, I don't care about the keys, only the lists of ancestors. The path through the tree can be found between the intersection of available nodes and the remaining ancestors.

  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)]
        );  
  }

这篇关于最简单的方法从祖先列表建立一棵树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！