Generador de árboles binarios

propuesto por josejuan

Crear una función que genere aleatoriamente árboles binarios con claves únicas de números naturales en sus nodos, y de los cuales, lo único que nos interesa son las listas obtenidas al procesar el árbol de forma Pre, In y Post orden.

Enunciado
Crear una función

arbolAleatorio(maxNiveles, bifurcacionP)

que devuelva tres listas de números naturales:

preorden
inorden
postorden

que contienen respectivamente las listas de números del mismo árbol binario con claves únicas en sus nodos (y hojas, en las que las claves son números naturales) al ser procesado de forma preorden, inorden y postorden.

Como el árbol se genera aleatoriamente, las claves en cada nodo pueden ser cualquier número natural (n = 1, 2, 3, 4, ...), pero cada clave (cada número natural) sólo puede aparecer una vez en todo el árbol.

Dado un nodo cualquiera del árbol, la probabilidad de que éste se expanda aleatoriamente es:

bifurcacionP si el nivel del nodo es inferior a maxNivel
0 en otro caso

Por ejemplo, llamar a la función con los parámetros

arbolAleatorio(5, 0.999)

podría ser (recuerda que se genera aleatoriamente)

preorden = [1]
inorden = [1]
postorden = [1]

pero eso sólo ocurrirá una de cada mil veces.

Ver todo el enunciado

Preguntas sobre el desafío
  • No me quedó claro que es bifurcacionP, ¿podría explicarlo mejor?

    Un árbol binario es aquel en el que cada nodo puede expandirse por dos ramas, comúnmente izquierda y derecha. Ahora bien, si un nodo no se expande por ninguna de las ramas se le suele denominar hoja; pero también puede ocurrir que sólo se expanda por la izquierda o sólo por la derecha. A la hora de generar el árbol, debe usarse la probabilidad "bifurcacionP" (comprendida entre 0 y 1) para decidir si expandir una rama. Así, con probabilidad (1 - bifurcacionP)^2 un nodo será una hoja. La forma habitual de decidir si expandir o no una rama sería "Si Aleatorio() < bifurcacionP Entonces Bifurcar".

Plantea tu pregunta

4 Soluciones

Dar mi solución

Dar mi solución