Jak sprawnie zbudować drzewo z płaskiej konstrukcji?

153

Mam kilka obiektów w płaskiej strukturze. Obiekty te mają IDi do ParentIDwłasności, więc mogą być umieszczone na drzewach. Nie są w określonej kolejności. Każda ParentIDwłaściwość niekoniecznie jest zgodna z IDw strukturze. Dlatego może to być kilka drzew wyłaniających się z tych obiektów.

Jak przetworzyłbyś te obiekty, aby stworzyć powstałe drzewa?

Nie jestem tak daleko od rozwiązania, ale jestem pewien, że jest dalekie od optymalnego ...

Muszę utworzyć te drzewa, aby następnie wstawić dane do bazy danych we właściwej kolejności.

Brak odniesień cyklicznych. Węzeł jest RootNode, gdy ParentID == null lub gdy nie można znaleźć ParentID w innych obiektach

Costo
źródło
Co rozumiesz przez „tworzenie”? Renderować w interfejsie użytkownika? Przechowywać hierarchicznie w XML czy w bazie danych?
RedFilter
Jak zdefiniować węzeł bez rodzica (tj. Węzeł główny). ParentID ma wartość null? ParentID = 0? Zakładam, że nie ma okrągłych odniesień, prawda?
Jason Punyon
5
Uważam, że to pytanie jest całkiem fajne.
nes1983
1
sprawdź ten artykuł: scip.be/index.php?Page=ArticlesNET23&Lang=NL
ebram khalil

Odpowiedzi:

120

Przechowuj identyfikatory obiektów w tabeli skrótów mapujących na określony obiekt. Wylicz wszystkie obiekty i znajdź ich rodzica, jeśli istnieje, i odpowiednio zaktualizuj jego wskaźnik nadrzędny.

class MyObject
{ // The actual object
    public int ParentID { get; set; }
    public int ID { get; set; }
}

class Node
{
    public List<Node> Children = new List<Node>();
    public Node Parent { get; set; }
    public MyObject AssociatedObject { get; set; }
}

IEnumerable<Node> BuildTreeAndGetRoots(List<MyObject> actualObjects)
{
    Dictionary<int, Node> lookup = new Dictionary<int, Node>();
    actualObjects.ForEach(x => lookup.Add(x.ID, new Node { AssociatedObject = x }));
    foreach (var item in lookup.Values) {
        Node proposedParent;
        if (lookup.TryGetValue(item.AssociatedObject.ParentID, out proposedParent)) {
            item.Parent = proposedParent;
            proposedParent.Children.Add(item);
        }
    }
    return lookup.Values.Where(x => x.Parent == null);
}
Mehrdad Afshari
źródło
5
który to język? (Rozumiem C #)
Jason S
3
Ten algo to (w notacji nieformalnej) O (3N), gdzie rozwiązanie O (1N) jest łatwo osiągalne przez utworzenie instancji częściowych węzłów dla nieprzekraczanych rodziców LUB przez zachowanie drugorzędnych tabel wyszukiwania dla elementów potomnych nieskonfigurowanych rodzice. Prawdopodobnie nie ma to znaczenia dla większości zastosowań w świecie rzeczywistym, ale może mieć znaczenie w przypadku dużych zbiorów danych.
Andrew Hanlon,
15
@AndrewHanlon może powinieneś opublikować sol za 0 (1BA)
Ced
1
Odpowiedź @Ced Martin Schmidt poniżej jest bardzo zbliżona do tego, jak bym ją wdrożył. Jak widać, używa pojedynczej pętli, a reszta to operacje haszujące.
Andrew Hanlon,
26
O (3N) to po prostu O (N);)
JakeWilson801
34

W oparciu o odpowiedź Mehrdada Afshariego i komentarz Andrew Hanlona dotyczący przyspieszenia, oto moje podejście.

Ważna różnica w stosunku do pierwotnego zadania: Węzeł główny ma identyfikator == parentID.

class MyObject
{   // The actual object
    public int ParentID { get; set; }
    public int ID { get; set; }
}

class Node
{
    public List<Node> Children = new List<Node>();
    public Node Parent { get; set; }
    public MyObject Source { get; set; }
}

