Apuntes_Python/03_arbol_binario

Binary Tree

¿Que es un Arbol? (Tree)

Un árbol contiene nodos, generalmente represantados como círculos
Un nodo contener otros nodos, el punto que une un nodo con otro
es llamado edge (borde)

graph TD
    id1((A)) --> id2((B))
    id2((B)) --> id3((D))
    id2((B)) --> id4((E))
    id1((A)) --> id5((C))
    id5((C)) --> id6((F))

Estos nodos pueden representar cualquier objeto.
Los nodos tienen relaciones unos con otros:

• B es padre de D y E (parent)
• D y E son hijos de B (child)
• A es el nodo raíz (root), no tiene padres
• D, E y F son nodos hoja (leaf), no tienen hijos

En el gráfico superior, los nodos leaf están a 2 niveles del nodo root

En el sgte. grafico los nodos leaf (C, D y E) están en distinto nivel

graph TD
    id1((A)) --> id2((B))
    id2((B)) --> id3((D))
    id2((B)) --> id4((E))
    id1((A)) --> id5((C))

Binary Tree

Binario tiene relacion al número 2. Un árbol binario es un árbol cuyos nodos tienen:

• máximo 2 hijos
• solo una raíz (root)
• solo una ruta entre entre nodos

No son arboles binarios:

• A tiene 3 nodos hijos

graph TD
    id1((A)) --> id2((B))
    id2((B)) --> id3((D))
    id2((B)) --> id4((E))
    id1((A)) --> id5((C))
    id1((A)) --> id6((F))

• C tiene dos nodos raíz

graph TD
    id1((A)) --> id2((B))
    id2((B)) --> id3((D))
    id2((B)) --> id4((E))
    id1((A)) --> id5((C))
    id5((C)) --> id6((F))
    id7((G)) --> id5((C))

• El nodo 'E' tiene dos rutas posibles (A, B, E) y (A, C, F)

graph TD
    id1((A)) --> id2((B))
    id2((B)) --> id3((D))
    id2((B)) --> id4((E))
    id1((A)) --> id5((C))
    id5((C)) --> id6((F))
    id5((C)) --> id4((E))

• Ningún nodo es root y hay infinitas rutas a los nodos

graph TD
    id1((A)) --> id2((B))
    id2((B)) --> id3((C))
    id3((C)) --> id1((A))

Son considerados árbol binario:

• Arbol con 1 root y 2 nodos child

graph TD
    id1((A)) --> id2((B))
    id1((A)) --> id5((C))

• Arbol con 1 root y 1 nodo child

graph TD
    id1((  A  )) --> id2((  B  ))

• Arbol único

graph TD
    id1((  A  ))

• Arbol vacío (empty tree)

Clase Arbol Binario

Representación de árbol binario con algún lenguaje de programación

• Cada nodo es un objeto (una instancia de clase)
• Las propiedades de un nodo son:
  • Su valor
  • Su referencia a nodos hijos (nodo.left, nodo.right)

class Nodo:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

---

Funciones para Arboles Binarios

Retornar valores

Prioridad valores de nodo hijo sobre valores de nodo del mismo nivel

def ValoresLejanosPrioridad(self):
    """
    retorna valor de nodos priorizando profundidad a nivel (de izquierda a derecha)
    usando recursividad y desempaquetado de lista (operador '*')
    """
    if self is None:
        return []
    val_izq = ValoresLejanosPrioridad(self.left)
    val_der = ValoresLejanosPrioridad(self.right)
    return [self.val, *val_izq, *val_der]

Prioridad valores de nodos mismo nivel

from collections import deque

def ValoresPrioridadNivel(self):
    """
    retorna valor de nodos de un arbol binario priorizando nodos
    del mismo nivel (de izquierda a derecha), usando una lista
    como cola (fifo)
    """
    cola = deque([self])
    valores = []
    if self == None:
        return []
    while cola:
        actual = cola.popleft()
        valores.append(actual.val)
        if actual.left:
            cola.append(actual.left)
        if actual.right:
            cola.append(actual.right)
    return valores

Comprobar un valor

def ArbolIncluye(self, valor):    
    """    
    retorna booleano según existencia en árbol binario    
    del valor consultado, utilizando recursión    
    """    
    if self is None:    
        return False    
    if self.val == valor:    
        return True    
    return ArbolIncluye(self.left, valor) or ArbolIncluye(self.right, valor)    

Suma de Valores

def SumaValores(self):
    """
    retorna la suma de todos los valores del árbol binario
    recursivamente.
    """
    if self is None:
        return 0
    return self.val + SumaValores(self.left) + SumaValores(self.right)

Valor Mínimo

def ValorMinimo(self):
    """
    retorna el valor mínimo en árbol binario usando recursividad
    """
    if self is None:
        return inf
    min_izq = ValorMinimo(self.left)
    min_der = ValorMinimo(self.right)
    return min(self.val, min_izq, min_der)

Ruta con mayor suma

def SumaMayorDeRutas(self):
    """
    retorna la suma de los valores de la ruta(root-leaf) del 
    árbol binario, cuya suma sea mayor. Usando recursión
    """
    if self is None:
        return -inf
    if self.left is None and self.right is None:
        return self.val
    mayor = max(SumaMayorDeRutas(self.left), SumaMayorDeRutas(self.right))
    return self.val + mayor

---

TestRunner

github.com/viniciusd