Jaki jest najbardziej efektywny / elegancki sposób parsowania płaskiego stołu w drzewo?

Jeśli używasz zagnieżdżonych zestawów (czasami określanych jako zmodyfikowane pre-order Tree Traversal), możesz wyodrębnić całą strukturę drzewa lub dowolny podzbiór w nim w kolejności drzewa za pomocą jednego zapytania, kosztem wstawek, które są droższe, ponieważ musisz zarządzać kolumnami, które opisują ścieżkę w kolejności przez strukturę drzewa.

Dla django-mptt użyłem takiej struktury:

id  parent_id  tree_id  level  lft  rght
--  ---------  -------  -----  ---  ----
 1       null        1      0    1    14
 2          1        1      1    2     7
 3          2        1      2    3     4
 4          2        1      2    5     6
 5          1        1      1    8    13
 6          5        1      2    9    10
 7          5        1      2    11   12

Który opisuje drzewo, które wygląda tak (z id reprezentujące każdy pozycja):

 1
 +-- 2
 |   +-- 3
 |   +-- 4
 |
 +-- 5
     +-- 6
     +-- 7

Lub, jako zagnieżdżony diagram zestawu, który sprawia, że bardziej oczywiste jest, jak działają wartości lft i rght:

 __________________________________________________________________________
|  Root 1                                                                  |
|   ________________________________    ________________________________   |
|  |  Child 1.1                     |  |  Child 1.2                     |  |
|  |   ___________    ___________   |  |   ___________    ___________   |  |
|  |  |  C 1.1.1  |  |  C 1.1.2  |  |  |  |  C 1.2.1  |  |  C 1.2.2  |  |  |
1  2  3___________4  5___________6  7  8  9___________10 11__________12 13 14
|  |________________________________|  |________________________________|  |
|__________________________________________________________________________|

Jak widzisz, aby uzyskać cały podzbiór dla danego węzła, w kolejności drzewiastej, musisz po prostu wybrać wszystkie wiersze, które mają wartości lft i rght pomiędzy wartościami lft i rght. Łatwo jest również pobrać drzewo przodków dla danego węzła.

Kolumna level jest nieco denormalizacją dla wygody ponad wszystko i tree_id kolumna pozwala na ponowne uruchomienie numeracji lft i rght dla każdego węzła najwyższego poziomu, co zmniejsza liczbę kolumn dotkniętych wstawkami, przesunięciami i usunięciami, ponieważ Kolumny lft i rght muszą być odpowiednio dostosowane podczas tych operacji w celu utworzenia lub zamknięcia luk. Zrobiłem kilka uwag dotyczących rozwoju w czasie, gdy próbowałem zawinąć głowę wokół zapytań wymaganych dla każdej operacji.

Jeśli chodzi o rzeczywistą pracę z tymi danymi, aby wyświetlić drzewo, stworzyłem tree_item_iterator funkcja użytkowa, która dla każdego węzła powinna dostarczyć wystarczających informacji, aby wygenerować dowolny rodzaj wyświetlacza.

Więcej informacji o MPTT:

• drzewa w SQL
• przechowywanie danych hierarchicznych w bazie danych
• zarządzanie danymi hierarchicznymi w MySQL

Od wersji Oracle 9i można używać CONNECT BY.

SELECT LPAD(' ', (LEVEL - 1) * 4) || "Name" AS "Name"
FROM (SELECT * FROM TMP_NODE ORDER BY "Order")
CONNECT BY PRIOR "Id" = "ParentId"
START WITH "Id" IN (SELECT "Id" FROM TMP_NODE WHERE "ParentId" = 0)

Począwszy od SQL Server 2005, możesz używać rekurencyjnego wyrażenia common table (CTE).

