Które kombinacje sekwencjonowania przed, po i w kolejności są wyjątkowe?

Znamy się na zamówieniu,

post L(x)     => [x]
post N(x,l,r) => (post l) ++ (post r) ++ [x]

i w przedsprzedaży

pre L(x)     => [x]
pre N(x,l,r) => [x] ++ (pre l) ++ (pre r)

oraz w kolejności przechodzenia lub. sekwencjonowanie.

in L(x)     => [x]
in N(x,l,r) => (in l) ++ [x] ++ (in r)

Łatwo zauważyć, że żadne z nich nie opisuje jednoznacznie danego drzewa, nawet jeśli przyjmiemy odrębne pary kluczy / etykiet.

Których kombinacji tych trzech można użyć do tego celu, a które nie?

Pozytywne odpowiedzi powinny obejmować (wydajny) algorytm do rekonstrukcji drzewa oraz dowód (pomysł), dlaczego jest on poprawny. Negatywne odpowiedzi powinny dawać kontrprzykłady, tj. Różne drzewa, które mają tę samą reprezentację.

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ć 1u podstawy, ale 2moż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.$[x_1,\dots,x_n]$$[y_n,\ldots,y_1]$$x_1=y_1$
• $x_2$ 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.$y_2$$x_2 = y_2$$[x_2,\ldots,x_n]$$[y_n,\ldots,y_2]$
• 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.$i$$j$$x_2 = y_i$$y_2 = x_j$$[x_2,\ldots,x_{j-1}]$$[x_j,\ldots,x_n]$$j-2=n-i+1$$i-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(n^2)$$\Theta(n^2)$$O(n\,\mathrm{lg}(n))$$n\,\mathrm{lg}(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:$[x_1,\ldots,x_n]$$[z_1,\ldots,z_n]$

• Rdzeń jest głową przejścia w przedsprzedaży .$x_1$
• 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.$k$$z_k = x_1$$[z_1,\ldots,z_{k-1}]$$[z_{k+1},\ldots,z_n]$$[x_2,\ldots,x_k]$$[x_{k+1},\ldots,x_n]$

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(n^2)$$O(n\,\mathrm{lg}(n))$

Zamówienie po zamówieniu i zamówienie jest oczywiście symetryczne.