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)
Я должен восстановить дерево с его порядком и порядком, когда использую эту функцию, я беру корень, который является h, и делю то, что осталось на левой стороне дерева, оставаясь таким образом
H
F, B, G, A, C - N, M, D
в списке порядка в списке предварительного заказа. Я бы оставался от до , b, f, g - m , n, d, из которых я должен взять aym, которые являются моими новыми корнями, и повторить предыдущий процесс отделения их от левого и правого. пока я не перестрою дерево, как я могу продолжить работу с моим кодом? Я знаю, что он должен быть рекурсивным, но я не знаю, как его реализовать.
не, если договоренности довольно аккуратные, следовательно я буду объяснять тебе мое решение используя:
В этом случае поездки - следующие:
Последовательность поездки предкоманды: F, B, A, D, C, E, G, I, H (raГ-z, левая сторона, правая сторона)
Последовательность поездки некоманды: В, B, C, D, E, F, G, H, I (левая сторона, raГ-z, правая сторона); заметьте cГіmo это производит аккуратную последовательность
Твой код эта хорошо, проблема состоит в том, что, если ты хочешь выбрать всегда корень элемент P[0]
, ты должен изменять эту договоренность в каждом так называемом переиталике, в моем случае после первого выполнения у нас есть следующие договоренности:
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])
Следовательно в следующем перекурсивном вызове, P
должен брать стоимость, которые есть между B (чтобы игнорировать F) до E, такой мы убеждаемся, что P[0]
был корень в каждом так называемом переиталике. Во втором вызове P
будь должен брать стоимость с G до H. Я присоединяю код для того, чтобы осталось более ясным и вывод, что я получил:
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)
Это был вывод, который я получил:
['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 -> []
И с твоими данными:
['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 -> []
Надеялся помочь тебе!