Schreiben Sie das kürzeste Programm zur Berechnung der Höhe eines Binärbaums

18

Die Höhe eines Binärbaums ist der Abstand vom Wurzelknoten zum untergeordneten Knoten, der am weitesten von der Wurzel entfernt ist.

Unten ist ein Beispiel:

           2 <-- root: Height 1
          / \
         7   5 <-- Height 2
        / \   \
       2   6   9 <-- Height 3
          / \  /
         5  11 4 <-- Height 4 

Höhe des Binärbaums: 4

Definition eines binären Baumes

Ein Baum ist ein Objekt, das einen vorzeichenbehafteten ganzzahligen Wert und entweder zwei andere Bäume oder Zeiger darauf enthält.

Die Struktur der binären Baumstruktur sieht ungefähr so ​​aus:

typedef struct tree
{
  struct tree * l;

  struct tree * r;

  int v;

} tree;

Die Herausforderung:

Eingang

Die Wurzel eines binären Baumes

Ausgabe

Die Zahl, die die Höhe eines Binärbaums darstellt

Angenommen, Sie erhalten die Wurzel eines Binärbaums als Eingabe, schreiben Sie das kürzeste Programm, das die Höhe eines Binärbaums berechnet und die Höhe zurückgibt. Das Programm mit der geringsten Anzahl von Bytes (Accounting Whitespaces) gewinnt.

T. Salim
quelle
4
Was brauchen Sprachen ohne Zeiger?
Jonathan Allan
4
... aber dann könnte mein Baumobjekt zum Beispiel nur eine Eigenschaft haben h. Könnte besser sein, eine bestimmte Struktur zu definieren, die nur aus Listen besteht, um diese Herausforderung zu bewältigen.
Jonathan Allan
11
@ T.Salim Bitte überlege dir in Zukunft zuerst, ob du etwas in die Sandbox schreiben möchtest .
wizzwizz4
1
Ist eine gültige Darstellung also eine Liste der Länge 3, [root_value, left_node, right_node]in der alle left_nodeund right_nodeauch Binärbäume zulässig sind? Es wird in vielen Sprachen trivial sein, aber in einigen anderen könnte es Spaß machen.
Jonathan Allan
3
Können Sie die Frage so bearbeiten, dass sie eine gültige Binärstruktur enthält? Vielleicht eine Definition wie a tree is an object that contains a value and either two other trees or pointers to them. Eine Definition, die Sprachen ohne Objekte einschließt, wäre auch schön.
Jo King

Antworten:

11

Gelee , 3 Bytes

ŒḊ’

Ein monadischer Link, der eine Liste akzeptiert, die den Baum darstellt: [root_value, left_tree, right_tree]wobei jede von left_treeund right_treeähnliche Strukturen sind (leer, wenn nötig), die die Höhe ergeben.

Probieren Sie es online!

Wie?

Ziemlich trivial in Jelly:

ŒḊ’ - Link: list, as described above
ŒḊ  - depth
  ’ - decremented (since leaves are `[value, [], []]`)
Jonathan Allan
quelle
Jonathon Allen, das ist eine interessante Sprache, die Sie verwenden. Können Sie als Neuling einen Link oder eine Website-Empfehlung bereitstellen, über die die Benutzer erfahren, wie Jelly verwendet wird?
T. Salim
4
Klicken Sie auf den Link in der Kopfzeile - es ist eine Golfsprache, die von Dennis , einem der Moderatoren der Website, entwickelt wurde.
Jonathan Allan
2
Ich frage mich, wie umstritten es wäre, ein Blatt darzustellen, xanstatt [x, [], []]...
Erik the Outgolfer
@EriktheOutgolfer Um mit der "Zeiger" und "Struktur" Natur der Frage zu bleiben, denke ich, dass jeder Knoten von der gleichen Form sein sollte.
Jonathan Allan
10

Python 2 ,  35  33 Bytes

Vielen Dank an Arnauld, der ein Versehen bemerkt und 4 gespart hat.

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

Eine rekursive Funktion, die eine Liste akzeptiert, die den Baum darstellt: [root_value, left_tree, right_tree]wobei jede von left_treeund right_treeähnliche Strukturen sind (ggf. leer), die die Höhe zurückgibt.

Probieren Sie es online!

Beachten Sie, dass zurückgegeben []wird False, jedoch in Python False==0.

