INFORME 3 DE ESTRUCTURA DE DATOS Y ALGORITMOS

INFORME 3 DE ESTRUCTURA DE DATOS Y ALGORITMOS

Implementación de Árbol binario y Max Heap:

Christopher Arancibia  201510011-k

Carlos Martínez 201510015-2

Nicolás González  201510003-9

Pregunta 1 (Árbol Binario):

pnodo creanodo(int valor):

En esta  función se  crea un nodo nuevo para ser utilizado en las otras funciones, en el desarrollo, se le da al nodo el valor que ingresó el usuario y dos punteros que se mandan a NULL, uno a la derecha y otro a la izquierda.

pnodo insert(int valor, pnodo árbol):

En esta función insert , que se ingresa como argumentos el valor que se desea insertar, y el árbol determinado a cual se agregará, primero se llama a la función creanodo para crea el nodo del elemento, luego  siempre y cuando el árbol exista se ingresara al ciclo while sin condiciones, ya que en el caso contrario se ingresaría el nuevo nodo inmediatamente como raíz. En el While  se analizara si el elemento  a ingresar será a la derecha o a la izquierda de su antecesor, en el caso que este los dos ocupados se cambiará el valor de la variable árbol a la dirección que le corresponda  respectivamente, cuando se agregue el nuevo elemento a su posición, se saldrá del ciclo con un break para que finalmente se retorne el árbol con los respectivos cambios.

Ejemplo:

 Si se ingresa como argumento el valor 6 y el árbol en que estamos trabajando es:

[pic 1]

[pic 2][pic 3][pic 4][pic 5]

[pic 6][pic 7]

[pic 8][pic 9]

bool search(int valor, pnodo arbol, int nivel):

La función search, busca  y retorna si el elemento que fue ingresado por el usuario se encuentra o no en el árbol mediante a reiteraciones de esta. Además la función indica en qué nivel se encuentra y las etapas con los respectivos valores en cual buscó. Primero se analiza si el árbol  que se ingresó como argumento es NULL, al ser así se retornará false,  sino ingresará  a otro if, el cual compara si el elemento en el  cual se encuentra recorriendo  es igual al valor que se busca, en el caso que sí sean iguales se imprimirá en la pantalla un mensaje de afirmación  y retornará true. Si no entra en ninguno de los dos if, se llamará nuevamente a la función search, pero se cambia el valor de la variable árbol, primero el siguiente elemento que está apuntando  hacia la izquierda y luego hacia la derecha. Como la función trabaja de una manera reiterativa, se pude recorrer todos los elementos  del árbol (de izquierda a derecha) permitiendo buscar el elemento deseado. Si no lo encuentra dentro de todas las reiteraciones (es decir que todas retornarían false) si imprime en la pantalla un mensaje negativo de la búsqueda. En cada reiteración se le suma uno a  la variable nivel que entra como argumento para indicar el nivel y el nodo en que estamos recorriendo.

Ejemplo:

 Si se ingresa como argumento el valor 12 y el árbol en que estamos trabajando es :

[pic 10][pic 11][pic 12]

[pic 13][pic 14][pic 15][pic 16][pic 17][pic 18]

void mostrar_arbol(pnodo arbol)

La función mostrar_arbol nos permite ver como están distribuidos en forma Pre orden travesal los elementos del árbol que se ingresa como argumento, también de una manera reiterativa como la función anterior.  Se irán mostrando en la pantalla  cada elemento  desde la izquierda hacia la derecha  del árbol( a partir de la raíz), cuando llegue al siguiente del último elemento de la ramificación, el cual sería NULL , la función retornará false, por lo tanto vuelve al nodo  anterior pero recorriendo ahora su derecha, y así reiteradamente hasta que se recorra por completo.

Ejemplo:

Si el árbol que se ingresa como argumento es el de los ejemplos anteriores, en la pantalla se imprimiría:

[pic 19]

Int menú()

La funcion extra "menu" imprime texto en pantalla y hace el usuario escoger una de las opciones mostradas, si el valor ingresado por el usuario no corresponde a alguna de las opciones, se le pedirá volver a ingresar un valor. Al final retornara la opción escogida (ya validada anteriormente en un bucle).

int main()

En el main se creará un árbol predeterminado, este se compondrá  por 10 elementos(los cuales serán ingresados por el usuario)  con dos punteros cada uno, uno hacia la derecha y otro a la izquierda, luego se le mostrara al usuario un menú con las distintas funciones(insertar o buscar), de las cuales deberá escoger una para implementar hacia el árbol o cerrar el programa.

...