Najprostszy sposób na zbudowanie drzewa z listy przodków

Question

W moim sercu czuję, że musi to być super proste rozwiązanie rekursywne, ale nie mogę od razu tego zignorować.

Mam drzewo przechowywane w SQL jako tabela zamknięcia. Drzewo wygląda jak: (1 (2 (3), 4)), a językami są SQL i PHP 5.3 MySQL.

tabela zamknięcie jest więc:

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

mogę kwerendy przodków dość łatwo:

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  | 
+----+-----------+ 

Jak można łatwo zbudować drzewo w PHP z tymi danymi? Czy mogę użyć bardziej inteligentnej kwerendy do pobrania większej ilości danych z MySQL?

Answer 1

Pierwszy klucz to sortowanie wyników SQL przez liczbę przodków. Zrobiłem to w PHP, ponieważ unikam złożoności liczb wielocyfrowych.

Zawiera listę węzłów w kolejności, w której można je poprawnie wstawić.

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 
     ) 

) 

W tym momencie nie interesują mnie klucze, tylko listy przodków. Ścieżka przez drzewo znajduje się pomiędzy przecięciem dostępnych węzłów i pozostałymi przodkami.

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

Answer 2

Użyłem tabeli zamknięcia (termin brzmi dziwnie dla mnie ... Zapomniałem, co/gdzie usłyszałem, nazywa się coś innego), ale miałem 3 kolumnę "odległości" między przodkiem a potomkiem, która pozwala rozróżniasz bezpośrednich potomków (dzieci) i pośrednich potomków (wnuki itp.).

Z technicznego punktu widzenia wymieniona tabela może rejestrować dane na skierowanym wykresie acyklicznym, więc utworzenie hierarchicznego drzewa bez powielonych sekcji może być niemożliwe.

edit:

Gdybym kwerend w PHP, I pewnie wystarczy wybrać na samej tabeli w/o użyciu GROUP_CONCAT - idziesz do przetwarzania rzeczy proceduralnie i tak, więc dlaczego nie po prostu uzyskać odpowiedni podzbiór tabeli zamknięcia w jego najsurowszej formie?

Należy również pamiętać, że tabela zamknięcia nie będzie przechowywać informacji o zamówieniu (jeśli jest to ważne).

Jeśli aspekty drzewiastych danych hierarchicznych są bardzo ważne, a użytkownik ma wybór sposobu przechowywania danych, należy rozważyć nested set model, który może utrzymać porządek i jest o wiele łatwiejszy do odtworzenia drzewa.