¿Cómo construir eficientemente un árbol a partir de una estructura plana?

153

Tengo un montón de objetos en una estructura plana. Estos objetos tienen una IDy una ParentIDpropiedad para que puedan organizarse en árboles. No están en un orden particular. Cada ParentIDpropiedad no necesariamente coincide con un IDen la estructura. Por lo tanto, podrían ser varios árboles que emergen de estos objetos.

¿Cómo procesarías estos objetos para crear los árboles resultantes?

No estoy tan lejos de una solución, pero estoy seguro de que está lejos de ser óptima ...

Necesito crear estos árboles para luego insertar datos en una base de datos, en el orden correcto.

No hay referencias circulares. Un nodo es un nodo raíz cuando ParentID == nulo o cuando ParentID no se puede encontrar en los otros objetos

Costo
fuente
¿Qué quieres decir con "crear"? Renderizar en una interfaz de usuario? ¿Almacenar de forma jerárquica en XML o en una base de datos?
RedFilter
¿Cómo define un nodo sin padre (es decir, un nodo raíz)? ParentID es nulo? ParentID = 0? Supongo que no hay referencias circulares ¿correcto?
Jason Punyon
55
Esta pregunta me parece bastante genial.
nes1983
1
mira
ebram khalil

Respuestas:

120

Almacenar ID de los objetos en una tabla hash que se asigna al objeto específico. Enumere todos los objetos y encuentre su padre si existe y actualice su puntero padre en consecuencia.

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
fuente
55
que idioma es ese (Lo tomo C #)
Jason S
3
Este algo es (en notación informal) O (3N), donde como una solución O (1N) se puede lograr fácilmente ya sea creando instancias de Nodos parciales para padres no 'atravesados' O manteniendo una tabla de búsqueda secundaria para hijos de niños no instanciados padres Probablemente no importa para la mayoría de los usos del mundo real, pero podría ser significativo en grandes conjuntos de datos.
Andrew Hanlon
15
@AndrewHanlon tal vez deberías publicar el sol por 0 (1N)
Ced
1
La respuesta de @Ced Martin Schmidt a continuación está muy cerca de cómo la implementaría. Como se puede ver, utiliza un solo bucle y el resto son operaciones de tabla hash.
Andrew Hanlon
26
O (3N) es solo O (N);)
JakeWilson801
34

Basado en la respuesta de Mehrdad Afshari y el comentario de Andrew Hanlon para una aceleración, aquí está mi opinión.

Diferencia importante con respecto a la tarea original: un nodo raíz tiene ID == 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
fuente
1
Bien, este es básicamente el enfoque al que me refería. Sin embargo, solo usaría un pseudo nodo raíz (con ID = 0 y nulo Parent) y eliminaría el requisito de auto referencia.
Andrew Hanlon
Lo único que falta en este ejemplo es asignar el campo Principal en cada nodo secundario. Para hacerlo, solo necesitamos establecer el campo Principal después de agregar los elementos secundarios a su Colección principal. Así: parentNode.Children.Add (ourNode); ourNode.Parent = parentNode;
plauriola
@plauriola Cierto, gracias, agregué esto. Una alternativa sería simplemente eliminar la propiedad Parent, no es necesaria para el algoritmo central.
Martin Schmidt
44
Como no pude encontrar un módulo npm que implemente una solución O (n), creé el siguiente (unidad probada, 100% de cobertura de código, solo 0.5 kb de tamaño e incluye tipings. Quizás ayude a alguien: npmjs.com/package / performant-array-to-tree
Philip Stanislaus
32

Aquí hay un algoritmo JavaScript simple para analizar una tabla plana en una estructura de árbol padre / hijo que se ejecuta en tiempo 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
fuente
tratando de convertir este enfoque a C #.
hakan
se dio cuenta de que si identificación comienza a partir de algo grande como 1.001 A continuación, obtener el índice de excepción límite ...
Hakan
2
Consejo: utilícelo console.log(JSON.stringify(root, null, 2));para imprimir bastante la salida.
aloisdg se muda a codidact.com el
14

Solución Python

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

Por ejemplo:

# (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)

Produce:

{
    "1": {
        "4": {
            "10": {}, 
            "11": {
                "16": {}, 
                "17": {
                    "24": {}, 
                    "25": {}
                }
            }
        }, 
        "5": {
            "8": {}, 
            "9": {
                "20": {}, 
                "12": {
                    "22": {}, 
                    "23": {
                        "2": {}, 
                        "27": {}, 
                        "26": {}
                    }
                }, 
                "21": {}, 
                "7": {}
            }
        }
    }
}
minkwe
fuente
Hola. ¿Cómo agrego otro atributo en la salida? es decir. name, parent_id
chico simple
De lejos, el más elegante!
ccpizza
@simpleguy: la comprensión de la lista se puede desplegar en caso de que necesite más control, por ejemplo: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

Versión JS que devuelve una raíz o una matriz de raíces, cada una de las cuales tendrá una propiedad de matriz Children que contiene los hijos relacionados. No depende de la entrada ordenada, decentemente compacta y no utiliza recursividad. ¡Disfrutar!

// 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
fuente
2
Esta pregunta tiene 7 años y ya tiene una respuesta votada y aceptada. Si cree que tiene una mejor solución, sería genial agregar alguna explicación a su código.
Jordi Nebot
Este enfoque funciona bien para este tipo de datos desordenado.
Cody C
4

Encontré una increíble versión de JavaScript aquí: http://oskarhane.com/create-a-nested-array-recursively-in-javascript/

Digamos que tiene una matriz como esta:

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

Y quieres tener los objetos anidados así:

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

Aquí hay una función recursiva que lo hace posible.

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

Usuage:

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
fuente
Para cada parentId, se está reproduciendo todo el modelo: ¿no es esto O (N ^ 2)?
Ed Randall el
4

Para cualquier persona interesada en una versión C # de la solución de Eugene, tenga en cuenta que se accede a node_list como un mapa, así que use un Diccionario en su lugar.

Tenga en cuenta que esta solución solo funciona si la tabla está ordenada por 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]);
}

