Wysokość drzewa binarnego to odległość od węzła głównego do potomka węzła, który jest najdalej od korzenia.
Poniżej znajduje się przykład:
2 <-- root: Height 1
/ \
7 5 <-- Height 2
/ \ \
2 6 9 <-- Height 3
/ \ /
5 11 4 <-- Height 4
Wysokość drzewa binarnego: 4
Definicja drzewa binarnego
Drzewo to obiekt zawierający podpisaną wartość całkowitą i albo dwa inne drzewa, albo wskaźniki do nich.
Struktura binarnego drzewa struktury wygląda mniej więcej tak:
typedef struct tree
{
struct tree * l;
struct tree * r;
int v;
} tree;
Wyzwanie:
Wejście
Korzeń drzewa binarnego
Wynik
Liczba reprezentująca wysokość drzewa binarnego
Zakładając, że jako dane wejściowe podano katalog główny drzewa binarnego, napisz najkrótszy program, który oblicza wysokość drzewa binarnego i zwraca wysokość. Wygrywa program z najmniejszą liczbą bajtów (białe znaki rozliczeniowe).
code-golf
binary-tree
T. Salim
źródło
źródło
h
. Być może lepiej zdefiniować konkretną strukturę złożoną z samych list do celów tego wyzwania.[root_value, left_node, right_node]
gdzie każdyleft_node
iright_node
są również drzewo binarne do zaakceptowania? W wielu językach będzie to trywialne, ale w innych może być zabawne.a tree is an object that contains a value and either two other trees or pointers to them
. Przydałaby się również definicja obejmująca języki bez obiektów.Odpowiedzi:
Galaretka , 3 bajty
Monadycznego link przyjmując listę reprezentujący drzewa:
[root_value, left_tree, right_tree]
, gdzie każdyleft_tree
iright_tree
są podobne struktury (pusty w razie potrzeby), co daje wzrost.Wypróbuj online!
W jaki sposób?
Całkiem trywialne w Galaretce:
źródło
x
zamiast[x, [], []]
...Python 2 ,
3533 bajtówDziękujemy Arnauldowi za zauważenie niedopatrzenia i oszczędność 4.
Funkcji rekurencyjnej przyjmując listę reprezentujący drzewa:
[root_value, left_tree, right_tree]
, gdzie każdyleft_tree
iright_tree
są podobne struktury (pusty w razie potrzeby), która zwraca wysokość.Wypróbuj online!
Zauważ, że
[]
powróciFalse
, ale w PythonieFalse==0
.źródło
Haskell, 33 bajty
Używanie niestandardowego typu drzewa
data T = L | N T T Int
, który jest odpowiednikiem struktury C Haskell podanej w wyzwaniu.Wypróbuj online!
źródło
Perl 6 , 25 bajtów
Dane wejściowe to lista 3-elementowa
(l, r, v)
. Puste drzewo to pusta lista.Wypróbuj online!
Wyjaśnienie
Stare rozwiązanie, 30 bajtów
Wypróbuj online!
źródło
&?BLOCK
Sztuką jest interesujący, ale jest to kilka bajtów krótszy przypisać blok $!$!
lub$/
dla mnie jest oszustwem.05AB1E ,
1175 bajtów-4 bajty dzięki @ExpiredData .
-2 bajty dzięki @Grimy .
Format wejściowy jest podobny jako odpowiedź Jelly: wykaz reprezentujący drzewa:
[root_value, left_tree, right_tree]
, gdzie każdyleft_tree
iright_tree
są podobne struktury (opcjonalnie pusty). To znaczy[2,[7,[2,[],[]],[6,[5,[],[]],[11,[],[]]]],[5,[],[9,[4,[],[]],[]]]]
Reprezentuje drzewo z opisu wyzwania.Wypróbuj online lub sprawdź kilka innych przypadków testowych .
Wyjaśnienie:
Zauważ, że chociaż 05AB1E jest oparty na 0, pętla zmian
Δ
powoduje, że indeks wyjściowy jest poprawny, ponieważ wymaga dodatkowej iteracji, aby sprawdzić, czy już się nie zmienia.źródło
JavaScript (ES6),
3533 bajtówStruktura wejściowa:
[[left_node], [right_node], value]
Wypróbuj online!
Skomentował
źródło
a&&-~
.C, 43 bajty
Struktura drzewa binarnego jest następująca:
źródło
JavaScript (Node.js) , 32 bajty
Wypróbuj online!
Używanie nazwyflat
zamiastflatten
lubsmoosh
to świetny pomysł na golfa kodowego.Używanie
[]
węzła zerowego w drzewie i[left, right, value]
węzłów.value
tutaj jest liczba całkowita.źródło
Wolfram Language (Mathematica) , 10 bajtów
Wypróbuj online! Pobiera dane wejściowe jako zagnieżdżoną listę
{v, l, r}
.źródło
2[7[2,6[5,11]],5[9[4,],]]
jest to prawidłowa reprezentacja drzewa,Depth
działaHaskell, 28 bajtów
Korzystanie z następującej definicji danych:
Wysokość wynosi:
źródło
Schemat, 72 bajty
Bardziej czytelna wersja:
Korzystanie z list formularza (dane, lewy, prawy) do reprezentowania drzewa. Na przykład
Wypróbuj online!
źródło
R , 51 bajtów
Wypróbuj online!
Dane wejściowe: lista zagnieżdżona w formacie:
list(ROOT_ELEMENT, LEFT_TREE, RIGHT_TREE)
Algorytm: Iteracyjnie spłaszcza drzewo o jeden poziom, aż stanie się płaskim wektorem: liczba iteracji odpowiada maksymalnej głębokości.
Zainspirowany rozwiązaniem @KevinCruijssen
Rekurencyjna alternatywa:
R , 64 bajty
Wypróbuj online!
Przedefiniowuje funkcję / operatora,
'~'
dzięki czemu jest w stanie obliczyć maksymalną głębokość drzewa przechowywanego w strukturze listy.Struktura listy drzewa ma format:
list(ROOT_ELEMENT, LEFT_TREE, RIGHT_TREE)
źródło
d=1
a potemd-1
na końcu? Nie możesz zacząć od0
?>
się~
tutaj, aby łatwiej było wprowadzić przypadki testoweJapt , 8 bajtów
Spróbuj
Oryginał, 9 bajtów
Spróbuj
źródło
K (ngn / k) , 4 bajty
Rozwiązanie:
Wypróbuj online!
Wyjaśnienie:
Myślę, że mogłem nie zauważyć sedna.
Przykład reprezentujący drzewo jako listę 3-elementową (węzeł nadrzędny; lewy podrzędny; prawy podrzędny), przykład można przedstawić jako
lub:
(2;(7;(,2);(6;(,5);(,11)));(5;();(9;(,4);())))
.Rozwiązaniem jest iteracyjne spłaszczenie i policzenie iteracji:
źródło
Węgiel drzewny , 29 bajtów
Wypróbuj online! Link jest do pełnej wersji kodu. Tymczasowo modyfikuje drzewo podczas przetwarzania. Wyjaśnienie:
Wciśnij zero do węzła głównego.
Wciśnij węzeł główny na listę wszystkich węzłów.
Wykonaj pierwsze wyszukiwanie drzewa.
Uzyskaj głębokość tego węzła.
Pętla nad dowolnymi węzłami potomnymi.
Poinformuj węzeł potomny o jego głębokości nadrzędnej i pchnij go na listę wszystkich węzłów.
Po przejściu wszystkich węzłów wydrukuj głębokość ostatniego węzła. Ponieważ przejście było pierwsze, będzie to wysokość drzewa.
źródło
Stax , 5 bajtów
Uruchom i debuguj
Stax nie ma wskaźników ani wartości zerowych, więc reprezentuję dane wejściowe jak
[2,[7,[2,[],[]],[6,[5,[],[]],[11,[],[]]]],[5,[],[9,[4,[],[]],[]]]]
. Może to niesprawiedliwa przewaga, ale to było najbliższe, jakie mogłem uzyskać.Kod po rozpakowaniu, niepolowaniu i komentowaniu wygląda tak.
Uruchom ten
źródło
Kotlin, 45 bajtów
Zakładając, że zdefiniowano następującą klasę
Wypróbuj online
źródło
Julia, 27 bajtów
Z następującą strukturą reprezentującą drzewo binarne:
c
to krotka reprezentująca lewy i prawy węzeł, a pusta krotka()
służy do sygnalizowania braku węzła.źródło
Kotlin , 42 bajty
Wypróbuj online!
Gdzie
źródło