Ejercicios Prácticos de Recursividad y Árboles Binarios en C++
Recursividad
Factorial
#include <iostream>
#include <Windows.h>
using namespace std;
int factorial (int r)
{
if (r==0)
return 1;
else
return r*factorial(r-1);
}
int main()
{
int n;
gotoxy (1,5); cout << "número del cual sacará";
cin >> n;
cout << "respuesta:" << n << endl;
system("pause");
}
Fibonacci
int fibonacci (int r)
{
if ((r==0) || (r==1))
return r;
else
return fibonacci (r-1) + fibonacci(r-2);
}
Torres de Hanói
#include <stdio.h>
#include <conio.h>
void hanoi(int n, int com, int aux, int fin);
void main(void){
clrscr();
char com='A';
char aux='B';
char fin='C';
int n;
printf("\nNúmero de discos: ");
scanf("%d", &n);
fflush(stdin);
printf("\n\nLos movimientos a realizar son: \n");
hanoi(n, com, aux, fin);
}
void hanoi(int n, int com, int aux, int fin){
if(n==1){
printf("%c->%c", com, fin);
}
else{
hanoi(n-1, com, fin, aux);
printf("\n%c->%c\n", com, fin);
hanoi(n-1, aux, com, fin);
}
}
Multiplicación Recursiva
Escriba una función recursiva que lleve por nombre multiplica() que realice la multiplicación de 2 enteros positivos de acuerdo a lo siguiente:
5*7 = 5 + 5*6
4*3 = 4 + 4*2
6*1 = 6
int multiplica(int a, int b)
{
if (b==1)
return a;
else
return a + multiplica(a, b-1);
}
Árboles
Los árboles son estructuras de datos de tipo jerarquía donde el primer nodo que llega o se inserta, siempre se considera la raíz.
Nodos Hoja: Es un nodo hoja cuando ya no tiene descendencia o hijos.
Los nodos menores que sus padres van a la izquierda.
Se dice que un árbol es binario si cada nodo tiene máximo 2 hijos.
- La ventaja principal de un árbol binario se da cuando hacemos la búsqueda de un elemento, porque va descartando por cada pregunta la mitad de toda una rama. Por lo tanto, se dice que la búsqueda de elementos es muy rápida, por lo que son muy eficientes.
Recorridos de un Árbol Binario
Son 3 tipos principales:
- Inorden (IZQ, RAÍZ, DER): Del menor al mayor.
- Preorden (RAÍZ, IZQ, DER): Raíz, luego izquierda, luego derecha.
- PostOrden (IZQ, DER, RAÍZ): Del mayor al menor.
Eliminación de Elementos
Para borrar un elemento de un árbol existen 2 formas:
El predecesor inmediato izquierdo se encuentra desplazándose a partir del nodo a borrar, una vez a la izquierda y tantas a la derecha como sea posible.
El predecesor inmediato derecho se encuentra desplazándose una vez a la derecha y tantas veces a la izquierda como sea posible a partir del nodo a borrar.
Si llega un elemento repetido, el programador decide en qué lado va a quedar ordenado.
Código Árbol
#include <iostream>
#include <windows.h>
#include <conio.h>
#include <stdio.h>
using namespace std;
class Arbol
{
private:
struct Nodo
{
char info;
Nodo *izq, *der;
};
Nodo *raiz;
public:
Arbol();
void insertar(char x);
void PrnInorden();
void Inorden(Nodo *p);
void PrnPsorden();
void Psorden(Nodo *p);
void PrnPreorden();
void Preorden(Nodo *p);
};
void gotoxy(int x, int y)
{
COORD coord;
coord.X = x;
coord.Y = y;
SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), coord);
}
Arbol::Arbol()
{
raiz = NULL;
}
void Arbol::Inorden(Nodo *p)
{
if (p != NULL)
{
Inorden(p->izq);
gotoxy(10, 10); cout << p->info;
gotoxy(10, 20); system("pause");
Inorden(p->der);
}
}
void Arbol::Psorden(Nodo *p)
{
if (p != NULL)
{
Psorden(p->izq);
Psorden(p->der);
gotoxy(10, 10);
cout << p->info;
gotoxy(10, 20); system("pause");
}
}
void Arbol::Preorden(Nodo *p)
{
if (p != NULL)
{
gotoxy(10, 10); cout << p->info;
gotoxy(10, 20); system("pause");
Preorden(p->izq);
Preorden(p->der);
}
}
void Arbol::insertar(char x)
{
Nodo *nn, *tep, *pnn;
nn = new Nodo;
nn->info = x;
nn->izq = NULL;
nn->der = NULL;
tep = raiz;
pnn = NULL;
while (tep != NULL)
{
pnn = tep;
if ((nn->info) > (tep->info))
tep = tep->der;
else
tep = tep->izq;
}
if (pnn == NULL)
raiz = nn;
else
if ((nn->info) > (pnn->info))
pnn->der = nn;
else
pnn->izq = nn;
}
void Arbol::PrnInorden()
{
Inorden(raiz);
}
void Arbol::PrnPsorden()
{
Psorden(raiz);
}
void Arbol::PrnPreorden()
{
Preorden(raiz);
}
int main()
{
Arbol z, x, y;
gotoxy(3, 5); cout << "Los elementos del Árbol en inorden son: ";
z.insertar('d');
z.insertar('a');
z.insertar('g');
z.PrnInorden();
gotoxy(3, 5); cout << "Los elementos del Árbol en Postorden son: ";
x.insertar('d');
x.insertar('a');
x.insertar('g');
x.PrnPsorden();
gotoxy(3, 5); cout << "Los elementos del Árbol en Preorden son: ";
y.insertar('d');
y.insertar('a');
y.insertar('g');
y.PrnPreorden();
return 0;
}