Cách dễ nhất để xây dựng cây từ danh sách Tổ tiên

Chìa khóa đầu tiên là sắp xếp các kết quả SQL theo số lượng tổ tiên. Tôi đã làm điều này trong PHP vì tôi tránh được sự phức tạp của các số có nhiều chữ số.

Điều này cung cấp danh sách các nút theo thứ tự mà chúng có thể được chèn hợp lệ.

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
        )

)

Tại thời điểm này, tôi không quan tâm đến các chìa khóa, chỉ có danh sách của tổ tiên. Đường dẫn xuyên qua cây có thể được tìm thấy giữa giao điểm của các nút có sẵn và các nút tổ tiên còn lại.

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