Laravel 递归地获取分类法的所有后代

Question

我有一个名为 taxonomies 的表，它存储我的电子商务网站的所有产品分类法。这就是表格的样子：

+--------------+------------------+------+-----+---------+----------------+
| Field        | Type             | Null | Key | Default | Extra          |
+--------------+------------------+------+-----+---------+----------------+
| id           | int(10) unsigned | NO   | PRI | NULL    | auto_increment |
| name         | varchar(20)      | NO   | UNI | NULL    |                |
| parent_id    | int(10) unsigned | YES  | MUL | NULL    |                |
| num_products | smallint(6)      | NO   |     | 0       |                |
+--------------+------------------+------+-----+---------+----------------+

现在给定一个分类ID，我如何递归地获取它的所有后代ID？到目前为止我的努力：

public function getAllTaxonomyOffspringIds($parent_id, $offspring_ids = array()) {
    $taxonomy = Taxonomy::find($parent_id);
    if (!is_null($taxonomy)) {
        $first_generation_ids = $taxonomy->subtaxonomies()->lists('id');
        $offspring_ids = array_merge($offspring_ids, $first_generation_ids);
        if (count($first_generation_ids) > 0) {
            foreach ($first_generation_ids as $child_id) {
                self::getAllTaxonomyOffspringIds($child_id, $offspring_ids);
            }
            // foreach ($first_generation_ids as $child_id) {
            //  $child_taxonomy = Taxonomy::find($child_id);
            //  if (!is_null($child_taxonomy)) {
            //      $second_generation_ids = $child_taxonomy->subtaxonomies()->lists('id');
            //      $offspring_ids = array_merge($offspring_ids, $second_generation_ids);
            //      if (count($second_generation_ids)) {

            //      }
            //  }
            // }
        }
    }
    return $offspring_ids;
}

但它只给我第一代孩子的 ID...

Answer 1

这实际上是一个宽度优先的树遍历算法，这是我设法弄清楚如何实现的代码：

public function getTaxonomyChildren($id) {
    $taxonomy = Taxonomy::find($id);
    $child_ids = array();
    if (!is_null($taxonomy)) {
        $child_ids = $taxonomy->subtaxonomies()->lists('id');
    }
    return $child_ids;
}
public function getAllTaxonomyOffspringIds($parent_id, $offspring_ids = array()) {
    $child_ids = self::getTaxonomyChildren($parent_id);
    $offspring_ids = array_merge($offspring_ids, $child_ids);
    while (count($child_ids) > 0) {
        $temp_ids = array();
        foreach ($child_ids as $child_id) {
            $temp_ids = array_merge($temp_ids, self::getTaxonomyChildren($child_id));
        }
        $child_ids = $temp_ids;
        $offspring_ids = array_merge($offspring_ids, $child_ids);
    }
    return $offspring_ids;
}