Suchen Sie den tiefsten Knoten eines Binärbaums

9

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 Tist die Kennung eines oder mehrerer alphanumerischer Zeichen und jedes xist 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.

Baum 1

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.

Baum 2

Dies ist Code Golf, also gewinnt der kürzeste in Bytes gemessene Code.

Jwosty
quelle
@ close-voter: worüber bist du unklar?
Jwosty
3
Möglicherweise die Tatsache, dass es keine Eingabe- oder Ausgabespezifikation oder Testfälle für diese Ein- und Ausgaben gibt.
Türknauf
Ich versuche es zu reparieren, aber mein Telefon ist scheiße ...: P es ist aber besser so.
Jwosty
3
Sollte der erste Baum nicht A (B (C, D (E)) sein?
Bakerg
1
@ Bakerg richtig, mein Fehler. Fest.
Jwosty

Antworten:

6

CJam, 49 47

0q')/{'(/):U;,+:TW>{T:W];}*TW={U]',*}*T(}/;W':@

 

0                 " Push 0 ";
q                 " Read the whole input ";
')/               " Split the input by ')' ";
{                 " For each item ";
  '(/             " Split by '(' ";
  )               " Extract the last item of the array ";
  :U;             " Assign the result to U, and discard it ";
  ,               " Get the array length ";
  +               " Add the top two items of the stack, which are the array length and the number initialized to 0 ";
  :T              " Assign the result to T ";
  W>{             " If T>W, while W is always initialized to -1 ";
    T:W];         " Set T to W, and empty the stack ";
  }*
  TW={            " If T==W ";
    U]',*         " Push U and add a ',' between everything in the stack, if there were more than one ";
  }*
  T(              " Push T and decrease by one ";
}/
;                 " Discard the top item, which should be now -1 ";
W                 " Push W ";
':                " Push ':' ";
@                 " Rotate the 3rd item to the top ";
jimmy23013
quelle
Ich habe das Ausgabeformat geringfügig geändert, um es konsistent und weniger mehrdeutig zu machen, aber es sollte nicht zu unangenehm sein.
Jwosty
@ Jwosty Es sollte nicht, wenn dies kein Code-Golf ist.
Jimmy23013
Nun, das ist Code-Golf ... Aber trotzdem, nette Einreichung :)
Jwosty
Können Sie bitte erklären, wie das funktioniert?
Jerry Jeremiah
@ JerryJeremiah Bearbeitet.
Jimmy23013
5

Haskell, 186 Bytes

p@(n,s)%(c:z)=maybe((n,s++[c])%z)(\i->p:(n+i,"")%z)$lookup c$zip"),("[-1..1];p%_=[p]
(n,w)&(i,s)|i>n=(i,show i++':':s)|i==n=(n,w++',':s);p&_=p
main=interact$snd.foldl(&)(0,"").((0,"")%)

Vollständiges Programm, nimmt Baum auf stdin, erzeugt spezifiziertes Ausgabeformat auf stdout:

& echo '2(7(2,6(5,11)),5(9(4)))' | runhaskell 32557-Deepest.hs 
3:5,11,4

& echo 'A(B(C,D(E)))' | runhaskell 32557-Deepest.hs 
3:E

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

type Label = String         -- the label on a node
type Node = (Int, Label)    -- the depth of a node, and its label

-- | Break a string into nodes, counting the depth as we go
number :: Node -> String -> [Node]
number node@(n, label) (c:cs) =
    maybe addCharToNode startNewNode $ lookup c adjustTable
  where
    addCharToNode = number (n, label ++ [c]) cs
        -- ^ append current character onto label, and keep numbering rest

    startNewNode adjust = node : number (n + adjust, "") cs
        -- ^ return current node, and the number the rest, adjusting the depth

    adjustTable = zip "),(" [-1..1]
        -- ^ map characters that end node labels onto depth adjustments
        -- Equivalent to [ (')',-1), (',',0), ('(',1) ]

number node _ = [node]      -- default case when there is no more input

-- | Accumulate into the set of deepest nodes, building the formatted output
deepest :: (Int, String) -> Node -> (Int, String)
deepest (m, output) (n, label)
    | n > m     = (n, show n ++ ':' : label)    -- n is deeper tham what we have
    | n == m    = (m, output ++ ',' : label)    -- n is as deep, so add on label
deepest best _ = best                           -- otherwise, not as deep

main' :: IO ()
main' = interact $ getOutput . findDeepest . numberNodes
  where
    numberNodes :: String -> [Node]
    numberNodes = number (0, "")

    findDeepest :: [Node] -> (Int, String)
    findDeepest = foldl deepest (0, "")

    getOutput :: (Int, String) -> String
    getOutput = snd
