"El reto de la semana", 5ª edición

Se me ocurre que cuando trabajamos con algunas estructuras de datos, a veces es útil poder verlas representadas, aunque solo sea en texto plano. Por ello, me atrevo a enunciar el 5º reto:

Diseñar el algoritmo que permita la impresión de un árbol por pantalla. No importa si es texto plano, xml o algo parecido. El caso es que, por ejemplo, para un árbol definido asi: 4( 2( 1,3), 6( 5, 7)), lo podamos ver así:

     ┌───4───┐
   ┌─2─┐   ┌─6─┐
   1   3   5   7

O parecido, claro. Sencillo, ¿verdad?

Comentarios

Opciones de visualización de comentarios

Seleccione la forma que prefiera para mostrar los comentarios y haga clic en «Guardar las opciones» para activar los cambios.
Imagen de david.villa

Creo que la definición del

Creo que la definición del árbol tiene un error, debería tener una ‘,’ antes del 6. Si los hijos de 6 y de 2 están separados por comas ¿por qué no lo están los hijos de 4?. Si 2 no tuviera hijos quedaría 4( 2 6( 5, 7)) que no parece correcto. Supongo que la ausencia de esa coma es un error del enunciado. ¿Estoy en lo cierto? Si realmente no hay coma ahí, tampoco pasa nada, se puede parsear en cualquier caso.

He convertido la definición en forma de cadena a una representación recursiva, más acorde con un árbol. La función para hacer la conversión es:

def parse(data):
  retval = []
  val = ''
  i = 0
 
  while i < len(data):
    v = data[i]
    i += 1
 
    if v in ',() ':
      if val: retval.append((val,))
      val = ''
    else: val += v
 
    if v == '(':
      n, children = parse(data[i:])
      i += n
      retval[-1] = (retval[-1][0], children)
 
    if v == ')': break
 
  return i, retval

Siendo data la cadena del enunciado, esta función (quitando los espacios) devuelve:

>>> print parse(data.replace(' ',''))
(16, [('4', [('2', [('1',), ('3',)]), ('6', [('5',), ('7',)])])])

La función parse() devuelve una dupla con el nº de caracteres realmente parseados y el árbol en si. Cada nodo del árbol es una dupla, siendo el primer elemento el valor del nodo y el segundo una lista con sus hijos.

La función para “pintar” un árbol con este formato es:

def draw(A, conn=[]):
  for i,v in enumerate(A):
    lin = ''
    c = '+'
 
    if len(A) == i+1: c = '`'
    for r in conn:
      if r: lin += '| '
      else: lin += '  '
 
    print '%s%s-%s' % (lin, c, v[0])
    if len(v) > 1:
      draw(v[1], conn + [len(A) != i+1])

que pinta esto:

`-4
  +-2
  | +-1
  | `-3
  `-6
    +-5
    `-7

que no es tan bonito como el ejemplo del enunciado, pero refleja perfectamente la estructura del árbol.

No soy portavoz de ningún colectivo, grupo o facción. Mi opinión es personal e intransferible.

Imagen de david.villa

Una pequeña mejora

Una pequeña mejora, las líneas que representan las relaciones entre "ancestros" también se pueden construir en la recursión, evitando ese vector de booleanos tan feo y el bucle for.

def draw(A, conn=''):
  for i,v in enumerate(A):
    brother = '+'
    parent = '| '
 
    if len(A)-1 == i:
      brother = '`'
      parent = '  '
 
    print '%s-%s' % (conn + brother, v[0])
 
    if len(v) > 1:
      draw(v[1], conn + parent)

Más corto y más sencillo.

No soy portavoz de ningún colectivo, grupo o facción. Mi opinión es personal e intransferible.

Imagen de oscarah

vaaale

Es cierto, es un error, me falta una coma, pero no me atrevo a ponerla por si me desaparece el post de portada Sticking out tongue

Y bien, no es como el enunciado, pero es igual a unas representaciones que estamos muy acostumbrados a ver: los exploradores de sistemas de archivos generalmente dibujan el sistema de ficheros de forma similar.

Esta bien, por lo menos es mas comprensible que el que yo tenia... Smiling.

"aviso: la dereferencia de punteros de tipo castigado romperá las reglas de alias estricto" --GCC 4.3.1