Viendo un árbol en ASCII

Como actividad de paso del tiempo, decidí implementar una estructura de árbol (similar) en python.
Implementé una clase de Node (que solo sirve al propósito aquí) así:

 class Node: def __init__(self, name, parent, *data): self.name = name self.parent = parent self.data = data self.children = [] self.is_root = False def __repr__(self): return 'Node '+repr(self.name) def dic(self): retval = {self:[]} for i in self.children: retval[self].append(i.dic()) return retval def display(self): # Here pass def has_children(self): return bool(self.children) def get_parent(self): return self.parent def add_child(self, name, *data): child = Node(name, self,*data) self.children.append(child) return child 

Como se puede ver, la función de display no está implementada.
Aquí hay un árbol de ejemplo.

 A = Node('A',Node) A.is_root = True B = A.add_child('B') D = B.add_child('D') C = A.add_child('C') E = C.add_child('E') F = C.add_child('F') G = C.add_child('G') 

Aquí hay algunos resultados de muestra para la display .

 >>> A.display() A +-^-+ BC | +-+-+ DEFG >>> C.display() C +-+-+ EFG 

En la forma más corta,
¿Cómo puedo “construir” un árbol ASCII (como arriba) de la clase Node?

En una forma más larga,
La “lógica” de la impresión es:

  1. Cuando hay un solo niño, | Se pone por encima del niño. (RE)
  2. De lo contrario, cada niño tiene un + encima de él, (B, C, E, F)
  3. Cuando ni siquiera hay. De los niños, ^ se pone debajo del padre. (UNA)
  4. De lo contrario, (hay un número impar de niños) + se coloca debajo del padre. (DO)

He estado pensando en empezar desde abajo. Me di cuenta de que tiene que haber una llamada a cada uno de los niños, pero no he podido implementar nada (de ese tipo o de otro tipo) que haya dado algo parecido.

Aquí hay una solución que cubre la mayor parte de lo que estás buscando.

Como cualquier algoritmo de árbol, recuenta a los hijos del árbol y combina los resultados en cada nodo. Aquí está el truco: display() devuelve un rectángulo de texto, por ejemplo:

 aaaaaa aaaaaa aaaaaa 

La mayor parte del rectángulo será espacios en blanco. Devolver solo rectangularjs de texto facilita la combinación de resultados. Usaremos las siguientes dos funciones auxiliares, una para medir el ancho de los bloques y la otra para combinar los bloques horizontalmente en bloques más grandes:

 def block_width(block): try: return block.index('\n') except ValueError: return len(block) def stack_str_blocks(blocks): """Takes a list of multiline strings, and stacks them horizontally. For example, given 'aaa\naaa' and 'bbbb\nbbbb', it returns 'aaa bbbb\naaa bbbb'. As in: 'aaa + 'bbbb = 'aaa bbbb aaa' bbbb' aaa bbbb' Each block must be rectangular (all lines are the same length), but blocks can be different sizes. """ builder = [] block_lens = [block_width(bl) for bl in blocks] split_blocks = [bl.split('\n') for bl in blocks] for line_list in itertools.izip_longest(*split_blocks, fillvalue=None): for i, line in enumerate(line_list): if line is None: builder.append(' ' * block_lens[i]) else: builder.append(line) if i != len(line_list) - 1: builder.append(' ') # Padding builder.append('\n') return ''.join(builder[:-1]) 

¿Ves a dónde va esto? Los niños devuelven un rectángulo que se muestra a sí mismos y a sus descendientes, y cada nodo combinará estos rectangularjs en un rectángulo más grande que se contiene a sí mismo. El rest del código simplemente representa los guiones y las ventajas:

 class Node: def display(self): # Here if not self.children: return self.name child_strs = [child.display() for child in self.children] child_widths = [block_width(s) for s in child_strs] # How wide is this block? display_width = max(len(self.name), sum(child_widths) + len(child_widths) - 1) # Determines midpoints of child blocks child_midpoints = [] child_end = 0 for width in child_widths: child_midpoints.append(child_end + (width // 2)) child_end += width + 1 # Builds up the brace, using the child midpoints brace_builder = [] for i in xrange(display_width): if i < child_midpoints[0] or i > child_midpoints[-1]: brace_builder.append(' ') elif i in child_midpoints: brace_builder.append('+') else: brace_builder.append('-') brace = ''.join(brace_builder) name_str = '{:^{}}'.format(self.name, display_width) below = stack_str_blocks(child_strs) return name_str + '\n' + brace + '\n' + below # SNIP (your other methods) 

¡Y nos vamos a las carreras!

  a +-+-+---------------------------+ befg + +-+-------------------------+ chik + + +-+-+-+-------------+-------------+-+------+ djlmprs OPQ + + +-+-+-+---------+ +-----+ nqtuwxy RS + + +-------+-------+ +---+---+ ovz AMTUZ +-+-+-+-+-+-+ + + + BDEHIKLNV a + + + +-+-+ + CFJWXY b + G 

(Requisitos como “colocar un ^ debajo del padre” se dejan como un ejercicio para el lector)

Me gustaría sugerirle echar un vistazo al módulo de ETE http://ete.cgenomics.org que implementa la funcionalidad que describe aquí y mucho más.

Al mismo tiempo, me gustaría proporcionar esta entrada de Impresión de impresión bonita en un formato de árbol lateral en la ventana de la consola, donde se ha formulado una pregunta similar anteriormente. Como puede ver en tal discusión, la función _asciiArt de ETE proporciona lo que creo que está buscando.

Espero que esto ayude,