No dejes de divulgar nuestra página y códigos con otro, apóyanos para ampliar nuestra comunidad.
Solución:
Aquí está mi intento, usando la recursividad y haciendo un seguimiento del tamaño de cada nodo y el tamaño de los niños.
class BstNode:
def __init__(self, key):
self.key = key
self.right = None
self.left = None
def insert(self, key):
if self.key == key:
return
elif self.key < key:
if self.right is None:
self.right = BstNode(key)
else:
self.right.insert(key)
else: # self.key > key
if self.left is None:
self.left = BstNode(key)
else:
self.left.insert(key)
def display(self):
lines, *_ = self._display_aux()
for line in lines:
print(line)
def _display_aux(self):
"""Returns list of strings, width, height, and horizontal coordinate of the root."""
# No child.
if self.right is None and self.left is None:
line = '%s' % self.key
width = len(line)
height = 1
middle = width // 2
return [line], width, height, middle
# Only left child.
if self.right is None:
lines, n, p, x = self.left._display_aux()
s = '%s' % self.key
u = len(s)
first_line = (x + 1) * ' ' + (n - x - 1) * '_' + s
second_line = x * ' ' + '/' + (n - x - 1 + u) * ' '
shifted_lines = [line + u * ' ' for line in lines]
return [first_line, second_line] + shifted_lines, n + u, p + 2, n + u // 2
# Only right child.
if self.left is None:
lines, n, p, x = self.right._display_aux()
s = '%s' % self.key
u = len(s)
first_line = s + x * '_' + (n - x) * ' '
second_line = (u + x) * ' ' + '\' + (n - x - 1) * ' '
shifted_lines = [u * ' ' + line for line in lines]
return [first_line, second_line] + shifted_lines, n + u, p + 2, u // 2
# Two children.
left, n, p, x = self.left._display_aux()
right, m, q, y = self.right._display_aux()
s = '%s' % self.key
u = len(s)
first_line = (x + 1) * ' ' + (n - x - 1) * '_' + s + y * '_' + (m - y) * ' '
second_line = x * ' ' + '/' + (n - x - 1 + u + y) * ' ' + '\' + (m - y - 1) * ' '
if p < q:
left += [n * ' '] * (q - p)
elif q < p:
right += [m * ' '] * (p - q)
zipped_lines = zip(left, right)
lines = [first_line, second_line] + [a + u * ' ' + b for a, b in zipped_lines]
return lines, n + m + u, max(p, q) + 2, n + u // 2
import random
b = BstNode(50)
for _ in range(50):
b.insert(random.randint(0, 100))
b.display()
Salida de ejemplo:
__50_________________________________________
/
________________________43_ ________________________99
/ /
_9_ 48 ____________67_____________________
/ /
3 11_________ 54___ ______96_
/ /
0 8 ____26___________ 61___ ________88___ 97
/ / /
14_ __42 56 64_ 75_____ 92_
/ / / / /
13 16_ 33_ 63 65_ 72 81_ 90 94
/ /
25 __31 41 66 80 87
/ /
28_ 76
29
Lo que está buscando es un recorrido que priorice la amplitud, que le permite atravesar un árbol nivel por nivel. Básicamente, usa una cola para realizar un seguimiento de los nodos que necesita visitar, agregando niños al espalda de la cola a medida que avanza (en lugar de agregarlos a la parte delantera de una pila). Primero haz que funcione.
Después de hacer eso, puede averiguar cuántos niveles tiene el árbol (log2(node_count) + 1) y utilícelo para estimar los espacios en blanco. Si desea obtener el espacio en blanco exactamente correcto, puede usar otras estructuras de datos para realizar un seguimiento de cuántos espacios necesita por nivel. Sin embargo, una estimación inteligente utilizando el número de nodos y niveles debería ser suficiente.
Mejoré la respuesta de Prashant Shukla para imprimir los nodos en el mismo nivel en la misma línea sin espacios.
class Node(object):
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def __str__(self):
return str(self.value)
def traverse(root):
current_level = [root]
while current_level:
print(' '.join(str(node) for node in current_level))
next_level = list()
for n in current_level:
if n.left:
next_level.append(n.left)
if n.right:
next_level.append(n.right)
current_level = next_level
t = Node(1, Node(2, Node(4, Node(7)), Node(9)), Node(3, Node(5), Node(6)))
traverse(t)