Recursión y recorrido en arboles binarios

Recursión y recorrido en arboles binarios

Prof. Ana Lorena Valerio

Chiste

Concepto de Recursividad

Es un algoritmo que expresa la solución de un problema en términos de una llamada a sí mismo.

Lo primero para entender la recursividad, es entender la recursividad".

Diseño recursivo

Todo algoritmo recursivo tendrá dos casos bien diferenciados:

Diseño recursivo

void funcionRecursiva( int parametro1){ int variableLocal1= 0; if(parametro1 == 5) return; //acceder al top de la pila y realizar un pop //antes de la recursividad cout<<"nAntes de la recursividad. "<<variableLocal!; variableLocal1++; funcionRecursiva(parametro1 + 1); //push en la pila, los parámetros y variable //después de la recursividad cout<<"InDespues de la recursividad "<<variableLocal1; return; //acceder al top de la pila y realizar un pop }

La mecánica de la recursividad está basada en una “pila”.Cuando un método recursivo se está ejecutando se crea en la memoria de la computadora una pila donde se almacenan los valores de los parámetros y de las variables locales del método.

Diseño recursivo

void funcionRecursiva( int parametro1){ int variableLocal1= 0; if(parametro1 == 5) return; //acceder al top de la pila y realizar un pop //antes de la recursividad cout<<"nAntes de la recursividad. "<<variableLocal!; variableLocal1++; funcionRecursiva(parametro1 + 1); //push en la pila, los parámetros y variable //después de la recursividad cout<<"InDespues de la recursividad "<<variableLocal1; return; //acceder al top de la pila y realizar un pop }

La mecánica de la recursividad está basada en una “pila”.Cuando un método recursivo se está ejecutando se crea en la memoria de la computadora una pila donde se almacenan los valores de los parámetros y de las variables locales del método.

Diseño recursivo

void funcionRecursiva( int parametro1){ int variableLocal1= 0; if(parametro1 == 5) return; //acceder al top de la pila y realizar un pop //antes de la recursividad cout<<"nAntes de la recursividad. "<<variableLocal!; variableLocal1++; funcionRecursiva(parametro1 + 1); //push en la pila, los parámetros y variable //después de la recursividad cout<<"InDespues de la recursividad "<<variableLocal1; return; //acceder al top de la pila y realizar un pop }

La mecánica de la recursividad está basada en una “pila”.Cuando un método recursivo se está ejecutando se crea en la memoria de la computadora una pila donde se almacenan los valores de los parámetros y de las variables locales del método.

Diseño recursivo

Si el método es función también se guarda en la pila el valor que adquiere la misma.

• Para cada llamada del método se almacenan en la pila los nuevos valores de los parámetros y de las variables locales, creándose un nuevo “registro de activación”.

Diseño recursivo

• Al terminar una llamada al método (return), es decir, cuando se cumple la definición base, se libera (sale) el registro de activación que se encuentra en el tope de la pila.

• De esta forma es como puede “recordar” qué valores tenían los parámetros y las variables locales en la llamada anterior.

Insertar ordenadoen árbol binario usando recursividad

//esta función inserta ordenado en el arbol binario //devuelve el primero del árbol struct nodo * insertar (int x, struct nodo *arbol){ if(arbol == NULL){ return arbol = new nodo(x); } else{ if(x < arbol->num) //se debe insertar a la izqulerda { arbol->izq = insertar(x,arbol->izq); } else if(x > arbol->num) // se debe insertar a la derecha { arbol->der = insertar(x,arbol->der); } else{ //entonces es igual cout<<"No insertamos datos repetidos.\n"; } } return arbol; }

Recorrido en-Orden de un árbol binario

izq-raiz-der

void enOrden(arbolB * raiz){ if(raiz == NULL) return; enOrden(raiz->izq); cout<<raiz->num<<", "; enOrden(raiz->der); return; }

Raiz=

nodo

Raiz=

nodo

Raiz=

nodo

10

Recorrido en-Orden de un árbol binario

izq-raiz-der

Raiz=

nodo

void enOrden(arbolB * raiz){ if(raiz == NULL) return; enOrden(raiz->izq); cout<<raiz->num<<", "; enOrden(raiz->der); return; }

Raiz=

nodo

Raiz=

nodo

10

Recorrido en-Orden de un árbol binario

izq-raiz-der

Raiz=

nodo

void enOrden(arbolB * raiz){ if(raiz == NULL) return; enOrden(raiz->izq); cout<<raiz->num<<", "; enOrden(raiz->der); return; }

Raiz=

nodo

Raiz=

nodo

10

Recorrido en-Orden de un árbol binario

izq-raiz-der

Raiz=

nodo

void enOrden(arbolB * raiz){ if(raiz == NULL) return; enOrden(raiz->izq); cout<<raiz->num<<", "; enOrden(raiz->der); return; }

Raiz=

nodo

Raiz=

nodo

10

Recorrido en-Orden de un árbol binario

izq-raiz-der

Raiz=

nodo

14

void enOrden(arbolB * raiz){ if(raiz == NULL) return; enOrden(raiz->izq); cout<<raiz->num<<", "; enOrden(raiz->der); return; }

Raiz=

nodo

22

Raiz=

nodo

10

10

Recorrido en-Orden de un árbol binario

izq-raiz-der

Raiz=

nodo

14

void enOrden(arbolB * raiz){ if(raiz == NULL) return; enOrden(raiz->izq); cout<<raiz->num<<", "; enOrden(raiz->der); return; }

Raiz=

nodo

22

Raiz=

nodo

10

10

14

22