resueltos - programacion orientada a objetos python ejemplos pdf

Recursivamente creando una jerarquía de árbol sin usar clase/objeto

Question

Tengo problemas para crear una jerarquía de árbol en Python 3. Me gustaría poder hacer esto sin usar clases.

Los datos con los que necesito comenzar no están en orden y en el formato [''ID'',''Parent''] :

data=[[''E1'', ''C1''],[''C1'', ''P1''],[''P1'', ''R1''],[''E2'', ''C2''],[''C2'', ''P2''],[''P2'', ''R1''],[''C3'', ''P2''],[''E3'', ''C4''],[''C4'', ''P3''],
  [''P3'', ''R2''],[''C5'', ''P3''],[''E4'', ''C6''],[''C6'', ''P4''], [''P4'', ''R2''],[''E5'', ''C7''],[''C7'', ''P5''],[''P5'', ''R3''],[''E6'', ''C9''],[''C9'', ''P6''],[''P6'', ''R3''],
  [''C8'', ''P6''],[''E7'', ''C10''],[''C10'', ''P7''],[''P7'', ''R4''],[''C11'', ''P7''],[''E8'', ''C12''],[''C12'', ''P8''],[''P8'', ''R4'']]

Quiero crear la variable del diccionario (Árbol) sin el uso de clases y terminar con algo como:

Tree={''R1'':{''P1'':{},''P2'':{}},''R2'':{}} etc

O

Tree={''R1'':[{''P1'':[],''P2'':[]}],''R2'':[]} etc

Obviamente, R1 y R2 tienen más hijos que eso, pero tal vez esa sea la estructura del Árbol.

Answer 1

Simplemente puede iterar sobre cada child , tupla parent , crear diccionario que asigne los identificadores del hijo y el padre a una lista que contenga los elementos secundarios de estos elementos. Seguimos haciendo esto hasta que hayamos terminado.

roots = set()
mapping = {}
for child,parent in data:
    childitem = mapping.get(child,None)
    if childitem is None:
        childitem =  {}
        mapping[child] = childitem
    else:
        roots.discard(child)
    parentitem = mapping.get(parent,None)
    if parentitem is None:
        mapping[parent] = {child:childitem}
        roots.add(parent)
    else:
        parentitem[child] = childitem

Ahora que lo hemos hecho, roots es un conjunto de identificadores de las raíces de los árboles: por lo tanto, para cada uno de esos elementos, sabemos que no existe un id que sea uno de los padres. Para cada identificación en las roots , podemos simplemente obtener de la mapping y que es un diccionario de la estructura {''childid'':child} donde childid es la identificación (aquí una string ) y child es de nuevo un diccionario de esa forma.

Para que pueda imprimirlos como:

for root in roots:
    print(mapping[root])

Entonces en tu caso, el tree es:

tree = { id : mapping[id] for id in roots }

Para su muestra de data , genera:

>>> tree
{''R1'': {''P1'': {''C1'': {''E1'': {}}}, ''P2'': {''C2'': {''E2'': {}}, ''C3'': {}}}, ''R2'': {''P4'': {''C6'': {''E4'': {}}}, ''P3'': {''C5'': {}, ''C4'': {''E3'': {}}}}, ''R3'': {''P6'': {''C8'': {}, ''C9'': {''E6'': {}}}, ''P5'': {''C7'': {''E5'': {}}}}, ''R4'': {''P8'': {''C12'': {''E8'': {}}}, ''P7'': {''C11'': {}, ''C10'': {''E7'': {}}}}}