Jonathan Allan
quelle
Dieselbe Person darf zwei unterschiedliche Antworten auf dieselbe Frage geben?
T. Salim
6
Natürlich ist Golf ein Wettbewerb auf Sprachniveau. Sogar ein zweiter Eintrag in derselben Sprache ist manchmal akzeptabel, wenn der Ansatz sehr unterschiedlich ist.
Jonathan Allan
@ Arnauld Rate mal (ich hatte angenommen, dass aus irgendeinem Grund nicht ganze Zahlen vorhanden sein könnten)
Jonathan Allan
6

Haskell, 33 Bytes

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

Verwenden des benutzerdefinierten Baumtyps data T = L | N T T Int, der dem Haskell-Äquivalent der in der Challenge angegebenen C-Struktur entspricht.

Probieren Sie es online!

nimi
quelle
6

Perl 6 , 25 Bytes

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

Die Eingabe ist eine Liste mit 3 Elementen (l, r, v). Der leere Baum ist die leere Liste.

Probieren Sie es online!

Erläuterung

{                       }  # 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

Alte Lösung, 30 Bytes

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

Probieren Sie es online!

nwellnhof
quelle
Der &?BLOCKTrick ist interessant, aber es ist ein paar Bytes kürzer , um den Block $ zuzuweisen!
Jo King
@JoKing Ich weiß es nicht. Das Speichern der Herausforderung Lösung in einem volatilen globalen wie $!oder $/fühlt sich an wie mir betrügt.
Nwellnhof
(Ab) Verwenden von Variablen wie $! und $ / ist ziemlich üblich für das Golfen P6.
user0721090601
6

05AB1E , 11 7 5 Bytes