WITH [NodeList] (
  [Id]
  , [ParentId]
  , [Level]
  , [Order]
) AS (
  SELECT [Node].[Id]
    , [Node].[ParentId]
    , 0 AS [Level]
    , CONVERT([varchar](MAX), [Node].[Order]) AS [Order]
  FROM [Node]
  WHERE [Node].[ParentId] = 0
  UNION ALL
  SELECT [Node].[Id]
    , [Node].[ParentId]
    , [NodeList].[Level] + 1 AS [Level]
    , [NodeList].[Order] + '|'
      + CONVERT([varchar](MAX), [Node].[Order]) AS [Order]
  FROM [Node]
    INNER JOIN [NodeList] ON [NodeList].[Id] = [Node].[ParentId]
) SELECT REPLICATE(' ', [NodeList].[Level] * 4) + [Node].[Name] AS [Name]
FROM [Node]
  INNER JOIN [NodeList] ON [NodeList].[Id] = [Node].[Id]
ORDER BY [NodeList].[Order]

Oba otrzymają następujące wyniki.

Name
'Node 1'
'    Node 1.1'
'        Node 1.1.1'
'    Node 1.2'
'Node 2'
'    Node 2.1'

To dość stare pytanie, ale ponieważ ma wiele poglądów, myślę, że warto przedstawić alternatywę, a moim zdaniem bardzo eleganckie rozwiązanie.

W celu odczytania struktury drzewa można użyć rekurencyjnych wyrażeń tabel wspólnych (CTEs). Daje możliwość pobrania całej struktury drzewa naraz, uzyskania informacji o poziomie węzła, jego węźle nadrzędnym i kolejności w obrębie węzłów potomnych węzła nadrzędnego.

Pokażę Ci jak to działa w PostgreSQL 9.1.

1. Utwórz strukturę

   CREATE TABLE tree (
       id int  NOT NULL,
       name varchar(32)  NOT NULL,
       parent_id int  NULL,
       node_order int  NOT NULL,
       CONSTRAINT tree_pk PRIMARY KEY (id),
       CONSTRAINT tree_tree_fk FOREIGN KEY (parent_id) 
         REFERENCES tree (id) NOT DEFERRABLE
   );
   
   
   insert into tree values
     (0, 'ROOT', NULL, 0),
     (1, 'Node 1', 0, 10),
     (2, 'Node 1.1', 1, 10),
     (3, 'Node 2', 0, 20),
     (4, 'Node 1.1.1', 2, 10),
     (5, 'Node 2.1', 3, 10),
     (6, 'Node 1.2', 1, 20);
   

2. Napisz zapytanie

   WITH RECURSIVE 
   tree_search (id, name, level, parent_id, node_order) AS (
     SELECT 
       id, 
       name,
       0,
       parent_id, 
       1 
     FROM tree
     WHERE parent_id is NULL
   
     UNION ALL 
     SELECT 
       t.id, 
       t.name,
       ts.level + 1, 
       ts.id, 
       t.node_order 
     FROM tree t, tree_search ts 
     WHERE t.parent_id = ts.id 
   ) 
   SELECT * FROM tree_search 
   WHERE level > 0 
   ORDER BY level, parent_id, node_order;
   

   Oto wyniki:

    id |    name    | level | parent_id | node_order 
   ----+------------+-------+-----------+------------
     1 | Node 1     |     1 |         0 |         10
     3 | Node 2     |     1 |         0 |         20
     2 | Node 1.1   |     2 |         1 |         10
     6 | Node 1.2   |     2 |         1 |         20
     5 | Node 2.1   |     2 |         3 |         10
     4 | Node 1.1.1 |     3 |         2 |         10
   (6 rows)
   

   Węzły drzewa są uporządkowane według poziomu głębokości. W końcowym efekcie zaprezentujemy je w kolejnych liniach.

   Dla każdego poziomu są one uporządkowane według parent_id i node_order w rodzicu. To mówi nam, jak przedstawić je w węźle output-link do rodzica w tej kolejności.

   Mając taką strukturę nie byłoby trudno zrobić naprawdę ładną prezentację w HTML.

   Rekurencyjne CTE są dostępne w PostgreSQL, IBM DB2, MS SQL Server i Oracle .

   Jeśli chcesz przeczytać więcej o rekurencyjnych zapytaniach SQL, możesz sprawdzić dokumentację swoich ulubionych DBMS lub przeczytać moje dwa artykuły dotyczące tego tematu:

   • zrób to w SQL: Recursive Tree Traversal
   • poznaj moc rekurencyjnych zapytań SQL

