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 T
es el identificador de uno o más caracteres alfanuméricos y cada uno x
es 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
.
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
.
Este es el código de golf, por lo que gana el código más corto medido en bytes.
code-golf
binary-tree
Jwosty
fuente
fuente
Respuestas:
CJam,
4947fuente
Haskell, 186 bytes
El programa completo, toma el árbol
stdin
, produce el formato de salida especificado enstdout
: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.) :
fuente
GolfScript (75 caracteres)
No es especialmente competitivo, pero lo suficientemente retorcido como para que tenga algún interés:
El código tiene tres fases. En primer lugar, preprocesamos la cadena de entrada:
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:
Finalmente seleccionamos los nodos más profundos y construimos la salida:
fuente
Perl 5-85
Siéntase libre de editar esta publicación para corregir el recuento de caracteres. Uso la
say
función, pero no sé acerca de las banderas para que se ejecute correctamente sin declararuse 5.010;
.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
fuente
VB.net
Supuesto: valores de los nodos no pueden contener
,
,(
,)
fuente
Javascript (E6) 120
Versión iterativa
Sin golf y comprobable
Prueba en la consola de Firefox:
Salida
fuente