El nodo se define de la siguiente manera.

class Node
{
    public int id { get; set; }
    public int parent_id { get; set; }
    public List<Node> children = new List<Node>();
}
Joel Malone
fuente
1
Es demasiado viejo, pero el elemento de lista 8 new Node { parent_id = 7, id = 9 },impide que node_list.Add(item.id, item);se complete debido llave no se puede repetir; es un error tipográfico; entonces, en lugar de id = 9 , escriba id = 8
Marcelo Scofano
Fijo. Gracias @MarceloScofano!
Joel Malone
3

Escribí una solución genérica en C # libremente basada en la respuesta de @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
fuente
Abajo votante, por favor comente. Me alegrará saber lo que hice mal.
HuBeZa
2

Aquí está la solución Java de la respuesta de Mehrdad Afshari.

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
fuente
Deberías explicar un poco cuál es tu idea detrás del código.
Ziad Akiki
Es solo la traducción de Java de la respuesta anterior
Vimal Bhatt
1

Aunque la pregunta me parezca vaga, probablemente crearía un mapa desde la ID hasta el objeto real. En pseudo-java (no comprobé si funciona / compila), podría ser algo como:

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

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

Y para buscar a cada padre:

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

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

Al reutilizar getRealObject(ID)y hacer un mapa de un objeto a una colección de objetos (o sus ID), también obtienes un mapa padre-> hijos.

Henrik Paul
fuente
1

Puedo hacer esto en 4 líneas de código y tiempo O (n log n), suponiendo que Dictionary sea algo así como un 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.

EDITAR : Ok, y ahora leí que algunos ID de padres son falsos, así que olvídate de lo anterior y haz esto:

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
fuente
1

La mayoría de las respuestas asumen que está buscando hacer esto fuera de la base de datos. Si sus árboles son de naturaleza relativamente estática y solo necesita mapear de alguna manera los árboles en la base de datos, puede considerar el uso de representaciones de conjuntos anidados en el lado de la base de datos. Echa un vistazo a los libros de Joe Celko (o aquí para obtener una descripción general de Celko).

Si está vinculado a Oracle dbs de todos modos, consulte su CONNECT BY para obtener enfoques SQL directos.

Con cualquier enfoque, puede omitir completamente la asignación de los árboles antes de cargar los datos en la base de datos. Solo pensé que ofrecería esto como una alternativa, puede ser completamente inapropiado para sus necesidades específicas. ¿La parte del "orden correcto" de la pregunta original implica que necesita que el orden sea "correcto" en la base de datos por alguna razón? Esto podría empujarme a manejar los árboles allí también.


fuente
1

No es exactamente lo que buscaba el autor de la pregunta, pero tuve dificultades para comprender las respuestas ambiguas que se proporcionan aquí, y todavía creo que esta respuesta encaja en el título.

Mi respuesta es para mapear una estructura plana a un árbol directamente en el objeto donde todo lo que tienes es un ParentIDen cada objeto. ParentIDes nullo 0si es una raíz. Frente al autor de la pregunta, supongo que todos ParentIDlos puntos válidos apuntan a algo más en la lista:

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;
Aske B.
fuente
1

Aquí hay una implementación de ruby:

Se catalogará por nombre de atributo o el resultado de una llamada al método.

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
fuente
1

La respuesta aceptada me parece demasiado compleja, así que agrego una versión de Ruby y NodeJS.

Suponga que la lista de nodos planos tiene la siguiente estructura:

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

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

Las funciones que convertirán la estructura de lista plana anterior en un árbol se ven de la siguiente manera

para Ruby:

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

para 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
fuente
Creo que el cheque nulldebe ser paraundefined
Ullauri
@Ullauri null == undefined => trueen NodeJS
Hirurg103
1

Una forma elegante de hacer esto es representar los elementos de la lista como una cadena que contiene una lista de padres separada por puntos, y finalmente un valor:

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

Al armar un árbol, terminarías con algo como:

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

Tengo una biblioteca de configuración que implementa esta configuración de anulación (árbol) a partir de argumentos de la línea de comandos (lista). El algoritmo para agregar un solo elemento a la lista a un árbol está aquí .

Omry Yadan
fuente
0

¿Estás atrapado usando solo esos atributos? De lo contrario, podría ser bueno crear una matriz de nodos secundarios, donde puede recorrer todos estos objetos una vez para construir tales atributos. A partir de ahí, seleccione el nodo con hijos pero sin padres y construya iterativamente su árbol de arriba hacia abajo.

Robert Elwell
fuente
0

versión 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
fuente