Odpowiedź Billa jest całkiem niezła, ta odpowiedź dodaje kilka rzeczy do niej, co sprawia, że chciałbym tak wspierane odpowiedzi.

W każdym razie chciałem wspierać strukturę drzewa i Właściwość Order. Dodałem do każdego węzła jedną właściwość o nazwie leftSibling, która robi to samo Order jest przeznaczona do zrobienia w pierwotnym pytaniu (utrzymuj kolejność od lewej do prawej).

mysql> desc nodes ;
+-------------+--------------+------+-----+---------+----------------+
| Field       | Type         | Null | Key | Default | Extra          |
+-------------+--------------+------+-----+---------+----------------+
| id          | int(11)      | NO   | PRI | NULL    | auto_increment |
| name        | varchar(255) | YES  |     | NULL    |                |
| leftSibling | int(11)      | NO   |     | 0       |                |
+-------------+--------------+------+-----+---------+----------------+
3 rows in set (0.00 sec)

mysql> desc adjacencies;
+------------+---------+------+-----+---------+----------------+
| Field      | Type    | Null | Key | Default | Extra          |
+------------+---------+------+-----+---------+----------------+
| relationId | int(11) | NO   | PRI | NULL    | auto_increment |
| parent     | int(11) | NO   |     | NULL    |                |
| child      | int(11) | NO   |     | NULL    |                |
| pathLen    | int(11) | NO   |     | NULL    |                |
+------------+---------+------+-----+---------+----------------+
4 rows in set (0.00 sec)

Więcej SZCZEGÓŁÓW I kodu SQL na moim blogu .

Dzięki Bill Twoja odpowiedź była pomocna w uzyskaniu zaczęło się!

Dobrze biorąc pod uwagę wybór, używałbym obiektów. Chciałbym utworzyć obiekt dla każdego rekordu, gdzie każdy obiekt ma kolekcję children i przechowywać je wszystkie w tablicy assoc (/hashtable), gdzie Id jest kluczem. I blitz przez kolekcję raz, dodając dzieci do odpowiednich pól dzieci. Proste.

Ale ponieważ nie jesteś zabawny ograniczając korzystanie z jakiegoś dobrego OOP, prawdopodobnie iterację bym napisał na podstawie:

function PrintLine(int pID, int level)
    foreach record where ParentID == pID
        print level*tabs + record-data
        PrintLine(record.ID, level + 1)

PrintLine(0, 0)

Edit: to jest podobne do kilku innych wpisów, ale myślę, że jest nieco czystsza. Jedna rzecz dodam: jest to bardzo intensywne SQL. To jest paskudne . Jeśli masz wybór, idź drogą OOP.

To zostało napisane szybko i nie jest ani ładne, ani wydajne (plus to autoboxes dużo, konwersja między int i Integer jest denerwujące!), ale działa.

Prawdopodobnie łamie zasady, ponieważ tworzę własne obiekty, ale hej, robię to jako odwrócenie od prawdziwej pracy:)

Zakłada to również, że zestaw wyników / tabela jest całkowicie wczytany do jakiejś struktury, zanim zaczniesz budować węzły, co nie byłoby najlepszym rozwiązaniem, jeśli masz setki tysięcy węzłów. rzędy.

public class Node {

    private Node parent = null;

    private List<Node> children;

    private String name;

    private int id = -1;

    public Node(Node parent, int id, String name) {
        this.parent = parent;
        this.children = new ArrayList<Node>();
        this.name = name;
        this.id = id;
    }

    public int getId() {
        return this.id;
    }

    public String getName() {
        return this.name;
    }

    public void addChild(Node child) {
        children.add(child);
    }

    public List<Node> getChildren() {
        return children;
    }

    public boolean isRoot() {
        return (this.parent == null);
    }

    @Override
    public String toString() {
        return "id=" + id + ", name=" + name + ", parent=" + parent;
    }
}

public class NodeBuilder {

