Representación de árboles binarios
Los árboles binarios son una estructura de datos fundamental muy utilizada en el área de la informática. Son especialmente útiles para crear algoritmos eficientes que realicen operaciones como búsqueda, ordenación y recorrido de datos.
Los árboles binarios están formados por nodos, donde cada nodo puede tener como máximo dos hijos: un hijo izquierdo y un hijo derecho. Cada uno de estos hijos, a su vez, puede tener también sus propios hijos, y esta estructura continúa hasta que no quedan más nodos en el árbol.
El nodo que se encuentra en la parte superior del árbol se conoce como la raíz, mientras que los elementos de la parte inferior reciben el nombre de hojas del árbol.
Esta idea tan sencilla permite representar muchos tipos de datos diferentes de forma eficiente y resulta fácil de implementar en distintos lenguajes de programación:
class Node: # Objeto Node para almacenar los datos de cada nodo
def __init__(self, value): # El valor que se guarda en cada nodo (puede ser cualquier cosa)
self.left = None # Inicialmente tanto left como right son None
self.right = None
self.value = value # Guarda el valor en un objeto
# Creación manual de todos los nodos
root = Node(1)
root.left, root.right = Node(2), Node(3)
root.left.left, root.left.right = Node(4), Node(5)
root.left.right.left, root.left.right.right = Node(7), Node(8)
root.right.right = Node(6)
# Luego podemos recorrer recursivamente todo el árbol binario
# Calculemos la suma de todos los nodos
def treesum(node: Node | None) -> int:
if node is None:
return 0
# Devuelve la suma del subárbol izquierdo, el subárbol derecho y el nodo actual
return treesum(node.left) + treesum(node.right) + node.value
print(treesum(root)) # Imprime 36En este ejemplo, recorremos todos los nodos comenzando desde
root. Si el nodo actual es None, significa que hemos llegado al final de esa rama del subárbol, de modo que retornamos 0 como resultado. De lo contrario, calculamos la suma del subárbol izquierdo, el subárbol derecho y el valor del nodo actual, sumándolo todo.Desafío: Crear un árbol binario manualmente
Dado el árbol binario que se muestra en la imagen, se te pide crearlo manualmente.
Escribe un código que construya el árbol binario. No necesitas imprimir nada; esa parte está automatizada.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB