Encuentra el nodo más profundo de un árbol binario

9

Escriba un programa que tome un árbol binario como entrada y genere el nodo más profundo y su profundidad. Si hay un empate, imprima todos los nodos involucrados, así como sus profundidades. Cada nodo se representa como:

T(x,x)

T(x)

T

donde Tes el identificador de uno o más caracteres alfanuméricos y cada uno xes otro nodo.

Aquí hay una definición simple de un árbol binario:

  • En la cabeza de un árbol binario hay un nodo.
  • Un nodo en un árbol binario tiene como máximo dos hijos.

Por ejemplo, la entrada A(B(C,D(E)))(a continuación) saldría 3:E.

Árbol 1

Si bien el siguiente árbol es un empate triple entre 5, 11 y 4, y su profundidad también es 3 (a partir de 0):

La entrada 2(7(2,6(5,11)),5(9(4)))(abajo) saldría 3:5,11,4.

Árbol 2

Este es el código de golf, por lo que gana el código más corto medido en bytes.

Jwosty
fuente
@ votante cercano: ¿de qué no está claro?
Jwosty
3
Quizás el hecho de que no hay especificación de entrada o salida, o casos de prueba para esas entradas y salidas.
Pomo de la puerta
Tratando de arreglarlo, pero mi teléfono apesta ...: P es mejor así que, aunque
Jwosty
3
¿No debería ser el primer árbol A (B (C, D (E))?
bakerg
1
@bakerg bien, mi error. Fijo.
Jwosty

Respuestas:

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
fuente
He realizado una ligera modificación en el formato de salida para que sea coherente y menos ambiguo, pero no debería ser un gran inconveniente.
Jwosty
@Jwosty No debería, si esto no es código golf.
jimmy23013
Bueno, este es el código de golf ... Pero de todos modos, buena presentación :)
Jwosty
¿Puedes explicar cómo funciona esto?
Jerry Jeremiah
@JerryJeremiah Editado.
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,"")%)

El programa completo, toma el árbol stdin, produce el formato de salida especificado en 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

Guía para el código golf'd (se agregaron mejores nombres, firmas de tipo, comentarios y algunas subexpresiones extraídas y nombradas, pero por lo demás el mismo código; una versión sin golf no se combinaría irrumpir en nodos con numeración, ni encontrar el más profundo con formato de salida.) :

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
fuente
1
Ese código me aterroriza.
seequ
¡Código explicativo ampliado agregado! ¡Deja que el terror te haga más fuerte!
MtnViewMark
Te mereces un +1 por eso.
seequ
Oh, Dios mío, y estoy luchando con las listas: P
Artur Trapp
4

GolfScript (75 caracteres)

No es especialmente competitivo, pero lo suficientemente retorcido como para que tenga algún interés:

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

El código tiene tres fases. En primer lugar, preprocesamos la cadena de entrada:

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

Nos hemos transformado, por ejemplo, A(B(C,D(E)))a 'A'^('B'^('C'^'D'^('E'^)''^)''^). Si asignamos un bloque adecuado, ^podemos hacer un procesamiento útil mediante el uso ~de evaluar la cadena.

En segundo lugar, encontramos la profundidad máxima:

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~

Finalmente seleccionamos los nodos más profundos y construimos la salida:

# 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
fuente
1

Perl 5-85

Siéntase libre de editar esta publicación para corregir el recuento de caracteres. Uso la sayfunción, pero no sé acerca de las banderas para que se ejecute correctamente sin declarar use 5.010;.

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

Demo en ideone

La salida está separada por espacios en lugar de por comas.

El código simplemente usa expresiones regulares recursivas para eliminar la raíz de los árboles en el bosque, hasta que no sea posible hacerlo. Luego, la cadena antes de la última contendrá todos los nodos de hoja en el nivel más profundo.

Ejecuciones de muestra

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̷̰̀ĥ̷̳
fuente
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

Supuesto: valores de los nodos no pueden contener ,, (,)

Adam Speight
fuente
1
Esto no parece ser golf en absoluto. ¿No puedes eliminar la mayor parte de ese espacio en blanco (no sé VB)?
seequ
Depende que parte del espacio en blanco sea significativo.
Adam Speight
1

Javascript (E6) 120

Versión iterativa

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

Sin golf y comprobable

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

Prueba en la consola de Firefox:

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

Salida

"A -> 0: A

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

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

edc65
fuente