Drzewa binarne
Drzewo binarne to drzewo z węzłami trzech typów:
- węzły końcowe, które nie mają dzieci
- jednoargumentowe węzły, z których każde ma jedno dziecko
- węzły binarne, z których każde ma dwoje dzieci
Możemy je przedstawić za pomocą następującej gramatyki, podanej w BNF (forma Backus – Naur):
<e> ::=
<terminal>
| <unary>
| <binary>
<terminal> ::=
"0"
<unary> ::=
"(1" <e> ")"
<binary> ::=
"(2" <e> " " <e> ")"
W tej gramatyce węzły są podane w przedsprzedaży, a każdy węzeł jest reprezentowany przez cyfrę, która jest liczbą jego dzieci.
Liczby Motzkina
Liczby Motzkina ( OEIS ) ( Wikipedia ) mają wiele interpretacji, ale jedna interpretacja jest taka, że nliczba Motzkina to liczba różnych drzew dwójkowych z nwęzłami. Rozpocznie się tabela liczb Motzkina
N Motzkin number M(N)
1 1
2 1
3 2
4 4
5 9
6 21
7 51
8 127
...
np. M(5)ma 9, a dziewięć odrębnych drzew binarnych z 5 węzłami to
1 (1 (1 (1 (1 0))))
2 (1 (1 (2 0 0)))
3 (1 (2 0 (1 0)))
4 (1 (2 (1 0) 0))
5 (2 0 (1 (1 0)))
6 (2 0 (2 0 0))
7 (2 (1 0) (1 0))
8 (2 (1 (1 0)) 0)
9 (2 (2 0 0) 0)
Zadanie
Weź jedną dodatnią liczbę całkowitą njako dane wejściowe i wyjściowe wszystkich różnych drzew binarnych z nwęzłami.
Przykłady nod 1 do 5 z nawiasami włączonymi dla czytelności
0
(1 0)
(1 (1 0))
(2 0 0)
(1 (1 (1 0)))
(1 (2 0 0))
(2 0 (1 0))
(2 (1 0) 0)
(1 (1 (1 (1 0))))
(1 (1 (2 0 0)))
(1 (2 0 (1 0)))
(1 (2 (1 0) 0))
(2 0 (1 (1 0)))
(2 0 (2 0 0))
(2 (1 0) (1 0))
(2 (1 (1 0)) 0)
(2 (2 0 0) 0)
Wejście
Dane wejściowe będą jedną dodatnią liczbą całkowitą.
Wynik
Dane wyjściowe powinny stanowić zrozumiałą reprezentację odrębnych drzew binarnych z tyloma węzłami. Nie jest obowiązkowe stosowanie dokładnego ciągu podanego powyżej przez gramatykę BNF: wystarczy, że zastosowana składnia da jednoznaczną reprezentację drzew. Na przykład można użyć []zamiast (), dodatkowy poziom nawiasach [[]]zamiast [], zewnętrznej nawiasach są obecne lub brakuje, dodatkowych przecinkami lub bez przecinków, dodatkowe spacje, nawiasy lub bez nawiasów, itp
Wszystkie są równoważne:
(1 (2 (1 0) 0))
[1 [2 [1 0] 0]]
1 2 1 0 0
12100
(1 [2 (1 0) 0])
.:.--
*%*55
(- (+ (- 1) 1))
-+-11
Również wariant przeznaczony przez @xnor w komentarzu. Ponieważ istnieje sposób na przetłumaczenie tego formatu na zrozumiały format, jest to dopuszczalne.
[[[]][]] is (2 (1 0) 0)
Aby to łatwiej zrozumieć niektóre z konwertować []do ()jak tak
[([])()]
Teraz, jeśli zaczniesz
[]
następnie wstaw plik binarny, który wymaga dwóch wyrażeń
[()()] which is 2
a następnie dla pierwszego () wstaw jednoargumentowy, który wymaga jednego wyrażenia, które otrzymasz
[([])()] which is 21
ale ponieważ brak nawiasu wewnętrznego []lub ()bez niego może reprezentować 0, które nie wymaga już żadnych wyrażeń, można je interpretować jako
2100
Zauważ, że odpowiedzi powinny teoretycznie działać z pamięcią nieskończoną, ale oczywiście zabraknie pamięci dla skończonego wejścia zależnego od implementacji.
Wariacje produkcji
BNF xnor Christian Ben
b(t, b(t, t)) [{}{{}{}}] (0(00)) (1, -1, 1, -1)
b(t, u(u(t))) [{}{(())}] (0((0))) (1, -1, 0, 0)
b(u(t), u(t)) [{()}{()}] ((0)(0)) (1, 0, -1, 0)
b(b(t, t), t) [{{}{}}{}] ((00)0) (1, 1, -1, -1)
b(u(u(t)), t) [{(())}{}] (((0))0) (1, 0, 0, -1)
u(b(t, u(t))) [({}{()})] ((0(0))) (0, 1, -1, 0)
u(b(u(t), t)) [({()}{})] (((0)0)) (0, 1, 0, -1)
u(u(b(t, t))) [(({}{}))] (((00))) (0, 0, 1, -1)
u(u(u(u(t)))) [(((())))] ((((0)))) (0, 0, 0, 0)
Możliwe miejsce, w którym można sprawdzić zduplikowane drzewa
Jednym miejscem do sprawdzenia duplikatu jest M (5).
To jedno drzewo zostało wygenerowane dwukrotnie dla M (5) z drzew M (4)
(2 (1 0) (1 0))
pierwszy, dodając jednoargumentowy oddział do
(2 (1 0) 0)
i po drugie, dodając jednoargumentową gałąź do
(2 0 (1 0))
Zrozumienie BNF
BNF składa się z prostych zasad:
<symbol> ::= expression
gdzie po lewej stronie znajduje się nazwa symbolu otoczona <>.
Po prawej stronie znajduje się wyrażenie do konstruowania symbolu. Niektóre reguły wykorzystują inne reguły w konstrukcji, np
<e> ::= <terminal>
e może być terminal
a niektóre reguły mają znaki, które są używane do konstruowania symbolu, np
<terminal> ::= "0"
terminal jest tylko znakiem zero.
Niektóre reguły mają wiele sposobów ich konstruowania, np
<e> ::=
<terminal>
| <unary>
| <binary>
eMoże być <terminal>albo <unary>albo <binary>.
A niektóre zasady są sekwencją części, np
<unary> ::= "(1" <e> ")"
unaryTo znaki (1obserwowani przez co może być skonstruowana dla enastępuje ).
Zawsze zaczynasz od reguły początkowej, która w tym celu <e>.
Kilka prostych przykładów:
Najprostsza sekwencja jest sprawiedliwa 0. Dlatego zaczynamy od reguły początkowej <e>i widzimy, że są trzy możliwości:
<terminal>
| <unary>
| <binary>
więc weź pierwszy <terminal>. Teraz terminal nie ma wyboru i jest 0. Więc zastąpić <terminal>ze 0w <e>reguły i gotowe.
Następnie jest następny (1 0). Zacznij od <e>i użyj reguły, <unary>która ma
"(1" <e> ")"
Teraz to potrzebuje, <e>więc wrócimy do <e>i dokonamy wyboru jednego z trzech, tym razem wybierając, <terminal>co daje 0. Zamieniając 0na (1 <e> )daje (1 0), a to jest zamieniane na <unary>tak <e>jest (1 0).