Wymień drzewa binarne

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).

Haskell, 68 bajtów

t 0=[""]
t 1=["0"]
t n=['(':x++y++")"|k<-[1..n-1],x<-t k,y<-t$n-k-1]

Węzły końcowe są reprezentowane przez 0, jednoargumentowe i binarne, przez (e)odpowiednio. (ee), więc dwa trzy-węzłowe drzewa podano jako (00)i ((0)).

Przykłady:

*Main> t 5
["(0(00))","(0((0)))","((0)(0))","((00)0)","(((0))0)","((0(0)))","(((0)0))","(((00)))","((((0))))"]
*Main> length $ t 8
127
*Main> length $ t 15
113634 

CJam (37 bajtów)

0aa{_2m*2\f+1Y$f+++:e__&}qi:A*{,A=},p

Demo online . Pamiętaj, że nie jest to zbyt wydajne i prawdopodobnie nie chcesz próbować obliczać nakładów 5online.

Wycięcie do naśladowania.

Pyth ( 24 21 19 bajtów)

Jest to oparte na moim rozwiązaniu Python 3 .

f!|sTf<sY0._T^}1_1t

Po raz pierwszy używam Pytha, więc prawdopodobnie nadal można grać w golfa.

Przykład danych wyjściowych, gdy dane wejściowe to 4:

[[1, 0, -1], [1, -1, 0], [0, 1, -1], [0, 0, 0]]

1 oznacza węzeł binarny, 0 oznacza węzeł jednoargumentowy, a -1 oznacza węzeł końcowy. Na końcu każdego drzewa znajduje się domniemany węzeł końcowy.

Objaśnienie :

f!|sTf<sY0._T^}1_1t
f                    filter
             ^    t  length n-1 lists of elements
              }1_1   from [1, 0, -1]
 !|                  for when both
   sT                sum of list is 0, and
     f    ._T        for each prefix of list,
      <sY0           sum of prefix is non-negative.

pieprzenie mózgu, 107 bajtów

,>++>-[-[<-[<-[>>[[>+<-]<]>+>[[<+>>>>>+<<<<-]>]>>++>,++++>]>[<+>-[+>>]>[<->[.<<<
<<]+[->+]+>>>]]]]<[[,<]<]<]

Sformatowany:

,>++>-
[
  -
  [
    <-
    [
      <-
      [
        >>
        [[>+<-]<]
        >+>
        [[<+> >>>>+<<<<-]>]
        >>++>,++++>
      ]
      >
      [
        <+>-
        [
          +>>
        ]
        >
        [
          <->[.<<<<<]
          +[->+]
          +>>>
        ]
      ]
    ]
  ]
  <
  [
    [,<]
    <
  ]
  <
]

Wypróbuj online

Dane wejściowe są traktowane jako bajt , a drzewo 12100jest reprezentowane jako\x01\x02\x03\x02 : do konwersji z powrotem, tłumaczenia tr/\x01\x02\x03/012/, odwrócenia łańcucha i dodania końcowego 0. Drzewa są oddzielone \xfe. (Dane wyjściowe można łatwiej odczytać, np. Zmieniając pierwszy -na -36i .na +47.-47, gdzie -36oznacza ciąg 36 -znaków itp.)

Podejście to wykorzystuje właściwość (której również użył Ben Frankel): biorąc pod uwagę możliwe węzły jako -1, 0, 1i ignorując -1węzeł końcowy , lista reprezentuje prawidłowe drzewo wtedy i tylko wtedy, gdy (1) wszystkie prefiksy listy mają nieujemną sumę, oraz (2) suma całej listy jest równa 0. Pierwszy warunek jest utrzymywany podczas generowania węzłów pośrednich, więc na końcu należy sprawdzić tylko drugi warunek.

Taśma jest podzielona na 5-węzłowe komórki,

i d x 0 0

gdzie ijest indeks (malejący od lewej do prawej), djest sumą częściową i xjest elementem.

Szkic przepływu kontrolnego:

take n and push initial node
while stack is non-empty:
    if rightmost node can be decremented:
        decrement rightmost node
        if there are less than n nodes:
            push new node
        else if valid tree:
            print
    else:
        backtrack (pop)

