Вопросы Теги

Восстановите дерево по его порядку и предзаказу

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, которые являются моими новыми корнями, и повторить предыдущий процесс отделения их от левого и правого. пока я не перестрою дерево, как я могу продолжить работу с моим кодом? Я знаю, что он должен быть рекурсивным, но я не знаю, как его реализовать.

1
задан 26.11.2019, 03:49
1 ответ

не, если договоренности довольно аккуратные, следовательно я буду объяснять тебе мое решение используя: introducir la descripción de la imagen aquí

В этом случае поездки - следующие:

  1. Последовательность поездки предкоманды: F, B, A, D, C, E, G, I, H (raГ-z, левая сторона, правая сторона)

  2. Последовательность поездки некоманды: В, 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 -> []

Надеялся помочь тебе!

1
ответ дан 01.12.2019, 10:48

Теги

Похожие вопросы