Najpierw założę, że wszystkie elementy są różne. Żadna ilość sekwencjonowania nie powie ci o kształcie drzewa z elementami [3,3,3,3,3]
. Oczywiście można zrekonstruować niektóre drzewa ze zduplikowanymi elementami; Nie wiem, jakie istnieją wystarczające warunki.
Kontynuując negatywne wyniki, nie można w pełni odbudować drzewa binarnego na podstawie samej sekwencjonowania przed i po zamówieniu. [1,2]
zamówienie przedpremierowe [2,1]
musi być 1
u podstawy, ale 2
może być lewym dzieckiem lub prawym dzieckiem. Jeśli nie obchodzi Cię ta dwuznaczność, możesz zrekonstruować drzewo za pomocą następującego algorytmu:
- Niech będzie przejściem przed zamówieniem, a będzie przejściem po zamówieniu. Musimy mieć , a to jest korzeń drzewa.[x1,…,xn][yn,…,y1]x1=y1
- x2 jest na lewo potomkiem katalogu głównego, a jest skrajnie na prawo dzieckiem. Jeśli , węzeł główny jest jednoargumentowy; przechodź przez i aby zbudować pojedyncze poddrzewo.y2x2=y2[x2,…,xn][yn,…,y2]
- W przeciwnym razie, niech i być wskaźniki takie, że i . to przejście w lewym poddrzewie w przedsprzedaży, w prawym poddrzewie i podobnie w przypadku przejścia po zamówieniu. Lewe poddrzewa ma elementy , a prawe poddrzewa ma elementy . Powtórz raz dla każdego poddrzewa.
Nawiasem mówiąc, ta metoda uogólnia na drzewa z dowolnym rozgałęzieniem. W przypadku dowolnego rozgałęzienia sprawdź zasięg lewego poddrzewa i odetnij jego elementy z obu list, a następnie powtórz, aby odciąć drugie poddrzewo od lewej i tak dalej.ijx2=yiy2=xj[x2,…,xj−1][xj,…,xn]j−2=n−i+1i−2=n−j+1
j−2
Jak wspomniano, czas działania wynosi z najgorszym przypadkiem (w przypadku dwojga dzieci przeszukujemy każdą listę liniowo). Możesz zmienić to w jeśli wstępnie przetworzysz listy, aby zbudować skończoną strukturę mapy od wartości elementów do pozycji na listach wejściowych . Użyj także tablicy lub mapy skończonej, aby przejść od indeksów do wartości; trzymaj się globalnych indeksów, aby rekursywne połączenia otrzymywały całe mapy i przyjmowały zasięg jako argument, aby wiedzieć, na czym należy działać.O(n2)Θ(n2)O(nlg(n))nlg(n)
Korzystając z przejścia w przedsprzedaży i przejścia w kolejności , możesz odbudować drzewo w następujący sposób:[x1,…,xn][z1,…,zn]
- Rdzeń jest głową przejścia w przedsprzedaży .x1
- Niech będzie indeksem takim, że . Zatem to przejście w kolejności lewego dziecka, a to przejście w kolejności prawego dziecka. Po liczbie elementów, jest przejściem w lewo lewego dziecka i tego prawego dziecka. Powtórz, aby zbudować lewe i prawe poddrzewa.kzk=x1[z1,…,zk−1][zk+1,…,zn][x2,…,xk][xk+1,…,xn]
Ponownie, tym algorytmem jest jak podano, i można go wykonać w jeśli lista jest wstępnie przetwarzana w skończoną mapę od wartości do pozycji.O(n2)O(nlg(n))
Zamówienie po zamówieniu i zamówienie jest oczywiście symetryczne.
2
jest to lewe, czy prawe dziecko. Odpowiada to przypadkowi „pojedynczego poddrzewa” algorytmu rekonstrukcji.