Zauważ, że czasami wartość jest przechowywana lub inicjowana jako jedna lub dwie większe niż rzeczywista (konceptualna) wartość i dostosowywana w razie potrzeby.

Python 3 ( 138 134 128 121 119 bajtów)

from itertools import*
lambda n:[any(sum(t[:k])<0for k in range(n))|sum(t)or print(t)for t in product(*[[-1,0,1]]*~-n)]

Przykładowe dane wyjściowe dla n=5:

(0, 0, 0, 0)
(0, 0, 1, -1)
(0, 1, -1, 0)
(0, 1, 0, -1)
(1, -1, 0, 0)
(1, -1, 1, -1)
(1, 0, -1, 0)
(1, 0, 0, -1)
(1, 1, -1, -1)

1 oznacza węzeł binarny, 0 oznacza węzeł jednoargumentowy, a -1 oznacza węzeł końcowy. Na końcu każdego drzewa znajduje się domniemany węzeł końcowy.

Program zaczyna zajmować zbyt dużo czasu n=17.

JavaScript (Firefox 30-57), 79 bajtów

f=(m,l=0)=>m?[for(n of[1,0,-1])if(l>n&l<=m+n)for(a of f(m-1,l-n))[...a,n]]:[[]]

Gdzie -1reprezentuje terminal, 0jednoargumentowy i 1dwójkowy. Zaczyna się powoli przym=14Na moim komputerze . Rekurencyjnie działa od końca drzewa.

• Liczba niezliczonych węzłów l jest ograniczona faktem, że na końcu może pozostać tylko 1 węzeł.
• Rodzaj następnego węzła njest ograniczony potrzebą wystarczającej liczby węzłów niezliczonych, aby mogły być jego potomkami.

Prolog, 149 144 138 137 131 131 107 bajtów

e(L,L)-->[0].

e([_|A],L)--> 
    [1],
    e(A,L).

e([_,_|A],L)--> 
    [2],
    e(A,B), 
    e(B,L).

e(M,E):-                   
    length([_|L],M),        
    e(L,[],E,[]).           

?- e(5,S).
S = [1, 1, 1, 1, 0] ;
S = [1, 1, 2, 0, 0] ;
S = [1, 2, 0, 1, 0] ;
S = [1, 2, 1, 0, 0] ;
S = [2, 0, 1, 1, 0] ;
S = [2, 0, 2, 0, 0] ;
S = [2, 1, 0, 1, 0] ;
S = [2, 1, 1, 0, 0] ;
S = [2, 2, 0, 0, 0].

I policzyć rozwiązania

e_count(N,Count) :-
    length([_|Ls], N),
    findall(., phrase(e(Ls,[]),E), Sols),
    length(Sols, Count).

?- e_count(N,Count).
N = Count, Count = 1 ;
N = 2, Count = 1 ;
N = 3, Count = 2 ;
N = Count, Count = 4 ;
N = 5, Count = 9 ;
N = 6, Count = 21 ;
N = 7, Count = 51 ;
N = 8, Count = 127 ;
N = 9, Count = 323 ;
N = 10, Count = 835 ;
N = 11, Count = 2188 ;
N = 12, Count = 5798 ;
N = 13, Count = 15511 ;
N = 14, Count = 41835 ;
N = 15, Count = 113634 

Python, 71 bajtów

f=lambda n:{(a+b,)for k in range(n)for a in f(k)for b in f(n+~k)}or[()]

Reprezentuje drzewa jako zagnieżdżone krotki, takie jak ((((),), ()),), na które można przekształcić ((())()), usuwając przecinki, spacje i najbardziej zewnętrzne ().

Wcześniejsza 76-bajtowa wersja:

f=lambda n:{'('+a+b+')'for k in range(n)for a in f(k)for b in f(n+~k)}or['']

CJam, 38 bajtów

Stosuje inne podejście, na które odpowiada CJam Petera Taylora.

3rim*{:(1\+[{1$+}*])\:(_:z#|!},

Wynik będzie podobny 1110120020102100. Każde drzewo jest grupąn cyfr (gdzien jest liczbą wejściową).

Podstawowym założeniem jest to, że możemy wygenerować wszystkie możliwe ciąg cyfr 0, 1i 2, a następnie filtrować tylko te, które są dobrze ukształtowane drzewa.