List<Node> BuildTreeAndGetRoots(List<MyObject> actualObjects)
{
    var lookup = new Dictionary<int, Node>();
    var rootNodes = new List<Node>();

    foreach (var item in actualObjects)
    {
        // add us to lookup
        Node ourNode;
        if (lookup.TryGetValue(item.ID, out ourNode))
        {   // was already found as a parent - register the actual object
            ourNode.Source = item;
        }
        else
        {
            ourNode = new Node() { Source = item };
            lookup.Add(item.ID, ourNode);
        }

        // hook into parent
        if (item.ParentID == item.ID)
        {   // is a root node
            rootNodes.Add(ourNode);
        }
        else
        {   // is a child row - so we have a parent
            Node parentNode;
            if (!lookup.TryGetValue(item.ParentID, out parentNode))
            {   // unknown parent, construct preliminary parent
                parentNode = new Node();
                lookup.Add(item.ParentID, parentNode);
            }
            parentNode.Children.Add(ourNode);
            ourNode.Parent = parentNode;
        }
    }

    return rootNodes;
}
Martin Schmidt
źródło
1
Fajnie, to jest w zasadzie podejście, do którego nawiązywałem. Chciałbym jednak po prostu użyć pseudo węzła głównego (z ID = 0 i zerowym rodzicielem) i usunąć wymóg samodzielnego odniesienia.
Andrew Hanlon,
Jedyne, czego brakuje w tym przykładzie, to przypisanie pola Parent do każdego węzła podrzędnego. Aby to zrobić, wystarczy ustawić pole nadrzędne po dodaniu elementów podrzędnych do jego kolekcji nadrzędnej. Na przykład: parentNode.Children.Add (ourNode); ourNode.Parent = parentNode;
plauriola
@plauriola True, dzięki, dodałem to. Alternatywą byłoby po prostu usunięcie właściwości Parent, nie jest to konieczne dla podstawowego algorytmu.
Martin Schmidt
4
Ponieważ nie mogłem znaleźć modułu npm implementującego rozwiązanie O (n), stworzyłem następujący (testowany jednostkowo, 100% pokrycia kodu, tylko 0,5 kb i zawiera typowania. Może to komuś pomoże: npmjs.com/package / performant-array-to-tree
Philip Stanislaus
32

Oto prosty algorytm JavaScript do analizowania płaskiej tabeli w strukturę drzewa nadrzędnego / podrzędnego, która działa w czasie N:

var table = [
    {parent_id: 0, id: 1, children: []},
    {parent_id: 0, id: 2, children: []},
    {parent_id: 0, id: 3, children: []},
    {parent_id: 1, id: 4, children: []},
    {parent_id: 1, id: 5, children: []},
    {parent_id: 1, id: 6, children: []},
    {parent_id: 2, id: 7, children: []},
    {parent_id: 7, id: 8, children: []},
    {parent_id: 8, id: 9, children: []},
    {parent_id: 3, id: 10, children: []}
];

var root = {id:0, parent_id: null, children: []};
var node_list = { 0 : root};

for (var i = 0; i < table.length; i++) {
    node_list[table[i].id] = table[i];
    node_list[table[i].parent_id].children.push(node_list[table[i].id]);
}

console.log(root);
Eugene
źródło
próbując przekonwertować to podejście do C #.
hakan
zdałem sobie sprawę, że jeśli id ​​zaczyna się od czegoś dużego, takiego jak 1001, to otrzymujemy indeks poza
granicami
2
Wskazówka: użyj, console.log(JSON.stringify(root, null, 2));aby ładnie wydrukować wynik.
aloisdg przenosi się na codidact.com
14

Rozwiązanie w Pythonie

def subtree(node, relationships):
    return {
        v: subtree(v, relationships) 
        for v in [x[0] for x in relationships if x[1] == node]
    }

Na przykład:

# (child, parent) pairs where -1 means no parent    
flat_tree = [
     (1, -1),
     (4, 1),
     (10, 4),
     (11, 4),
     (16, 11),
     (17, 11),
     (24, 17),
     (25, 17),
     (5, 1),
     (8, 5),
     (9, 5),
     (7, 9),
     (12, 9),
     (22, 12),
     (23, 12),
     (2, 23),
     (26, 23),
     (27, 23),
     (20, 9),
     (21, 9)
    ]

subtree(-1, flat_tree)

Produkuje:

{
    "1": {
        "4": {
            "10": {}, 
            "11": {
                "16": {}, 
                "17": {
                    "24": {}, 
                    "25": {}
                }
            }
        }, 
        "5": {
            "8": {}, 
            "9": {
                "20": {}, 
                "12": {
                    "22": {}, 
                    "23": {
                        "2": {}, 
                        "27": {}, 
                        "26": {}
                    }
                }, 
                "21": {}, 
                "7": {}
            }
        }
    }
}
minkwe
źródło
Cześć. Jak dodać kolejny atrybut w danych wyjściowych? to znaczy. name, parent_id
simple guy
zdecydowanie najbardziej elegancki!
ccpizza
@simpleguy: zrozumienie listy można rozwinąć, jeśli potrzebujesz większej kontroli, np .:def recurse(id, pages): for row in rows: if row['id'] == id: print(f'''{row['id']}:{row['parent_id']} {row['path']} {row['title']}''') recurse(row['id'], rows)
ccpizza
8

Wersja JS, która zwraca jeden katalog główny lub tablicę korzeni, z których każdy będzie miał właściwość tablicową Children zawierającą powiązane dzieci. Nie zależy od uporządkowanego wejścia, przyzwoicie zwarty i nie używa rekurencji. Cieszyć się!

// creates a tree from a flat set of hierarchically related data
var MiracleGrow = function(treeData, key, parentKey)
{
    var keys = [];
    treeData.map(function(x){
        x.Children = [];
        keys.push(x[key]);
    });
    var roots = treeData.filter(function(x){return keys.indexOf(x[parentKey])==-1});
    var nodes = [];
    roots.map(function(x){nodes.push(x)});
    while(nodes.length > 0)
    {

        var node = nodes.pop();
        var children =  treeData.filter(function(x){return x[parentKey] == node[key]});
        children.map(function(x){
            node.Children.push(x);
            nodes.push(x)
        });
    }
    if (roots.length==1) return roots[0];
    return roots;
}


// demo/test data
var treeData = [

    {id:9, name:'Led Zep', parent:null},
    {id:10, name:'Jimmy', parent:9},
    {id:11, name:'Robert', parent:9},
    {id:12, name:'John', parent:9},

    {id:8, name:'Elec Gtr Strings', parent:5},
    {id:1, name:'Rush', parent:null},
    {id:2, name:'Alex', parent:1},
    {id:3, name:'Geddy', parent:1},
    {id:4, name:'Neil', parent:1},
    {id:5, name:'Gibson Les Paul', parent:2},
    {id:6, name:'Pearl Kit', parent:4},
    {id:7, name:'Rickenbacker', parent:3},

    {id:100, name:'Santa', parent:99},
    {id:101, name:'Elf', parent:100},

];
var root = MiracleGrow(treeData, "id", "parent")
console.log(root)
nu11ptr
źródło
2
To pytanie ma 7 lat i ma już zagłosowaną i zaakceptowaną odpowiedź. Jeśli uważasz, że masz lepsze rozwiązanie, wspaniale byłoby dodać wyjaśnienie do swojego kodu.
Jordi Nebot
To podejście działa dobrze w przypadku tego nieuporządkowanego typu danych.
Cody C
4

Znalazłem niesamowitą wersję JavaScript tutaj: http://oskarhane.com/create-a-nested-array-recursively-in-javascript/

Powiedzmy, że masz taką tablicę:

const models = [
    {id: 1, title: 'hello', parent: 0},
    {id: 2, title: 'hello', parent: 0},
    {id: 3, title: 'hello', parent: 1},
    {id: 4, title: 'hello', parent: 3},
    {id: 5, title: 'hello', parent: 4},
    {id: 6, title: 'hello', parent: 4},
    {id: 7, title: 'hello', parent: 3},
    {id: 8, title: 'hello', parent: 2}
];

I chcesz mieć obiekty zagnieżdżone w następujący sposób:

const nestedStructure = [
    {
        id: 1, title: 'hello', parent: 0, children: [
            {
                id: 3, title: 'hello', parent: 1, children: [
                    {
                        id: 4, title: 'hello', parent: 3, children: [
                            {id: 5, title: 'hello', parent: 4},
                            {id: 6, title: 'hello', parent: 4}
                        ]
                    },
                    {id: 7, title: 'hello', parent: 3}
                ]
            }
        ]
    },
    {
        id: 2, title: 'hello', parent: 0, children: [
            {id: 8, title: 'hello', parent: 2}
        ]
    }
];

Oto funkcja rekurencyjna, która to umożliwia.

function getNestedChildren(models, parentId) {
    const nestedTreeStructure = [];
    const length = models.length;

    for (let i = 0; i < length; i++) { // for-loop for perf reasons, huge difference in ie11
        const model = models[i];

        if (model.parent == parentId) {
            const children = getNestedChildren(models, model.id);

            if (children.length > 0) {
                model.children = children;
            }

            nestedTreeStructure.push(model);
        }
    }

    return nestedTreeStructure;
}

Zastosowanie:

const models = [
    {id: 1, title: 'hello', parent: 0},
    {id: 2, title: 'hello', parent: 0},
    {id: 3, title: 'hello', parent: 1},
    {id: 4, title: 'hello', parent: 3},
    {id: 5, title: 'hello', parent: 4},
    {id: 6, title: 'hello', parent: 4},
    {id: 7, title: 'hello', parent: 3},
    {id: 8, title: 'hello', parent: 2}
];
const nestedStructure = getNestedChildren(models, 0);
codeBelt
źródło
Dla każdego rodzica Czy zapętla cały model - czy to nie jest O (N ^ 2)?
Ed Randall,
4

Dla wszystkich zainteresowanych wersją C # rozwiązania Eugene'a, pamiętaj, że lista węzłów jest dostępna jako mapa, więc zamiast tego użyj Dictionary.

Pamiętaj, że to rozwiązanie działa tylko wtedy, gdy tabela jest posortowana według parent_id .

var table = new[]
{
    new Node { parent_id = 0, id = 1 },
    new Node { parent_id = 0, id = 2 },
    new Node { parent_id = 0, id = 3 },
    new Node { parent_id = 1, id = 4 },
    new Node { parent_id = 1, id = 5 },
    new Node { parent_id = 1, id = 6 },
    new Node { parent_id = 2, id = 7 },
    new Node { parent_id = 7, id = 8 },
    new Node { parent_id = 8, id = 9 },
    new Node { parent_id = 3, id = 10 },
};

var root = new Node { id = 0 };
var node_list = new Dictionary<int, Node>{
    { 0, root }
};

foreach (var item in table)
{
    node_list.Add(item.id, item);
    node_list[item.parent_id].children.Add(node_list[item.id]);
}

Węzeł jest zdefiniowany w następujący sposób.

class Node
{
    public int id { get; set; }
    public int parent_id { get; set; }
    public List<Node> children = new List<Node>();
}
Joel Malone
źródło
1
Jest zbyt stary, ale pozycja 8 listy new Node { parent_id = 7, id = 9 },uniemożliwia node_list.Add(item.id, item);ukończenie, ponieważ klucz nie może się powtórzyć; to literówka; więc zamiast id = 9 wpisz id = 8
Marcelo Scofano
Naprawiony. Dzięki @MarceloScofano!
Joel Malone
3

Ogólne rozwiązanie napisałem w C # luźno na podstawie odpowiedzi @Mehrdad Afshari:

void Example(List<MyObject> actualObjects)
{
  List<TreeNode<MyObject>> treeRoots = actualObjects.BuildTree(obj => obj.ID, obj => obj.ParentID, -1);
}

public class TreeNode<T>
{
  public TreeNode(T value)
  {
    Value = value;
    Children = new List<TreeNode<T>>();
  }

  public T Value { get; private set; }
  public List<TreeNode<T>> Children { get; private set; }
}

public static class TreeExtensions
{
  public static List<TreeNode<TValue>> BuildTree<TKey, TValue>(this IEnumerable<TValue> objects, Func<TValue, TKey> keySelector, Func<TValue, TKey> parentKeySelector, TKey defaultKey = default(TKey))
  {
    var roots = new List<TreeNode<TValue>>();
    var allNodes = objects.Select(overrideValue => new TreeNode<TValue>(overrideValue)).ToArray();
    var nodesByRowId = allNodes.ToDictionary(node => keySelector(node.Value));

    foreach (var currentNode in allNodes)
    {
      TKey parentKey = parentKeySelector(currentNode.Value);
      if (Equals(parentKey, defaultKey))
      {
        roots.Add(currentNode);
      }
      else
      {
        nodesByRowId[parentKey].Children.Add(currentNode);
      }
    }

    return roots;
  }
}
HuBeZa
źródło
Wyborcy przeciw, proszę o komentarz. Z przyjemnością dowiem się, co zrobiłem źle.
HuBeZa
2

Oto java rozwiązanie odpowiedzi autorstwa Mehrdada Afshariego.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

public class Tree {

    Iterator<Node> buildTreeAndGetRoots(List<MyObject> actualObjects) {
        Map<Integer, Node> lookup = new HashMap<>();
        actualObjects.forEach(x -> lookup.put(x.id, new Node(x)));
        //foreach (var item in lookup.Values)
        lookup.values().forEach(item ->
                {
                    Node proposedParent;
                    if (lookup.containsKey(item.associatedObject.parentId)) {
                        proposedParent = lookup.get(item.associatedObject.parentId);
                        item.parent = proposedParent;
                        proposedParent.children.add(item);
                    }
                }
        );
        //return lookup.values.Where(x =>x.Parent ==null);
        return lookup.values().stream().filter(x -> x.parent == null).iterator();
    }

}

class MyObject { // The actual object
    public int parentId;
    public int id;
}

class Node {
    public List<Node> children = new ArrayList<Node>();
    public Node parent;
    public MyObject associatedObject;

    public Node(MyObject associatedObject) {
        this.associatedObject = associatedObject;
    }
}
Vimal Bhatt
źródło
Powinieneś trochę wyjaśnić, jaki jest twój pomysł na kod.
Ziad Akiki,
To tylko Java tłumaczenie wcześniejszej odpowiedzi
Vimal Bhatt
1

Choć wydaje mi się to niejasne, prawdopodobnie stworzyłbym mapę z identyfikatora do rzeczywistego obiektu. W pseudo-java (nie sprawdzałem czy działa / kompiluje się) może to być coś takiego:

Map<ID, FlatObject> flatObjectMap = new HashMap<ID, FlatObject>();

for (FlatObject object: flatStructure) {
    flatObjectMap.put(object.ID, object);
}

I żeby sprawdzić każdego rodzica:

private FlatObject getParent(FlatObject object) {
    getRealObject(object.ParentID);
}

private FlatObject getRealObject(ID objectID) {
    flatObjectMap.get(objectID);
}

Używając ponownie getRealObject(ID)i wykonując mapę od obiektu do kolekcji obiektów (lub ich identyfikatorów), otrzymujesz również mapę rodzic-> dzieci.

Henrik Paul
źródło
1

Mogę to zrobić w 4 liniach kodu i czasie O (n log n), zakładając, że Dictionary jest czymś w rodzaju TreeMap.

dict := Dictionary new.
ary do: [:each | dict at: each id put: each].
ary do: [:each | (dict at: each parent) addChild: each].
root := dict at: nil.

EDYCJA : Ok, a teraz czytam, że niektóre identyfikatory rodzicielskie są fałszywe, więc zapomnij o powyższym i zrób to:

dict := Dictionary new.
dict at: nil put: OrderedCollection new.
ary do: [:each | dict at: each id put: each].
ary do: [:each | 
    (dict at: each parent ifAbsent: [dict at: nil]) 
          add: each].
roots := dict at: nil.
nes1983
źródło
1

Większość odpowiedzi zakłada, że ​​chcesz to zrobić poza bazą danych. Jeśli Twoje drzewa są z natury względnie statyczne i musisz w jakiś sposób zmapować je do bazy danych, możesz rozważyć użycie zagnieżdżonych reprezentacji zbiorów po stronie bazy danych. Sprawdź książki autorstwa Joe Celko (lub tutaj, aby uzyskać przegląd autorstwa Celko).

Jeśli mimo to jesteś powiązany z Oracle DBS, sprawdź ich CONNECT BY, aby zapoznać się z prostymi podejściami SQL.

W obu przypadkach można całkowicie pominąć mapowanie drzew przed załadowaniem danych do bazy danych. Pomyślałem, że zaoferuję to jako alternatywę, może to być całkowicie nieodpowiednie dla twoich konkretnych potrzeb. Cała część oryginalnego pytania dotycząca „właściwej kolejności” sugeruje, że z jakiegoś powodu potrzebujesz, aby kolejność była „poprawna” w bazie danych? To może popchnąć mnie do zajmowania się tam również drzewami.


źródło
1

Nie jest to dokładnie to samo, czego szukał pytający, ale miałem trudności z objęciem odpowiedzi udzielonych tutaj niejednoznacznie sformułowanych i nadal uważam, że ta odpowiedź pasuje do tytułu.

Moją odpowiedzią jest odwzorowanie płaskiej struktury na drzewo bezpośrednio na obiekcie, w którym wszystko, co masz, to znak ParentIDna każdym obiekcie. ParentIDjest nulllub 0jeśli jest to root. Naprzeciw pytającego zakładam, że wszystkie ważne ParentIDpunkty wskazują na coś innego na liście:

var rootNodes = new List<DTIntranetMenuItem>();
var dictIntranetMenuItems = new Dictionary<long, DTIntranetMenuItem>();

//Convert the flat database items to the DTO's,
//that has a list of children instead of a ParentID.
foreach (var efIntranetMenuItem in flatIntranetMenuItems) //List<tblIntranetMenuItem>
{
    //Automapper (nuget)
    DTIntranetMenuItem intranetMenuItem =
                                   Mapper.Map<DTIntranetMenuItem>(efIntranetMenuItem);
    intranetMenuItem.Children = new List<DTIntranetMenuItem>();
    dictIntranetMenuItems.Add(efIntranetMenuItem.ID, intranetMenuItem);
}

foreach (var efIntranetMenuItem in flatIntranetMenuItems)
{
    //Getting the equivalent object of the converted ones
    DTIntranetMenuItem intranetMenuItem = dictIntranetMenuItems[efIntranetMenuItem.ID];

    if (efIntranetMenuItem.ParentID == null || efIntranetMenuItem.ParentID <= 0)
    {
        rootNodes.Add(intranetMenuItem);
    }
    else
    {
        var parent = dictIntranetMenuItems[efIntranetMenuItem.ParentID.Value];
        parent.Children.Add(intranetMenuItem);
        //intranetMenuItem.Parent = parent;
    }
}
return rootNodes;
Zapytaj B.
źródło
1

oto implementacja ruby:

Kataloguje według nazwy atrybutu lub wyniku wywołania metody.

CatalogGenerator = ->(depth) do
  if depth != 0
    ->(hash, key) do
      hash[key] = Hash.new(&CatalogGenerator[depth - 1])
    end
  else
    ->(hash, key) do
      hash[key] = []
    end
  end
end

def catalog(collection, root_name: :root, by:)
  method_names = [*by]
  log = Hash.new(&CatalogGenerator[method_names.length])
  tree = collection.each_with_object(log) do |item, catalog|
    path = method_names.map { |method_name| item.public_send(method_name)}.unshift(root_name.to_sym)
  catalog.dig(*path) << item
  end
  tree.with_indifferent_access
end

 students = [#<Student:0x007f891d0b4818 id: 33999, status: "on_hold", tenant_id: 95>,
 #<Student:0x007f891d0b4570 id: 7635, status: "on_hold", tenant_id: 6>,
 #<Student:0x007f891d0b42c8 id: 37220, status: "on_hold", tenant_id: 6>,
 #<Student:0x007f891d0b4020 id: 3444, status: "ready_for_match", tenant_id: 15>,
 #<Student:0x007f8931d5ab58 id: 25166, status: "in_partnership", tenant_id: 10>]

catalog students, by: [:tenant_id, :status]

# this would out put the following
{"root"=>
  {95=>
    {"on_hold"=>
      [#<Student:0x007f891d0b4818
        id: 33999,
        status: "on_hold",
        tenant_id: 95>]},
   6=>
    {"on_hold"=>
      [#<Student:0x007f891d0b4570 id: 7635, status: "on_hold", tenant_id: 6>,
       #<Student:0x007f891d0b42c8
        id: 37220,
        status: "on_hold",
        tenant_id: 6>]},
   15=>
    {"ready_for_match"=>
      [#<Student:0x007f891d0b4020
        id: 3444,
        status: "ready_for_match",
        tenant_id: 15>]},
   10=>
    {"in_partnership"=>
      [#<Student:0x007f8931d5ab58
        id: 25166,
        status: "in_partnership",
        tenant_id: 10>]}}}
joegiralt
źródło
1

Zaakceptowana odpowiedź wydaje mi się zbyt złożona, więc dodaję jej wersje Ruby i NodeJS

Załóżmy, że lista węzłów płaskich ma następującą strukturę:

nodes = [
  { id: 7, parent_id: 1 },
  ...
] # ruby

nodes = [
  { id: 7, parentId: 1 },
  ...
] # nodeJS

Funkcje, które zmienią płaską strukturę listy powyżej w drzewo, wyglądają następująco

dla Rubiego:

def to_tree(nodes)

  nodes.each do |node|

    parent = nodes.find { |another| another[:id] == node[:parent_id] }
    next unless parent

    node[:parent] = parent
    parent[:children] ||= []
    parent[:children] << node

  end

  nodes.select { |node| node[:parent].nil? }

end

dla NodeJS:

const toTree = (nodes) => {

  nodes.forEach((node) => {

    const parent = nodes.find((another) => another.id == node.parentId)
    if(parent == null) return;

    node.parent = parent;
    parent.children = parent.children || [];
    parent.children = parent.children.concat(node);

  });

  return nodes.filter((node) => node.parent == null)

};
Hirurg103
źródło
nullundefined
Wydaje
@Ullauri null == undefined => truew NodeJS
Hirurg103
1

jednym eleganckim sposobem na to jest przedstawienie pozycji na liście jako łańcucha zawierającego listę rodziców rozdzielonych kropkami, a na koniec wartość:

server.port=90
server.hostname=localhost
client.serverport=90
client.database.port=1234
client.database.host=localhost

Podczas montażu drzewa otrzymujesz coś takiego:

server:
  port: 90
  hostname: localhost
client:
  serverport=1234
  database:
    port: 1234
    host: localhost

Mam bibliotekę konfiguracji, która implementuje tę konfigurację zastąpienia (drzewo) z argumentów wiersza polecenia (lista). Algorytm dodawania pojedynczego elementu do listy do drzewa jest tutaj .

Omry Yadan
źródło
0

Czy utknąłeś, używając tylko tych atrybutów? Jeśli nie, fajnie byłoby utworzyć tablicę węzłów potomnych, w której można raz przejść przez wszystkie te obiekty, aby zbudować takie atrybuty. Stamtąd wybierz węzeł z dziećmi, ale bez rodziców i iteracyjnie utwórz drzewo od góry do dołu.

Robert Elwell
źródło
0

wersja java

// node
@Data
public class Node {
    private Long id;
    private Long parentId;
    private String name;
    private List<Node> children = new ArrayList<>();
}

// flat list to tree
List<Node> nodes = new ArrayList();// load nodes from db or network
Map<Long, Node> nodeMap = new HashMap();
nodes.forEach(node -> {
  if (!nodeMap.containsKey(node.getId)) nodeMap.put(node.getId, node);
  if (nodeMap.containsKey(node.getParentId)) {
    Node parent = nodeMap.get(node.getParentId);
    node.setParentId(parent.getId());
    parent.getChildren().add(node);
  }
});

// tree node
List<Node> treeNode = nodeMap .values().stream().filter(n -> n.getParentId() == null).collect(Collectors.toList());
Aldom Michael
źródło