    public static Node build(List<Map<String, String>> input) {

        // maps id of a node to it's Node object
        Map<Integer, Node> nodeMap = new HashMap<Integer, Node>();

        // maps id of a node to the id of it's parent
        Map<Integer, Integer> childParentMap = new HashMap<Integer, Integer>();

        // create special 'root' Node with id=0
        Node root = new Node(null, 0, "root");
        nodeMap.put(root.getId(), root);

        // iterate thru the input
        for (Map<String, String> map : input) {

            // expect each Map to have keys for "id", "name", "parent" ... a
            // real implementation would read from a SQL object or resultset
            int id = Integer.parseInt(map.get("id"));
            String name = map.get("name");
            int parent = Integer.parseInt(map.get("parent"));

            Node node = new Node(null, id, name);
            nodeMap.put(id, node);

            childParentMap.put(id, parent);
        }

        // now that each Node is created, setup the child-parent relationships
        for (Map.Entry<Integer, Integer> entry : childParentMap.entrySet()) {
            int nodeId = entry.getKey();
            int parentId = entry.getValue();

            Node child = nodeMap.get(nodeId);
            Node parent = nodeMap.get(parentId);
            parent.addChild(child);
        }

        return root;
    }
}

public class NodePrinter {

    static void printRootNode(Node root) {
        printNodes(root, 0);
    }

    static void printNodes(Node node, int indentLevel) {

        printNode(node, indentLevel);
        // recurse
        for (Node child : node.getChildren()) {
            printNodes(child, indentLevel + 1);
        }
    }

    static void printNode(Node node, int indentLevel) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < indentLevel; i++) {
            sb.append("\t");
        }
        sb.append(node);

        System.out.println(sb.toString());
    }

    public static void main(String[] args) {

        // setup dummy data
        List<Map<String, String>> resultSet = new ArrayList<Map<String, String>>();
        resultSet.add(newMap("1", "Node 1", "0"));
        resultSet.add(newMap("2", "Node 1.1", "1"));
        resultSet.add(newMap("3", "Node 2", "0"));
        resultSet.add(newMap("4", "Node 1.1.1", "2"));
        resultSet.add(newMap("5", "Node 2.1", "3"));
        resultSet.add(newMap("6", "Node 1.2", "1"));

        Node root = NodeBuilder.build(resultSet);
        printRootNode(root);

    }

    //convenience method for creating our dummy data
    private static Map<String, String> newMap(String id, String name, String parentId) {
        Map<String, String> row = new HashMap<String, String>();
        row.put("id", id);
        row.put("name", name);
        row.put("parent", parentId);
        return row;
    }
}

Zakładając, że wiesz, że pierwiastki główne są zerowe, oto pseudokod do wyjścia do tekstu:

function PrintLevel (int curr, int level)
    //print the indents
    for (i=1; i<=level; i++)
        print a tab
    print curr \n;
    for each child in the table with a parent of curr
        PrintLevel (child, level+1)


for each elementID where the parentid is zero
    PrintLevel(elementID, 0)

Możesz emulować dowolną inną strukturę danych za pomocą hashmapy, więc nie jest to straszne ograniczenie. Skanując od góry do dołu, tworzysz hashmapę dla każdego wiersza bazy danych, z wpisem dla każdej kolumny. Dodaj każdą z tych HashMap do hashmapy "master", wpisanej na id. Jeśli jakiś węzeł ma "rodzica", którego jeszcze nie widziałeś, utwórz dla niego wpis zastępczy w hashmapie głównym i wypełnij go, gdy zobaczysz rzeczywisty węzeł.

Aby go wydrukować, najpierw wykonaj prostą głębię przeprowadź przez dane, śledząc poziom wcięcia po drodze. Możesz to ułatwić, zachowując wpis "dzieci" dla każdego wiersza i wypełniając go podczas skanowania danych.

Jeśli chodzi o to, czy istnieje "lepszy" sposób przechowywania drzewa w bazie danych, to zależy od tego, jak zamierzasz wykorzystać dane. Widziałem systemy o znanej maksymalnej głębokości, które używały innej tabeli dla każdego poziomu w hierarchii. To ma sens, jeśli poziomy w drzewie nie są do końca równoważne po wszystkie (kategorie najwyższego poziomu są inne niż liście).

