no se si los arreglos estan bien ordenados, por lo tanto voy a explicarte mi solucion usando:
En este caso los recorridos son los siguientes:
Secuencia de recorrido de preorden: F, B, A, D, C, E, G, I, H (raíz, izquierda, derecha)
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!