Napisz najkrótszy program do obliczania wysokości drzewa binarnego

18

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

T. Salim
źródło
4
Co robią języki bez wskaźników?
Jonathan Allan
4
... ale mój obiekt drzewa może mieć po prostu właściwość, powiedzmy h. Być może lepiej zdefiniować konkretną strukturę złożoną z samych list do celów tego wyzwania.
Jonathan Allan
11
@ T.Salim W przyszłości rozważ najpierw opublikowanie w piaskownicy .
wizzwizz4
1
Tak, to ważne reprezentacja lista długości 3 [root_value, left_node, right_node]gdzie każdy left_nodei right_nodesą również drzewo binarne do zaakceptowania? W wielu językach będzie to trywialne, ale w innych może być zabawne.
Jonathan Allan
3
Czy możesz edytować pytanie, aby uwzględnić to, co stanowi prawidłową strukturę binarną? Być może taka definicja 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.
Jo King

Odpowiedzi:

11

Galaretka , 3 bajty

ŒḊ’

Monadycznego link przyjmując listę reprezentujący drzewa: [root_value, left_tree, right_tree], gdzie każdy left_treei right_treesą podobne struktury (pusty w razie potrzeby), co daje wzrost.

Wypróbuj online!

W jaki sposób?

Całkiem trywialne w Galaretce:

ŒḊ’ - Link: list, as described above
ŒḊ  - depth
  ’ - decremented (since leaves are `[value, [], []]`)
Jonathan Allan
źródło
Jonathon Allen, to ciekawy język, którego używasz. Czy jako nowy użytkownik może podać link lub skierowanie strony internetowej, która będzie instruować ludzi, jak korzystać z Jelly?
T. Salim,
4
Kliknij link w nagłówku - jest to język golfa opracowany przez Dennisa , jednego z moderatorów strony.
Jonathan Allan
2
Zastanawiam się, jak kontrowersyjne byłoby przedstawianie liścia, xzamiast [x, [], []]...
Erik the Outgolfer
@EriktheOutgolfer Aby zachować charakter „wskaźnika” i „struktury” pytania, myślę, że każdy węzeł powinien mieć tę samą formę.
Jonathan Allan
10

Python 2 ,  35  33 bajtów

Dziękujemy Arnauldowi za zauważenie niedopatrzenia i oszczędność 4.

f=lambda a:a>[]and-~max(map(f,a))

Funkcji rekurencyjnej przyjmując listę reprezentujący drzewa: [root_value, left_tree, right_tree], gdzie każdy left_treei right_treesą podobne struktury (pusty w razie potrzeby), która zwraca wysokość.

Wypróbuj online!

Zauważ, że [] powróci False, ale w Pythonie False==0.

Jonathan Allan
źródło
Ta sama osoba może udzielić dwóch różnych odpowiedzi na to samo pytanie?
T. Salim
6
Tak, oczywiście golf jest konkurencją na poziomie językowym. Nawet drugi wpis w tym samym języku jest czasami akceptowalny, jeśli podejście jest zupełnie inne.
Jonathan Allan
@Arnauld Zgadnij, więc (zakładałem, że z jakiegoś powodu mogą być niecałkowite)
Jonathan Allan
6

Haskell, 33 bajty

h L=0 
h(N l r _)=1+max(h l)(h r)

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!

nimi
źródło
6

Perl 6 , 25 bajtów

{($_,{.[*;*]}...*eqv*)-2}

Dane wejściowe to lista 3-elementowa (l, r, v). Puste drzewo to pusta lista.

Wypróbuj online!

Wyjaśnienie

{                       }  # Anonymous block
    ,        ...  # Sequence constructor
  $_  # Start with input
     {.[*;*]}  # Compute next element by flattening one level
               # Sadly *[*;*] doesn't work for some reason
                *eqv*  # Until elements doesn't change
 (                   )-2  # Size of sequence minus 2

Stare rozwiązanie, 30 bajtów

{+$_&&1+max map &?BLOCK,.[^2]}

Wypróbuj online!

nwellnhof
źródło
&?BLOCKSztuką jest interesujący, ale jest to kilka bajtów krótszy przypisać blok $!
Jo King
@JoKing Nie wiem. Przechowywanie rozwiązania stanowiącego wyzwanie w niestabilnej globalnej sytuacji $!lub $/dla mnie jest oszustwem.
nwellnhof
(Ab) przy użyciu zmiennych takich jak $! i $ / to dość standardowa praktyka gry w golfa P6.
user0721090601
6

05AB1E , 11 7 5 bajtów

Δ€`}N

-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żdy left_treei right_treesą 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:

Δ     # Loop until the (implicit) input-list no longer changes:
  €`  #  Flatten the list one level
}N    # After the loop: push the 0-based index of the loop we just finished
      # (which is output implicitly as result)

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.

Kevin Cruijssen
źródło
1
7 bajtów?
Data wygasła
@ExpiredData Ah, oczywiście .. Dzięki! :)
Kevin Cruijssen
1
5 bajtów
Grimmy,
@Grimy Myślałem, że użycie indeksu poza pętlą działa tylko w starszym kodzie ..: S Dzięki!
Kevin Cruijssen
5

JavaScript (ES6),  35  33 bajtów

Struktura wejściowa: [[left_node], [right_node], value]

f=([a,b])=>a?1+f(f(a)>f(b)?a:b):0

Wypróbuj online!

Skomentował