Istnieją naprawdę dobre rozwiązania, które wykorzystują wewnętrzną reprezentację btree indeksów sql. Jest to oparte na kilku wspaniałych badaniach przeprowadzonych około 1998 roku.

Oto przykładowa tabela (w mysql).

CREATE TABLE `node` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `name` varchar(255) NOT NULL,
  `tw` int(10) unsigned NOT NULL,
  `pa` int(10) unsigned DEFAULT NULL,
  `sz` int(10) unsigned DEFAULT NULL,
  `nc` int(11) GENERATED ALWAYS AS (tw+sz) STORED,
  PRIMARY KEY (`id`),
  KEY `node_tw_index` (`tw`),
  KEY `node_pa_index` (`pa`),
  KEY `node_nc_index` (`nc`),
  CONSTRAINT `node_pa_fk` FOREIGN KEY (`pa`) REFERENCES `node` (`tw`) ON DELETE CASCADE
)

Jedynymi polami niezbędnymi do reprezentacji drzewa są:

• tw: od lewej do prawej DFS Pre-order index, gdzie root = 1.
• pa: odniesienie (używając tw) do węzła nadrzędnego, root ma null.
• sz: wielkość gałęzi węzła, w tym siebie.
• nc: jest używany jako cukier składniowy. jest to tw+nc i reprezentuje tw "następnego dziecka" węzła.

+-----+---------+----+------+------+------+
| id  | name    | tw | pa   | sz   | nc   |
+-----+---------+----+------+------+------+
|   1 | Root    |  1 | NULL |   24 |   25 |
|   2 | A       |  2 |    1 |   14 |   16 |
|   3 | AA      |  3 |    2 |    1 |    4 |
|   4 | AB      |  4 |    2 |    7 |   11 |
|   5 | ABA     |  5 |    4 |    1 |    6 |
|   6 | ABB     |  6 |    4 |    3 |    9 |
|   7 | ABBA    |  7 |    6 |    1 |    8 |
|   8 | ABBB    |  8 |    6 |    1 |    9 |
|   9 | ABC     |  9 |    4 |    2 |   11 |
|  10 | ABCD    | 10 |    9 |    1 |   11 |
|  11 | AC      | 11 |    2 |    4 |   15 |
|  12 | ACA     | 12 |   11 |    2 |   14 |
|  13 | ACAA    | 13 |   12 |    1 |   14 |
|  14 | ACB     | 14 |   11 |    1 |   15 |
|  15 | AD      | 15 |    2 |    1 |   16 |
|  16 | B       | 16 |    1 |    1 |   17 |
|  17 | C       | 17 |    1 |    6 |   23 |
| 359 | C0      | 18 |   17 |    5 |   23 |
| 360 | C1      | 19 |   18 |    4 |   23 |
| 361 | C2(res) | 20 |   19 |    3 |   23 |
| 362 | C3      | 21 |   20 |    2 |   23 |
| 363 | C4      | 22 |   21 |    1 |   23 |
|  18 | D       | 23 |    1 |    1 |   24 |
|  19 | E       | 24 |    1 |    1 |   25 |
+-----+---------+----+------+------+------+

Każdy wynik drzewa może być wykonywany non-rekurencyjnie. Na przykład, aby uzyskać listę przodków węzła w tw='22'

Przodkowie

select anc.* from node me,node anc 
where me.tw=22 and anc.nc >= me.tw and anc.tw <= me.tw 
order by anc.tw;
+-----+---------+----+------+------+------+
| id  | name    | tw | pa   | sz   | nc   |
+-----+---------+----+------+------+------+
|   1 | Root    |  1 | NULL |   24 |   25 |
|  17 | C       | 17 |    1 |    6 |   23 |
| 359 | C0      | 18 |   17 |    5 |   23 |
| 360 | C1      | 19 |   18 |    4 |   23 |
| 361 | C2(res) | 20 |   19 |    3 |   23 |
| 362 | C3      | 21 |   20 |    2 |   23 |
| 363 | C4      | 22 |   21 |    1 |   23 |
+-----+---------+----+------+------+------+

Rodzeństwo i dzieci są trywialne - wystarczy użyć pola pa uporządkowanego przez tw.

Potomkowie

