1
Preorden = ["h","a","b","f","g","c","m","n","d"]
Inorden = ["f","b","g","a","c","h","n","m","d"]

def PreordenReconstruccion(P,I):
 Izquierda=[]
 Derecha=[]
 x=0
 Raiz=P[0]
 while I[x] != Raiz:
    Izquierda.append(I[x])
    x=x+1
 Derecha=I[x+1:len(I)]
 print Izquierda
 print Derecha
PreordenReconstruccion(Preorden,Inorden)

tengo que reconstruir un arbol con su inorden y preorden al usar esa funcion cojo la raiz que es h y divido lo que queda en el lado izquierdo del arbol, asi quedandome

H

F,B,G,A,C - N,M,D

en la lista inorden en la lista de preorden me quedaria a,b,f,g - m,n,d de los cuales deberia tomar a y m que son mis nuevas raices y repetir el porceso anterior de separarlos de izquierda y derecha. hasta reconstruir el arbol, como puedo continuar con mi codigo soy conciente que debe ser recursivo pero no se como implementarlo.

1 respuesta 1

1

no se si los arreglos estan bien ordenados, por lo tanto voy a explicarte mi solucion usando: introducir la descripción de la imagen aquí

En este caso los recorridos son los siguientes:

  1. Secuencia de recorrido de preorden: F, B, A, D, C, E, G, I, H (raíz, izquierda, derecha)

  2. Secuencia de recorrido de inorden: A, B, C, D, E, F, G, H, I (izquierda, raíz, derecha); note cómo esto produce una secuencia ordenada

Tu codigo esta bien, el problema es que si quieres elegir siempre la raiz el elemento P[0], tienes que modificar este arreglo en cada llamada recursiva, en mi caso despues de la primera ejecucion tenemos los siguientes arreglos:

P = [F, B, A, D, C, E, G, I, H]
I = [A, B, C, D, E, F, G, H, I]

Raiz = F
Izquierda = [A, B, C, D, E]
Derecha = [G, H, I]

# Entonces las llamadas serian:

PreordenReconstruccion ([B,A,D,C,E], [A, B, C, D, E])
PreordenReconstruccion ([G,I,H], [G, H, I])

Por lo tanto en la siguiente llamada recursiva, P debe tomar los valores que hay entre B (para ignorar el F) hasta E, asi nos aseguramos que el P[0] sea la raiz en cada llamada recursiva. En la segunda llamada P debe tomar los valores desde G hasta H. Adjunto el codigo para que quede mas claro y la salida que obtuve:


Preorden = ["F", "B", "A", "D", "C", "E", "G", "I", "H"]
Inorden = ["A", "B", "C", "D", "E", "F", "G", "H", "I"]

def PreordenReconstruccion(P,I):
    if (len(I) == 0 or len(P) == 0):
        return
    else:
        Izquierda=[]
        Derecha=[]
        x=0
        Raiz=P[0]
        while I[x] != Raiz:
            Izquierda.append(I[x])
            x=x+1
        Derecha=I[x+1:len(I)]
        print (Izquierda , "<-", Raiz, "->", Derecha)

        PreordenReconstruccion(P[1:len(Izquierda)+1],Izquierda)
        PreordenReconstruccion(P[len(P)-len(Derecha):len(P)],Derecha)

PreordenReconstruccion(Preorden,Inorden)

Esta fue la salida que obtuve:

['A', 'B', 'C', 'D', 'E'] <- F -> ['G', 'H', 'I']
['A'] <- B -> ['C', 'D', 'E']
[] <- A -> []
['C'] <- D -> ['E']
[] <- C -> []
[] <- E -> []
[] <- G -> ['H', 'I']
['H'] <- I -> []
[] <- H -> []

Y con tus datos:

['f', 'b', 'g', 'a', 'c'] <- h -> ['n', 'm', 'd']
['f', 'b', 'g'] <- a -> ['c']
['f'] <- b -> ['g']
[] <- f -> []
[] <- g -> []
[] <- c -> []
['n'] <- m -> ['d']
[] <- n -> []
[] <- d -> []

Espero haberte ayudado!

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.