MtnViewMark
quelle
1
Dieser Code erschreckt mich.
siehe
Erweiterter erklärender Code hinzugefügt! Lass dich vom Terror stärker machen !!
MtnViewMark
Sie verdienen eine +1 dafür.
siehe
Oh mein Gott, und ich kämpfe mit Listen: P
Artur Trapp
4

GolfScript (75 Zeichen)

Nicht besonders wettbewerbsfähig, aber so verdreht, dass es ein gewisses Interesse hat:

{.48<{"'^"\39}*}%','-)](+0.{;.@.@>-\}:^;@:Z~{2$2$={@@.}*;}:^;Z~\-])':'@','*

Der Code besteht aus drei Phasen. Zuerst verarbeiten wir die Eingabezeichenfolge vor:

# In regex terms, this is s/([ -\/])/'^\1'/g
{.48<{"'^"\39}*}%
# Remove all commas
','-
# Rotate the ' which was added after the closing ) to the start
)](+

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:

0.
# The block we assign to ^ assumes that the stack is
#   max-depth current-depth string
# It discards the string and updates max-depth
{;.@.@>-\}:^;
@:Z~

Schließlich wählen wir die tiefsten Knoten aus und erstellen die Ausgabe:

# The block we assign to ^ assumes that the stack is
#   max-depth current-depth string
# If max-depth == current-depth it pushes the string under them on the stack
# Otherwise it discards the string
{2$2$={@@.}*;}:^;
# Eval
Z~
# The stack now contains
#   value1 ... valuen max-depth 0
# Get a positive value for the depth, collect everything into an array, and pop the depth
\-])
# Final rearranging for the desired output
':'@','*
Peter Taylor
quelle
1

Perl 5 - 85

Bitte zögern Sie nicht, diesen Beitrag zu bearbeiten, um die Anzahl der Zeichen zu korrigieren. Ich verwende die sayFunktion, weiß aber nichts über die Flags, damit sie ohne Deklaration korrekt ausgeführt werden use 5.010;.

$_=$t=<>,$i=0;$t=$_,$i++while s/\w+(\((?R)(,(?R))?\))?/$1/g,/\w/;@x=$t=~/\w+/gs;say"$i:@x"

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

2
0:2

2(3(4(5)),6(7))
3:5

2(7(2,6(5,11)),5(9(4)))
3:5 11 4

1(2(3(4,5),6(7,8)),9(10(11,12),13(14,15)))
3:4 5 7 8 11 12 14 15
n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳
quelle
1

VB.net

Function FindDeepest(t$) As String
  Dim f As New List(Of String)
  Dim m = 0
  Dim d = 0
  Dim x = ""
  For Each c In t
    Select Case c
      Case ","
        If d = m Then f.Add(x)
        x = ""
      Case "("
        d += 1
        If d > m Then f.Clear() :
        m = d
        x = ""
      Case ")"
        If d = m Then f.Add(x) : x = ""
        d -= 1
      Case Else
        x += c
    End Select
  Next
  Return m & ":" & String.Join(",", f)
End Function

Annahme: Knotenwerte nicht enthalten kann ,, (,)

Adam Speight
quelle
1
Dies scheint überhaupt nicht Golf zu sein. Können Sie den größten Teil dieses Leerzeichens nicht entfernen (ich kenne VB nicht)?
siehe
Hängt davon ab, dass ein Teil des Leerzeichens von Bedeutung ist.
Adam Speight
1

Javascript (E6) 120

Iterative Version

m=d=0,n=[''];
prompt().split(/,|(\(|\))/).map(e=>e&&(e=='('?m<++d&&(n[m=d]=''):e==')'?d--:n[d]+=' '+e));
alert(m+':'+n[m])

Ungolfed und prüfbar

F= a=> (
    m=d=0,n=[''],
    a.split(/,|(\(|\))/)
    .map(e=>e && (e=='(' ? m < ++d && (n[m=d]='') : e==')' ? d-- : n[d]+=' '+e)),
    m+':'+n[m]
)

In der Firefox-Konsole testen :

['A', '2(7(2,6(5,11)),5(9(4)))', 'A(B(C,D(E)))']
.map(x => x + ' --> ' + F(x)).join('\n')

Ausgabe

"A -> 0: A.

2 (7 (2,6 (5,11)), 5 (9 (4))) -> 3: 5 11 4

A (B (C, D (E))) -> 3: E

edc65
quelle