Napisz program, który pobiera drzewo binarne jako dane wejściowe i wyświetla najgłębszy węzeł i jego głębokość. W przypadku remisu wydrukuj wszystkie zaangażowane węzły oraz ich głębokości. Każdy węzeł jest reprezentowany jako:
T(x,x)
T(x)
T
gdzie T
jest identyfikatorem jednego lub więcej znaków alfanumerycznych, a każdy x
jest innym węzłem.
Oto prosta definicja drzewa binarnego:
- Na czele drzewa binarnego znajduje się węzeł.
- Węzeł w drzewie binarnym ma co najwyżej dwoje dzieci.
Na przykład dane wejściowe A(B(C,D(E)))
(poniżej) zostaną wypisane 3:E
.
Podczas gdy następujące drzewo jest trójdrożnym remisem między 5, 11 i 4, a ich głębokość wynosi również 3 (zaczynając od 0):
Dane wejściowe 2(7(2,6(5,11)),5(9(4)))
(poniżej) zostaną wygenerowane 3:5,11,4
.
To jest kod golfowy, więc wygrywa najkrótszy kod mierzony w bajtach.
code-golf
binary-tree
Jwosty
źródło
źródło
Odpowiedzi:
CJam,
4947źródło
Haskell, 186 bajtów
Pełny program, pobiera drzewo
stdin
, tworzy określony format wyjściowy nastdout
:Przewodnik po kodzie golfowym (dodano lepsze imiona, podpisy, komentarze i niektóre podwyrażenia wyciągnięte i nazwane - ale poza tym ten sam kod; wersja bez golfa nie połączyłaby się z włamaniem do węzłów z numeracją ani znalezieniem najgłębszego z formatowaniem wyjściowym.) :
źródło
GolfScript (75 znaków)
Niezbyt konkurencyjny, ale wystarczająco pokręcony, aby miał pewne zainteresowanie:
Kod ma trzy fazy. Najpierw wstępnie przetwarzamy ciąg wejściowy:
Mamy przekształcił np
A(B(C,D(E)))
do'A'^('B'^('C'^'D'^('E'^)''^)''^)
. Jeśli przypiszemy odpowiedni blok^
, możemy wykonać przydatne przetwarzanie, używając~
do ewaluacji łańcucha.Po drugie, znajdujemy maksymalną głębokość:
Na koniec wybieramy najgłębsze węzły i tworzymy dane wyjściowe:
źródło
Perl 5 - 85
Edytuj ten post, aby poprawić liczbę znaków. Używam
say
funkcji, ale nie wiem o flagach, aby działała poprawnie bez deklarowaniause 5.010;
.Demo na ideone
Dane wyjściowe są rozdzielone spacjami zamiast przecinków.
Kod używa po prostu rekursywnego wyrażenia regularnego do usuwania korzenia drzew w lesie, dopóki nie jest to możliwe. Następnie łańcuch przed ostatnim będzie zawierać wszystkie węzły liści na najgłębszym poziomie.
Przykładowe przebiegi
źródło
VB.net
Założenie: wartości węzłów nie mogą zawierać
,
,(
,)
źródło
JavaScript (E6) 120
Wersja iteracyjna
Nie golfowane i testowalne
Testuj w konsoli Firefox:
Wynik
źródło