Na przykład zbiór (gałąź) węzłów zakorzenionych przy tw = 17.

select des.* from node me,node des 
where me.tw=17 and des.tw < me.nc and des.tw >= me.tw 
order by des.tw;
+-----+---------+----+------+------+------+
| id  | name    | tw | pa   | sz   | nc   |
+-----+---------+----+------+------+------+
|  17 | C       | 17 |    1 |    6 |   23 |
| 359 | C0      | 18 |   17 |    5 |   23 |
| 360 | C1      | 19 |   18 |    4 |   23 |
| 361 | C2(res) | 20 |   19 |    3 |   23 |
| 362 | C3      | 21 |   20 |    2 |   23 |
| 363 | C4      | 22 |   21 |    1 |   23 |
+-----+---------+----+------+------+------+

Uwagi Dodatkowe

Ta metodologia jest niezwykle przydatna, gdy jest znacznie większa liczba odczytów niż są wstawiane lub aktualizowane.

Ponieważ wstawianie, ruch lub aktualizacja węzła w drzewie wymaga dostosowania drzewa, konieczne jest zablokowanie tabeli przed rozpoczęciem akcji.

Koszt wstawiania/usuwania jest wysoki, ponieważ indeks tw i sz (rozmiar gałęzi) wartości będą musiały być aktualizowane odpowiednio dla wszystkich węzłów po punkcie wstawiania i dla wszystkich przodków.

Przenoszenie gałęzi polega na przeniesieniu wartości tw gałęzi poza zakres, dlatego konieczne jest również wyłączenie ograniczeń klucza obcego podczas przenoszenia gałęzi. Istnieją, zasadniczo cztery zapytania wymagane do przeniesienia gałęzi:

• Przesuń gałąź poza zasięg.
• zamknąć lukę, którą zostawił. (Pozostałe drzewo jest teraz znormalizowane).
• Otwórz lukę, gdzie będzie.
• Przenieś gałąź na nową pozycję.

Adjust Tree Queries

Otwieranie/zamykanie luk w drzewie jest ważną pod-funkcją używaną przez metody create/update/delete, więc dołączam ją tutaj.

Potrzebujemy dwóch parametrów-flagi określającej, czy zmniejszamy lub zwiększamy Rozmiar, oraz indeksu tw węzła. Tak więc, na przykład tw=18 (który ma rozmiar gałęzi 5). Załóżmy, że redukujemy (usuwamy tw) - to oznacza to, że używamy " - "zamiast" + " w aktualizacjach poniższego przykładu.

Najpierw używamy (nieco zmienionej) funkcji przodka do aktualizacji wartości sz.

update node me, node anc set anc.sz = anc.sz - me.sz from 
node me, node anc where me.tw=18 
and ((anc.nc >= me.tw and anc.tw < me.pa) or (anc.tw=me.pa));

Następnie musimy dostosować tw dla tych, których tw jest wyższa niż gałąź, która ma zostać usunięta.

update node me, node anc set anc.tw = anc.tw - me.sz from 
node me, node anc where me.tw=18 and anc.tw >= me.tw;

Następnie musimy dostosować rodzica dla tych, których tw pa jest wyższe niż gałąź, która ma zostać usunięta.

update node me, node anc set anc.pa = anc.pa - me.sz from 
node me, node anc where me.tw=18 and anc.pa >= me.tw;

Jeśli można utworzyć zagnieżdżone mapy hash lub tablice, to mogę po prostu zejść do tabeli Od początku i dodać każdy element do zagnieżdżonej tablicy. Muszę śledzić każdą linię do węzła głównego, aby wiedzieć, na którym poziomie zagnieżdżonej tablicy wstawić. Mogę korzystać z memoizacji, aby nie musieć szukać tego samego rodzica w kółko.

Edit: najpierw wczytałbym całą tabelę do tablicy, więc nie odpytywałby DB wielokrotnie. Oczywiście nie będzie to praktyczne, jeśli twój stół jest bardzo duży.

Po zbudowaniu struktury muszę najpierw przejść przez nią głębię i wydrukować HTML.