Δ€`}N

-4 Bytes dank @ExpiredData .
-2 Bytes dank @Grimy .

Das Eingabeformat ist ähnlich wie bei der Gelee-Antwort: Eine Liste, die den Baum darstellt: [root_value, left_tree, right_tree]wobei jede von left_treeund right_treeähnliche Strukturen sind (optional leer). Dh [2,[7,[2,[],[]],[6,[5,[],[]],[11,[],[]]]],[5,[],[9,[4,[],[]],[]]]]repräsentiert den Baum aus der Herausforderungsbeschreibung.

Probieren Sie es online aus oder überprüfen Sie ein paar weitere Testfälle .

Erläuterung:

Δ     # 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)

Beachten Sie, dass 05AB1E zwar 0-basiert ist, die Änderungsschleife jedoch Δbewirkt, dass der Ausgabeindex korrekt ist, da eine zusätzliche Iteration erforderlich ist, um zu überprüfen, dass er sich nicht mehr ändert.

Kevin Cruijssen
quelle
1
7 Bytes?
Abgelaufene Daten
@ExpiredData Ah, natürlich .. Danke! :)
Kevin Cruijssen
1
5 Bytes
Grimmy
@Grimy Ich dachte, die Verwendung des Index außerhalb einer Schleife funktioniert nur im Legacy-Code ..: S Danke!
Kevin Cruijssen
5

JavaScript (ES6),  35  33 Bytes

Eingabestruktur: [[left_node], [right_node], value]

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

Probieren Sie es online!

Kommentiert

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
quelle
Sieht aus wie Sie ein Byte mit speichern können a&&-~.
Shaggy
1
@ Shaggy Das würde zu Vergleichen mit undefined führen .
Arnauld
4

C 43 Bytes

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

Die Struktur des Binärbaums ist wie folgt:

typedef struct tree
{
  struct tree * l;

  struct tree * r;

  int v;

} tree;
T. Salim
quelle
2
55 bytes Online testen! Einige C-spezifische Golf-Tricks sind da!
ErikF
1
@ ErikF Oder 45 Bytes
Arnauld
2
43 Bytes
Nwellnhof
3
Wenn Ihre Einreichung auf Flags basiert, können Sie diese bitte in die Kopfzeile Ihrer Einreichung einfügen?
Jo King
1
Aufbauend auf @nwellnhof 42 Bytes
Ceilingcat
4

JavaScript (Node.js) , 32 Byte

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

Probieren Sie es online!

Die Verwendung des Namens flatanstelle von flattenoder smooshist eine großartige Idee für Code-Golf.

Verwenden von []für Nullknoten in der Struktur und [left, right, value]für Knoten. valueHier ist eine ganze Zahl.

tsh
quelle
3

Haskell, 28 Bytes

Verwendung der folgenden Datendefinition:

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

Die Höhe beträgt:

h(_:&x)=foldr(max.succ.h)0 x
Michael Klein
quelle
2

Schema, 72 Bytes

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

Mehr lesbare Version:

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

Verwenden von Listen des Formulars (Daten, links, rechts) zur Darstellung eines Baums. Z.B

   1
  / \
  2  3
 /\
 4 5

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

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

Probieren Sie es online!

Zachary Cotton
quelle
2

R , 51 Bytes

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

Probieren Sie es online!

  • Eingabe: Eine verschachtelte Liste im Format:list(ROOT_ELEMENT, LEFT_TREE, RIGHT_TREE)

  • Algorithmus: Glättet den Baum iterativ um eine Ebene, bis er zu einem flachen Vektor wird: Die Anzahl der Iterationen entspricht der maximalen Tiefe.

Inspiriert von der @ KevinCruijssen-Lösung


Rekursive Alternative:

R , 64 Bytes

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

Probieren Sie es online!

Definiert die Funktion / den Operator neu, '~'sodass die maximale Tiefe eines in einer Listenstruktur gespeicherten Baums berechnet werden kann.

Die Listenstruktur eines Baums hat das Format: list(ROOT_ELEMENT, LEFT_TREE, RIGHT_TREE)

  • -2 danke an @ Giuseppe
digEmAll
quelle
warum benutzt du d=1und dann d-1am ende Könntest du nicht bei anfangen 0?
Giuseppe
Außerdem habe ich hierher gewechselt >, damit die Testfälle einfacher einzugeben sind~
Giuseppe
@ Giuseppe: natürlich ... mir fehlte die offensichtliche 🤦‍♂️
digEmAll
1

K (ngn / k) , 4 Bytes

Lösung:

#,/\

Probieren Sie es online!

Erläuterung:

Ich glaube, ich habe den Punkt verpasst.

Durch die Darstellung eines Baums als Liste mit drei Elementen (übergeordneter Knoten; linkes Kind; rechtes Kind) kann das Beispiel als dargestellt werden

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

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

Die Lösung ist also, iterativ zu reduzieren und die Iterationen zu zählen:

#,/\ / the solution
   \ / iterate
 ,/  / flatten
#    / count
Streetster
quelle
0

Kohle , 29 Bytes

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

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Ändert den Baum vorübergehend während der Verarbeitung. Erläuterung:

⊞θ⁰

Schieben Sie die Null auf den Wurzelknoten.

⊞υθ

Verschieben Sie den Stammknoten in die Liste aller Knoten.

Fυ«

Führen Sie eine Breitensuche des Baums durch.

≔⊕⊟ιθ

Ruft die Tiefe dieses Knotens ab.

FΦι∧κλ

Schleife über alle untergeordneten Knoten.

⊞υ⊞Oκθ

Teilen Sie dem untergeordneten Knoten die Tiefe des übergeordneten Knotens mit und verschieben Sie ihn in die Liste aller Knoten.

»Iθ

Nachdem alle Knoten durchlaufen wurden, wird die Tiefe des letzten Knotens gedruckt. Da die Durchquerung die Breite zuerst war, wird dies die Höhe des Baumes sein.

Neil
quelle
0

Stax , 5 Bytes

▐▌µ╡⌂

Führen Sie es aus und debuggen Sie es

Stax hat weder Zeiger noch Nullwerte, daher vertrete ich die Eingabe gerne [2,[7,[2,[],[]],[6,[5,[],[]],[11,[],[]]]],[5,[],[9,[4,[],[]],[]]]]. Vielleicht ist das ein unfairer Vorteil, aber es war der größte, den ich bekommen konnte.

Entpackt, ungolfed und kommentiert sieht der Code so aus.

        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

Führen Sie dieses aus

rekursiv
quelle
0

Kotlin, 45 Bytes

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

Angenommen, die folgende Klasse ist definiert

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

Probieren Sie es online aus

Aso Leo
quelle
0

Julia, 27 Bytes

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

Mit der folgenden Struktur, die den Binärbaum darstellt:

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

cist ein Tupel, das den linken und den rechten Knoten darstellt, und das leere Tupel ()wird verwendet, um die Abwesenheit eines Knotens anzuzeigen.

user3263164
quelle