Ejercicio examen arboles binarios

Iniciado por alhuertis, 19 Mayo 2015, 19:18 PM

0 Miembros y 2 Visitantes están viendo este tema.

alhuertis

Dado un árbol binario, en cuya raíz se encuentra situado un tesoro y cuyos nodos internos pueden
contener un dragón o no contener nada, se pide diseñar un algoritmo que nos indique la hoja del arbol
cuyo camino hasta la raíz tenga el menor numero de dragones. En caso de que existan varios caminos
con el mismo numero de dragones, el algoritmo devolver´a el que se encuentre m´as a la izquierda de todos
ellos.
Para ello implementar una función que reciba un árbol binario cuyos nodos almacenan enteros:

1. La raíz contiene el entero 0, que representa al tesoro.
2. Los nodos internos contienen el entero 1 para indicar que en el nodo hay un dragón o el entero 2
para indicar que no hay dragón.
3. En cada hoja se almacena un entero mayor o igual a 3 que no puede estar repetido.
y devuelva el entero de la hoja del camino seleccionado. El árbol tiene como mínimo un nodo raíz y un
nodo hoja diferente de la raíz.
Por ejemplo, dado el siguiente árbol (segundo caso de prueba mostrado en el ejemplo) el algoritmo
devolver´a el entero 4.

No puedo subir una foto del árbol de ejemplo, pero con que alguien me diga con palabras que puedo hacer para recorrer todas las ramas y saber cual es el camino con menos dragones se lo agradecería.

Un saludo!

DarK_FirefoX

#1
alhuertis, aqui no se resuelven ejercicios, tienes que pensar y comenzar a hacer tus ejercicios y cuando te atasques, hacer alguna pregunta en concreto, pero no esperes que hagamos los ejercicios por ti.

Puedes ir pensando en hacer un recorrido en pre-orden para recorrer el arbol. Vaya puedes ir comenzando por ahí. Lo demás es cuestión de comprobar y guardar los datos

Salu2s

alhuertis

Lo se lo se, si no quiero que nadie me lo deje hecho, siemplemente que no se por donde tirar para empezar y quería ver si alguien me indicaba con palabras alguna forma de hacerlo o entenderlo.

Gracias de todas formas tio  ::)

Saludos

DarK_FirefoX

Ya te había dejado una idea, aquí te vá más completa:

Utilizando un recorrido en pre-orden recursivamente o iterativamente puedes ir contando la cantidad de "dragones" hasta llegar a una hoja. Esa hoja la almacenas en algún lado y vas llevando el control de la cantidad de "dragones" en el camino a esa hoja, luego sigues el recorrido de todo el arbol. Si encuentras una hoja con una cantidad de "dragones" hacia ella menor, pues la cambias por la que habias guardado, junto con la cantidad de dragones hasta esa hoja.

Salu2s. Espero que te ayude.

alhuertis

ok tio muchas gracias, algo asi quería, voy a ver si con estas indicaciones consigo que me salga!

Gracias!  ;D