Nie ma lepszego fundamentalnego sposobu przechowywania tych informacji za pomocą jednej tabeli (mogę się jednak mylić;) i chciałbym zobaczyć lepsze rozwiązanie ). Jeśli jednak stworzysz schemat wykorzystujący dynamicznie tworzone tabele db, otworzysz zupełnie nowy świat kosztem prostoty i ryzyka SQL hell ;).

Jeśli elementy są w kolejności drzewiastej, jak pokazano w twoim przykładzie, możesz użyć czegoś takiego jak Poniższy przykład Pythona:

delimiter = '.'
stack = []
for item in items:
  while stack and not item.startswith(stack[-1]+delimiter):
    print "</div>"
    stack.pop()
  print "<div>"
  print item
  stack.append(item)

To, co robi, to utrzymuje stos reprezentujący bieżącą pozycję w drzewie. Dla każdego elementu w tabeli wyświetla elementy stosu (zamykając pasujące divs), dopóki nie znajdzie rodzica bieżącego elementu. Następnie wyprowadza początek tego węzła i pcha go do stosu.

Jeśli chcesz wypisać drzewo za pomocą wcięcia, a nie zagnieżdżenia elementy, można po prostu pominąć polecenia print, aby wydrukować divs, i wydrukować liczbę spacji równą pewnej wielokrotności rozmiaru stosu przed każdym elementem. Na przykład w Pythonie:

print "  " * len(stack)

Możesz również łatwo użyć tej metody do zbudowania zestawu zagnieżdżonych list lub słowników.

Edit: widzę z twojego wyjaśnienia, że nazwy nie miały być ścieżkami węzłów. To sugeruje alternatywne podejście:

idx = {}
idx[0] = []
for node in results:
  child_list = []
  idx[node.Id] = child_list
  idx[node.ParentId].append((node, child_list))

To tworzy drzewo tablic krotek (!). idx[0] reprezentuje korzeń (- y) drzewa. Każdy element w tablicy jest 2-krotką składającą się z samego węzła i listy wszystkich jego potomków. Po zbudowaniu możesz trzymać się idx[0] i odrzucić idx, chyba że chcesz uzyskać dostęp do węzłów po ich ID.

Aby rozszerzyć rozwiązanie SQL Billa, możesz w zasadzie zrobić to samo za pomocą płaskiej tablicy. Co więcej, jeśli wszystkie łańcuchy mają taką samą długość i znana jest maksymalna liczba dzieci (np. w drzewie binarnym), możesz to zrobić za pomocą pojedynczego łańcucha (tablica znaków). Jeśli masz dowolną liczbę dzieci, to trochę komplikuje sprawy... Musiałbym sprawdzić moje stare notatki, aby zobaczyć, co można zrobić.

Następnie, poświęcając trochę pamięci, zwłaszcza jeśli twoje drzewo jest rzadkie i / lub niesymetryczne, możesz, z odrobiną matematyki indeksowej, uzyskać dostęp do wszystkich łańcuchów losowo, przechowując swoje drzewo, szerokość najpierw w tablicy tak (dla drzewa binarnego):

String[] nodeArray = [L0root, L1child1, L1child2, L2Child1, L2Child2, L2Child3, L2Child4] ...

Yo know your string length, you know it

Jestem teraz w pracy, więc nie mogę poświęcić dużo czasu na to, ale z zainteresowaniem mogę pobrać trochę kodu, aby to zrobić.

Używamy tego do wyszukiwania w binarnych drzewach zbudowanych z kodonów DNA, procesu zbudowanego drzewo, następnie spłaszczamy je, aby przeszukać wzorce tekstowe i gdy je znajdziemy, index math (revers from above) dostajemy węzeł z powrotem... bardzo szybkie i wydajne, trudne nasze drzewo rzadko miało puste węzły, ale mogliśmy przeszukiwać gigabajty danych w mgnieniu oka.

Pomyśl o używaniu narzędzi nosql, takich jak neo4j dla struktur hierarchicznych. np. aplikacja sieciowa, taka jak linkedin, korzysta z couchbase (innego rozwiązania nosql)

Ale używaj nosql tylko do zapytań poziomu data-mart, a nie do przechowywania / utrzymywania transakcji