f =                       // f is a recursive function taking
([a, b]) =>               // a node of the tree split into
                          // a[] = left child, b[] = right child (the value is ignored)
  a ?                     // if a[] is defined:
    1 +                   //   increment the final result for this branch
    f(                    //   and add:
      f(a) > f(b) ? a : b //     f(a) if f(a) > f(b) or f(b) otherwise
    )                     //
  :                       // else:
    0                     //   stop recursion and return 0
Arnauld
źródło
Wygląda na to, że możesz zapisać bajt a&&-~.
Kudłaty
1
@Shaggy To doprowadziłoby do porównań z nieokreślonymi .
Arnauld
4

C, 43 bajty

h(T*r){r=r?1+(int)fmax(h(r->l),h(r->r)):0;}

Struktura drzewa binarnego jest następująca:

typedef struct tree
{
  struct tree * l;

  struct tree * r;

  int v;

} tree;
T. Salim
źródło
2
55 bajtów Wypróbuj online! Oto kilka sztuczek golfowych specyficznych dla C !
ErikF
1
@ErikF Lub 45 bajtów
Arnauld
2
43 bajty
nwellnhof
3
Jeśli Twoje zgłoszenie opiera się na flagach, czy możesz dodać je do nagłówka zgłoszenia?
Jo King
1
Opierając się na @nwellnhof 42 bajtów
ceilingcat
4

JavaScript (Node.js) , 32 bajty

f=a=>/,,/.test(a)&&f(a.flat())+1

Wypróbuj online!

Używanie nazwy flatzamiast flattenlub smooshto świetny pomysł na golfa kodowego.

Używanie []węzła zerowego w drzewie i [left, right, value]węzłów. valuetutaj jest liczba całkowita.

tsh
źródło
3

Haskell, 28 bajtów

Korzystanie z następującej definicji danych:

data T a = (:&) a [T a]

Wysokość wynosi:

h(_:&x)=foldr(max.succ.h)0 x
Michael Klein
źródło
2

Schemat, 72 bajty

(define(f h)(if(null? h)0(+ 1(max(f(car(cdr h)))(f(car(cdr(cdr h))))))))

Bardziej czytelna wersja:

(define (f h)
   (if (null? h)
      0
      (+ 1 
         (max
             (f (car (cdr h)))
             (f (car (cdr (cdr h))))
         )
      )
   )
)

Korzystanie z list formularza (dane, lewy, prawy) do reprezentowania drzewa. Na przykład

   1
  / \
  2  3
 /\
 4 5

is represented as: (1 (2 (4 () ()) (5 () ())) (3 () ())

(1
   (2
      (4 () ())
```   (5 () ())
   (3 () ())
)

Wypróbuj online!

Zachary Cotton
źródło
2

R , 51 bajtów

function(L){while(is.list(L<-unlist(L,F)))T=T+1;+T}

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

`~`=function(L,d=0)'if'(is.list(L),max(L[[2]]~d+1,L[[3]]~d+1),d)

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)

  • -2 dzięki @Giuseppe
digEmAll
źródło
dlaczego używasz, d=1a potem d-1na końcu? Nie możesz zacząć od 0?
Giuseppe
Również przełączyłem >się ~ tutaj, aby łatwiej było wprowadzić przypadki testowe
Giuseppe
@Giuseppe: oczywiście ... brakowało mi oczywistego 🤦‍♂️
digEmAll
1

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

(2;
  (7;
    (,2);
    (6;
      (,5);
      (,11)
    )
  );
  (5;
    ();
    (9;
      (,4);
      ()
    )
  )
)

lub: (2;(7;(,2);(6;(,5);(,11)));(5;();(9;(,4);()))) .

Rozwiązaniem jest iteracyjne spłaszczenie i policzenie iteracji:

#,/\ / the solution
   \ / iterate
 ,/  / flatten
#    / count
streetster
źródło
0

Węgiel drzewny , 29 bajtów

⊞θ⁰⊞υθFυ«≔⊕⊟ιθFΦι∧κλ⊞υ⊞Oκθ»Iθ

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.

Fυ«

Wykonaj pierwsze wyszukiwanie drzewa.

≔⊕⊟ιθ

Uzyskaj głębokość tego węzła.

FΦι∧κλ

Pętla nad dowolnymi węzłami potomnymi.

⊞υ⊞Oκθ

Poinformuj węzeł potomny o jego głębokości nadrzędnej i pchnij go na listę wszystkich węzłów.

»Iθ

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.

Neil
źródło
0

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.

        The input starts on top of the input stack
Z       Tuck a zero underneath the top value in the stack.  Both values end up on the main stack.
D       Drop the first element from array
F       For each remaining element (the leaves) run the rest of the program
  G^    Recursively call the entire program, then increment
  T     Get maximum of the two numbers now ow the stack

Uruchom ten

rekurencyjny
źródło
0

Kotlin, 45 bajtów

val Tree.h:Int get()=1+maxOf(l?.h?:0,r?.h?:0)

Zakładając, że zdefiniowano następującą klasę

class Tree(var v: Int, var l: Tree? = null, var r: Tree? = null)

Wypróbuj online

Aso Leo
źródło
0

Julia, 27 bajtów

f(t)=t≢()&&maximum(f,t.c)+1

Z następującą strukturą reprezentującą drzewo binarne:

struct Tree
    c::NTuple{2,Union{Tree,Tuple{}}}
    v::Int
end

cto krotka reprezentująca lewy i prawy węzeł, a pusta krotka ()służy do sygnalizowania braku węzła.

użytkownik3263164
źródło
0

Kotlin , 42 bajty

fun N.c():Int=maxOf(l?.c()?:0,r?.c()?:0)+1

Wypróbuj online!

Gdzie

data class N(val l: N? = null, val r: N? = null, val v: Int = 0)
Brojowski
źródło