Schreiben Sie ein Programm, das einen Binärbaum als Eingabe verwendet und den tiefsten Knoten und seine Tiefe ausgibt. Wenn es ein Unentschieden gibt, drucken Sie alle beteiligten Knoten sowie deren Tiefen. Jeder Knoten wird dargestellt als:
T(x,x)
T(x)
T
Dabei T
ist die Kennung eines oder mehrerer alphanumerischer Zeichen und jedes x
ist ein anderer Knoten.
Hier ist eine einfache Definition eines Binärbaums:
- An der Spitze eines Binärbaums steht ein Knoten.
- Ein Knoten in einem Binärbaum hat höchstens zwei Kinder.
Zum Beispiel würde die Eingabe A(B(C,D(E)))
(unten) ausgegeben 3:E
.
Während der folgende Baum eine Drei-Wege-Bindung zwischen 5, 11 und 4 ist und ihre Tiefe ebenfalls 3 beträgt (beginnend mit 0):
Die Eingabe 2(7(2,6(5,11)),5(9(4)))
(unten) würde ausgegeben 3:5,11,4
.
Dies ist Code Golf, also gewinnt der kürzeste in Bytes gemessene Code.
code-golf
binary-tree
Jwosty
quelle
quelle
Antworten:
CJam,
4947quelle
Haskell, 186 Bytes
Vollständiges Programm, nimmt Baum auf
stdin
, erzeugt spezifiziertes Ausgabeformat aufstdout
:Anleitung zum Golf-Code (bessere Namen, Typensignaturen , Kommentare und einige herausgezogene und benannte Unterausdrücke hinzugefügt - aber ansonsten derselbe Code; eine ungolf-Version würde nicht mit der Nummerierung in Knoten zerfallen oder die tiefste finden mit Ausgabeformatierung.) :
quelle
GolfScript (75 Zeichen)
Nicht besonders wettbewerbsfähig, aber so verdreht, dass es ein gewisses Interesse hat:
Der Code besteht aus drei Phasen. Zuerst verarbeiten wir die Eingabezeichenfolge vor:
Wir haben uns zB
A(B(C,D(E)))
in verwandelt'A'^('B'^('C'^'D'^('E'^)''^)''^)
. Wenn wir einen geeigneten Block zuweisen, können^
wir eine nützliche Verarbeitung durchführen, indem wir~
den String auswerten.Zweitens finden wir die maximale Tiefe:
Schließlich wählen wir die tiefsten Knoten aus und erstellen die Ausgabe:
quelle
Perl 5 - 85
Bitte zögern Sie nicht, diesen Beitrag zu bearbeiten, um die Anzahl der Zeichen zu korrigieren. Ich verwende die
say
Funktion, weiß aber nichts über die Flags, damit sie ohne Deklaration korrekt ausgeführt werdenuse 5.010;
.Demo auf ideone
Die Ausgabe ist durch Leerzeichen anstatt durch Kommas getrennt.
Der Code verwendet einfach rekursiven regulären Ausdruck, um die Wurzel der Bäume im Wald zu entfernen, bis dies nicht mehr möglich ist. Dann enthält die Zeichenfolge vor der letzten alle Blattknoten auf der tiefsten Ebene.
Probeläufe
quelle
VB.net
Annahme: Knotenwerte nicht enthalten kann
,
,(
,)
quelle
Javascript (E6) 120
Iterative Version
Ungolfed und prüfbar
In der Firefox-Konsole testen :
Ausgabe
quelle