Un árbol binario de búsqueda es un árbol binario cuyos nodos almacenan claves (y valores asociados a esas claves) que se mantienen ordenadas de la siguiente manera: la raíz del árbol contiene una clave que es estrictamente mayor que todas las claves almacenadas en el hijo izquierdo y estrictamente menor que todas las claves almacenadas en el hijo derecho; además, ambos hijos son árboles binarios de búsqueda.

De los siguientes árboles (con números enteros como claves) solamente el de la derecha es un árbol binario de búsqueda.

Dado un árbol binario, el problema consiste en decidir si es o no un árbol binario de búsqueda.

Entrada

La entrada comienza con el número de casos que vienen a continuación. Cada caso de prueba consiste en una línea con la descripción de un árbol binario: primero aparece su raíz (un entero no negativo), y a continuación la descripción del hijo izquierdo y después la del hijo derecho. El número −1 indica el árbol vacío. Los árboles nunca contendrán más de 4.000 nodos.

Salida

Para cada árbol se escribirá SI si el árbol es un árbol binario de búsqueda y NO si no lo es.

Entrada de ejemplo

4
1 2 4 -1 -1 5 -1 -1 3 -1 6 -1 -1
5 4 1 -1 -1 -1 8 6 -1 -1 9 -1 -1
-1
2 2 -1 -1 -1

Salida de ejemplo

NO
SI
SI
NO

Solución propuesta

class ArbolBinarioBusqueda:

    def __init__(self, valor, padre=None, izquierda=None, derecha=None):
        self.valor = valor
        self.padre = padre
        self.izquierda = izquierda
        self.derecha = derecha

    def insertar_izquierda(self, valor):
        añadir = self.valor > valor
        if añadir:
            self.izquierda = ArbolBinarioBusqueda(valor, padre=self)

        return self.izquierda

    def insertar_derecha(self, valor):
        añadir = self.valor < valor
        if añadir:
            self.derecha = ArbolBinarioBusqueda(valor, padre=self)

        return self.derecha

    def devolver_padre(self):
        return self.padre


if __name__ == '__main__':
    IZQ = 'IZQUIERDA'
    DER = 'DERECHA'
    lista_respuestas = []
    numero_casos = int(input())
    for i in range(numero_casos):
        lista_nodos = [int(x) for x in list(input().split(' '))]
        es_bin_busqueda = True
        if lista_nodos[0] != -1:  # Árbol no vacío
            arbol = ArbolBinarioBusqueda(lista_nodos[0])
            nodo_actual = arbol
            rama = IZQ
            posicion_nodo = 1
            es_bin_busqueda = True
            while es_bin_busqueda and posicion_nodo < len(lista_nodos):
                if lista_nodos[posicion_nodo] != -1 and rama == IZQ:
                    nodo_actual = nodo_actual.insertar_izquierda(lista_nodos[posicion_nodo])
                    es_bin_busqueda = nodo_actual is not None
                elif lista_nodos[posicion_nodo] != -1 and rama == DER:
                    nodo_actual = nodo_actual.insertar_derecha(lista_nodos[posicion_nodo])
                    rama = IZQ
                    es_bin_busqueda = nodo_actual is not None
                elif lista_nodos[posicion_nodo] == -1 and rama == IZQ:
                    rama = DER
                elif lista_nodos[posicion_nodo] == -1 and rama == DER:
                    nodo_actual = nodo_actual.devolver_padre()

                posicion_nodo += 1
        if es_bin_busqueda:
            lista_respuestas.append('SI')
        else:
            lista_respuestas.append('NO')
    for respuesta in lista_respuestas:
        print(respuesta)

La realización de este código implica tener conocimientos de estructuras de datos y también de recursividad pero ese es otro tema. Primero hay que explicar qué es un árbol binario de búsqueda (ABB), es decir, hay que explicar tres cosas:

• Árbol: todos tenemos en mente qué es un árbol, visualmente es una raíz (o raíces), del cual parte un tronco y las distintas ramas, hasta llegar a las hojas. Pues bien, esto mismo tenemos aquí, el árbol comienza en la raíz y comienzan a surgir ramas hasta llegar a las hojas. Recuerdo que a partir de una rama pueden surgir una o muchas pero a una rama solo se llega por un camino, es decir, un padre puede tener varios hijos, pero un hijo solo tiene un padre.

• Binario: se refiere al número de hijos o de ramas que surgen a partir de una, en nuestro caso, binario, pues solo dos. Lo cual simplifica las cosas. También hay que puntualizar que una rama puede tener uno o dos hijos, no necesariamente dos.

• De búsqueda: este tercer concepto nos indica una condición que se ha de cumplir en cada nodo (que es como se llama a cada círculo en la imagen superior). Al ser nuestro árbol binario de búsqueda, necesariamente se ha de cumplir que todos los valores de la rama izquierda son menores al valor que almacena el nodo y por otro lado que todos los valores de la rama derecha son estríctamente mayores al valor que almacena el nodo.

Vale, ya tenemos más o menos claro qué es un árbol, pero, ¿cómo lo programamos? Pues buscando, yo no he encontrado una estructura tree en las librerías estándar de Python, por lo que o no existe o como digo, no la he encontrado. Por lo que vamos a programar una clase árbol binario de búsqueda, así, sin anestesia.

Como en Python todo es sencillo (hasta que se complica), pues definimos nuestra ArbolBinarioBusqueda, cumpliendo el PEP 8, es decir, la guía de estilo. Para definir los métodos dentro de una clase usamos al igual que para las funciones la palabra reservada ref y el primer método que hay que declarar en una clase es el constructor que en Python siempre se llama __init__ y dentro vamos a informar las variables que necesitará toda instancia de un árbol binario, en nuestro caso serán el valor del nodo, la rama izquierda (que será un ABB), la rama derecha (que será otro ABB) y por último el padre, y luego explicaré por qué.

Una peculiaridad de Python con respecto a otros lenguajes es que los atributos o variables de instancia se declaran dentro del constructor y no fuera. Además, como en el constructor he dado valores por defecto a tres parámetros, el único obligatorio es el de valor del nodo.

En un principio la solución tenía una clase nodo y otra la clase que estoy explicando pero finalmente dificultaba más que ayudaba a la resolución del problema, de modo que si os lo habéis preguntado, ya sabéis que intenté esa vía.

Continuando con los métodos definidos en la clase, insertar_izquierda e insertar_derecha lo único que hay que hacer es añadir a izquierda o derecha un nuevo árbol, que será el hijo, pero como hemos comentado antes hay que asegurarse de que cumpla la condición de un ABB, es decir, que sea menor o mayor el valor a insertar.

Si os preguntáis que pasará con los valores añadidos a posteriori pues no hay problema, ya que si a > b y b > c, entonces por transitividad a > c. Sí, sé que esto son matemáticas pero ¿nadie os advirtió que la programación y las matemáticas van de la mano? Otro punto importante en estos métodos es que en el padre se asigna el nodo en el que nos encontramos, en Python la forma de autoreferenciar un objeto es con self, de que se asigne self al padre. Hay que mencionar que cuando se define un método el primer argumento siempre es self, aunque no sea necesario.

Por último, el método devolver_padre, lo que se devuelve es el padre del nodo actual, de esto modo se puede decir que nuestro árbol es un árbol doblemente enlazado ya que desde un padre se puede ir a sus hijos que es lo normal y desde un hijo se puede ir al padre, lo cual no suele ser habitual, porque un árbol no se recorre en ese sentido.

Una vez dadas todas las explicaciones previas, vamos con la parte principal del código, es decir, nuestro ‘__main__‘. La primera dificultad a la que nos enfrentamos es leer los datos del árbol, en este caso la entrada es una lista de números separados por espacios donde el -1 indica que esa rama acaba. Es fundamental que tengamos este dato ya que en otro caso no sabríamos cómo finalizar las ramas o dónde terminan. También hay que tener en cuenta que en el orden en el que nos dan el árbol es en preorden, ya que primero nos dan la raíz, luego la parte izquierda y luego la derecha. Solo como curiosidad tenéis que saber que hay varias formas de recorrer un árbol y todas tienen su nombre.

Una vez que tenemos claro cómo nos dan los datos hay que pararse a pensar cómo vamos a movernos para construirlo, de modo que nada más empezar estamos en la raíz; el siguiente nodo es la rama izquierda y así hasta que nos encontremos con un -1, que tendremos que cambiarnos a la rama derecha y leer el valor de esa raíz, pero qué ocurre después que volvemos a rellenar la rama izquierda. Recordad que estamos recorriendo (o construyendo) el árbol en preorden, de modo que siempre que leamos un nodo lo siguiente será rellenar la rama izquierda, salvo que ésta no continúe.

Por último, el caso más conflictivo es que leamos una hoja, es decir, el árbol no continúa ni por la izquierda ni por la derecha o lo que es lo mismo, leemos dos -1 seguidos. Pues en ese caso, debemos subir un nivel, o visto de otro modo volver al nodo anterior, es decir, a nuestro padre. De ahí, que se haya creado un árbol doblemente enlazado, para así poder movernos rápidamente hacia arriba.

En cuanto a la respuesta que se devuelve, se utliza la variable de control es_bin_busqueda que indica en todo momento si estamos leyendo un árbol binario de búsqueda bien formado. La ventaja de hacerlo así es que si construyendo el árbol un nodo no puede ser insertado no tenemos que seguir leyendo ya que sabemos no es correcto.

Espero que hayáis aprendido con este ejercicio, a mí me sirvió para desempolvar mentalmente muchos conceptos y algoritmos de los años univesitarios.

Enlace del código

Enlace en aceptaelreto.com