Dada una lista de listas, escriba un programa en Python para convertir la lista de listas dada en un diccionario en forma de árbol.
Ejemplos:
Input : [[1], [2, 1], [3, 1], [4, 2, 1], [5, 2, 1], [6, 3, 1], [7, 3, 1]] Output : {1: {2: {4: {}, 5: {}}, 3: {6: {}, 7: {}}}} Input : [['A'], ['B', 'A'], ['C', 'A'], ['D', 'C', 'A']] Output : {'A': {'C': {'D': {}}, 'B': {}}}
Método #1: Método Naive
Este es un enfoque Naive en el que usamos dos bucles for para recorrer la lista de listas. Inicializamos el ‘árbol’ del diccionario vacío a currTree y cada vez verificamos si la clave (lista de elementos de la lista) está incluida en currTree o no. Si no, inclúyalo en currTree , de lo contrario no haga nada. Finalmente, asigne el currTree[key]
a currTree
.
# Python3 program to Convert a list # of lists into Dictionary (Tree form) def formTree(list): tree = {} for item in list: currTree = tree for key in item[::-1]: if key not in currTree: currTree[key] = {} currTree = currTree[key] return tree # Driver Code lst = [['A'], ['B', 'A'], ['C', 'A'], ['D', 'C', 'A']] print(formTree(lst))
{'A': {'B': {}, 'C': {'D': {}}}}
Método #2: Usar reduce()
La reduce()
función se usa para aplicar una función particular pasada en su argumento a todos los elementos de la lista mencionados en la secuencia pasada. Usaremos reduce()
para recorrer el diccionario y reutilizar getTree()
para encontrar la ubicación para almacenar el valor de setTree()
. Se necesita todo menos el último elemento en mapList para encontrar el diccionario ‘principal’ para agregar el valor, luego use el último elemento para establecer el valor en la clave correcta.
# Python3 program to Convert a list # of lists into Dictionary (Tree form) from functools import reduce from operator import getitem def getTree(tree, mappings): return reduce(getitem, mappings, tree) def setTree(tree, mappings): getTree(tree, mappings[:-1])[mappings[-1]] = dict() # Driver Code lst = [['A'], ['B', 'A'], ['C', 'A'], ['D', 'C', 'A']] tree ={} for item in lst: setTree(tree, item[::-1]) print(tree)
{'A': {'B': {}, 'C': {'D': {}}}}
Publicación traducida automáticamente
Artículo escrito por Smitha Dinesh Semwal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA