Árbol monodistante

17 abril 2007

Un árbol monodistante de orden N es un árbol binario de números enteros en el que la suma de los valores de los nodos de cada camino que va desde la raíz a un nodo hoja es igual a N.

Ejemplo de árbol monodistante de orden 15:

arbol monodistante de orden 15

En un ejercicio de clase se nos pide que diseñemos una función que compruebe si un árbol es monodistante o no.

El prototipo de la función puede ser el siguiente:

func esMonodistante(a:BinaryTree; n: Natural) dev b:Boolean

La función tiene como entrada un arbol binario (BinaryTree) y un natural que indica el orden y devuelve cierto si el árbol es monodistante o falso en cualquier otro caso.

Siempre que vayamos a trabajar con árboles conviene pensar en una solución recursiva. El caso base de esta función recursiva podría ser que el árbol estuviera vacio o que el árbol sólo tuviera una hoja. En el resto de casos sólo tendríamos que comprobar que el subarbol derecho y el subarbol izquierdo son monodistantes haciendo una llamada recursiva y decrementando el orden del árbol.

Mi solución recursiva es esta:

func esMonodistante (a:BinaryTree, n:Natural) dev (b:Logico)
alg
	si a.isEmpty():   //el árbol está vacio
		b := cierto
	| a.isLeaf():     //el árbol es una hoja
		b := ( a.getRoot() = n )
	otras
		b := (esMonodistante(a.left() , n-a.getRoot())
		    Y esMonodistante(a.right(), n-a.getRoot()) )
	fsi
fin

Por si os sirve de algo se trata del Ejercicio 19 del Boletín de Árboles de la asignatura Estructuras de Datos y Algoritmos

:wq

5 Responses to “Árbol monodistante”

  1. alidhaey Says:

    A ver, a ver, este arbol monodistante que aplicaciones practicas tendria?

    Quiero ejemplos! xDDD

    PD: Cuidado, no estudies demasiado. que al final los sesos se vuelven agua.


  2. Por ejemplo, tenemos que pasar 15 pruebas a varias máquinas (arranque en red, instalación, aceleración, rendimiento, etc). Si se detecta un error en una prueba se avisa del error al proveedor de la máquina para que haga las modificaciones pertinentes que lo subsanen.

    Al final tendríamos un árbol n-ario donde cada nodo indica el número de pruebas satisfactorias antes de un error.

    Si el árbol es monodistante significaría que todas las máquinas han pasado las 15 pruebas.

    Habría que modificar el algoritmo para que trabajara con árboles n-arios en vez de binarios comprobando todas las ramas en vez de las 2 ramas.

    La probabilidad de aplicar un algoritmo de este tipo en la vida real es baja pero de vez en cuando está bien pensar en recursivo🙂

  3. Vio Says:

    Discrepo contigo en el caso base, si el arbol es vacío, debe devolver falso, ya que no contiene nada, y la suma de su nodo sería 0 no N.
    Mis dos bits.
    un abrazo.


  4. Efectivamente. Añade la cláusula de que un árbol vacío es monodistante por definición.

    A mi me sigue sin quedar del todo claro pero sin esa cláusula el algoritmo no cumple su cometido ya que daría falso cuando se llama a cualquier subárbol binario no completo.

  5. Inma Says:

    Hola Antonio, quería saber una aplicación para los árboles monodistantes n-arios, que no sea tan abstracta como la de los ordenadores. Estoy pensando en algo relacionado con la medicina, pero no sé si estoy entendiendo bien la representación del árbol. Muchas gracias


Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: