Desarrollar un programa para la administración de un árbol binario ordenado con información de tipo int.
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct nodo {
int info;
struct nodo *izq;
struct nodo *der;
};
struct nodo *raiz=NULL;
void insertar(int x)
{
struct nodo *nuevo;
nuevo = malloc(sizeof(struct nodo));
nuevo->info = x;
nuevo->izq = NULL;
nuevo->der = NULL;
if (raiz == NULL)
raiz = nuevo;
else
{
struct nodo *anterior, *reco;
anterior = NULL;
reco = raiz;
while (reco != NULL)
{
anterior = reco;
if (x < reco->info)
reco = reco->izq;
else
reco = reco->der;
}
if (x < anterior->info)
anterior->izq = nuevo;
else
anterior->der = nuevo;
}
}
void imprimirPre(struct nodo *reco)
{
if (reco != NULL)
{
printf("%i-",reco->info);
imprimirPre(reco->izq);
imprimirPre(reco->der);
}
}
void imprimirEntre(struct nodo *reco)
{
if (reco != NULL)
{
imprimirEntre(reco->izq);
printf("%i-",reco->info);
imprimirEntre(reco->der);
}
}
void imprimirPost(struct nodo *reco)
{
if (reco != NULL)
{
imprimirPost(reco->izq);
imprimirPost(reco->der);
printf("%i-",reco->info);
}
}
void borrar(struct nodo *reco)
{
if (reco != NULL)
{
borrar(reco->izq);
borrar(reco->der);
free(reco);
}
}
int main()
{
insertar(100);
insertar(50);
insertar(25);
insertar(75);
insertar(150);
printf("Impresion preorden: ");
imprimirPre(raiz);
printf("\n\n");
printf("Impresion entreorden: ");
imprimirEntre(raiz);
printf("\n\n");
printf("Impresion postorden: ");
imprimirPost(raiz);
borrar(raiz);
getch();
return 0;
}
La declaración del nodo es:
struct nodo {
int info;
struct nodo *izq;
struct nodo *der;
};
Hay dos punteros, uno que apunta al subárbol izquierdo y otro que apunta al subárbol derecho.
En la función insertar creamos un nodo y disponemos los punteros izq y der a NULL, guardamos la información que llega en el nodo creado.
Si el árbol está vacío, apuntamos raíz al nodo creado; en caso de no estar vacío, dentro de una estructura repetitiva vamos comparando x con la información del nodo, si x es mayor a la del nodo descendemos por el subárbol derecho en caso contrario descendemos por el subárbol izquierdo.
Cuando se encuentra un subárbol vacío insertar el nodo en dicho subárbol. Para esto llevamos un puntero anterior dentro del while:
void insertar(int x)
{
struct nodo *nuevo;
nuevo = malloc(sizeof(struct nodo));
nuevo->info = x;
nuevo->izq = NULL;
nuevo->der = NULL;
if (raiz == NULL)
raiz = nuevo;
else
{
struct nodo *anterior, *reco;
anterior = NULL;
reco = raiz;
while (reco != NULL)
{
anterior = reco;
if (x < reco->info)
reco = reco->izq;
else
reco = reco->der;
}
if (x < anterior->info)
anterior->izq = nuevo;
else
anterior->der = nuevo;
}
}
La funcióno imprimirPre recibe como parámetro la dirección del nodo a visitar (desde la main le enviamos raiz):
void imprimirPre(struct nodo *reco)
{
if (reco != NULL)
{
printf("%i-",reco->info);
imprimirPre(reco->izq);
imprimirPre(reco->der);
}
}
La función es recursiva, lo primero que verifica con un if si reco está apuntando a un nodo (esto es verdad si reco es distinto a NULL), en caso afirmativo ingresa al bloque del if y realiza:
- Visitar la raiz.
- Recorrer el subárbol izquierdo en pre-orden.
- Recorrer el subárbol derecho en pre-orden.
La visita en este caso es la impresión de la información del nodo y los recorridos son las llamadas recursivas pasando las direcciones de los subárboles izquierdo y derecho.
Los algoritmos de los recorridos en entreorden y postorden son similares. La diferencia es que la visita la realizamos entre las llamadas recursivas en el recorrido en entre orden:
void imprimirEntre(struct nodo *reco)
{
if (reco != NULL)
{
imprimirEntre(reco->izq);
printf("%i-",reco->info);
imprimirEntre(reco->der);
}
}
y por último en el recorrido en postorden la visita la realizamos luego de las dos llamadas recursivas:
void imprimirPost(struct nodo *reco)
{
if (reco != NULL)
{
imprimirPost(reco->izq);
imprimirPost(reco->der);
printf("%i-",reco->info);
}
}
En la función borrar debemos eliminar todos los nodos que quedan en el árbol, para esto debemos recorrer el árbol en post orden y en la visita eliminar el nodo:
void borrar(struct nodo *reco)
{
if (reco != NULL)
{
borrar(reco->izq);
borrar(reco->der);
free(reco);
}
}
Confeccionar un programa que permita insertar un entero en un árbol binario ordenado verificando que no se encuentre previamente dicho número.
Desarrollar las siguientes funcionalidades:
1 - Retornar la cantidad de nodos del árbol.
2 - Retornar la cantidad de nodos hoja del árbol.
3 - Imprimir en entre orden.
4 - Imprimir en entre orden junto al nivel donde se encuentra dicho nodo.
5 - Retornar la altura del árbol.
6 - Imprimir el mayor valor del árbol.
7 - Borrar el nodo menor del árbol.
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct nodo {
int info;
struct nodo *izq;
struct nodo *der;
};
struct nodo *raiz=NULL;
int existe(int x)
{
struct nodo *reco = raiz;
while (reco != NULL)
{
if (x == reco->info)
return 1;
else
if (x>reco->info)
reco = reco->der;
else
reco = reco->izq;
}
return 0;
}
void insertar(int x)
{
if (!existe(x))
{
struct nodo *nuevo;
nuevo = malloc(sizeof(struct nodo));
nuevo->info = x;
nuevo->izq = NULL;
nuevo->der = NULL;
if (raiz == NULL)
raiz = nuevo;
else
{
struct nodo *anterior, *reco;
anterior = NULL;
reco = raiz;
while (reco != NULL)
{
anterior = reco;
if (x < reco->info)
reco = reco->izq;
else
reco = reco->der;
}
if (x < anterior->info)
anterior->izq = nuevo;
else
anterior->der = nuevo;
}
}
}
void cantidad(struct nodo *reco,int *cant)
{
if (reco != NULL)
{
(*cant)++;
cantidad(reco->izq, cant);
cantidad(reco->der, cant);
}
}
void cantidadNodosHoja(struct nodo *reco,int *cant)
{
if (reco != NULL) {
if (reco->izq == NULL && reco->der == NULL)
(*cant)++;
cantidadNodosHoja(reco->izq,cant);
cantidadNodosHoja(reco->der,cant);
}
}
void imprimirEntreConNivel(struct nodo *reco, int nivel)
{
if (reco != NULL) {
imprimirEntreConNivel(reco->izq, nivel + 1);
printf("%i(%i) - ", reco->info, nivel);
imprimirEntreConNivel(reco->der, nivel + 1);
}
}
void retornarAltura(struct nodo *reco, int nivel,int *altura)
{
if (reco != NULL)
{
retornarAltura(reco->izq, nivel + 1,altura);
if (nivel>*altura)
*altura = nivel;
retornarAltura(reco->der, nivel + 1,altura);
}
}
void mayorValor()
{
if (raiz != NULL)
{
struct nodo *reco = raiz;
while (reco->der != NULL)
reco = reco->der;
printf("Mayor valor del arbol:%i\n", reco->info);
}
}
void borrarMenor()
{
if (raiz != NULL) {
struct nodo *bor;
if (raiz->izq == NULL)
{
bor = raiz;
raiz = raiz->der;
free(bor);
}
else {
struct nodo *atras = raiz;
struct nodo *reco = raiz->izq;
while (reco->izq != NULL)
{
atras = reco;
reco = reco->izq;
}
atras->izq = reco->der;
free(reco);
}
}
}
void imprimirEntre(struct nodo *reco)
{
if (reco != NULL)
{
imprimirEntre(reco->izq);
printf("%i - ",reco->info);
imprimirEntre(reco->der);
}
}
void borrar(struct nodo *reco)
{
if (reco != NULL)
{
borrar(reco->izq);
borrar(reco->der);
free(reco);
}
}
int main()
{
int cant;
int altura=0;
insertar(100);
insertar(50);
insertar(25);
insertar(75);
insertar(150);
printf("Impresion entreorden: ");
imprimirEntre(raiz);
printf("\n");
cant=0;
cantidad(raiz,&cant);
printf("Cantidad de nodos del arbol:%i\n", cant);
cant=0;
cantidadNodosHoja(raiz,&cant);
printf("Cantidad de nodos hoja:%i\n", cant);
printf("Impresion en entre orden junto al nivel del nodo:");
imprimirEntreConNivel(raiz,1);
printf("\n");
altura=0;
retornarAltura(raiz,1,&altura);
printf("Artura del arbol:%i\n",altura);
mayorValor();
borrarMenor();
printf("Luego de borrar el menor:");
imprimirEntre(raiz);
borrar(raiz);
getch();
return 0;
}
Para verificar si existe un elemento de información en el árbol disponemos un puntero reco en el nodo apuntado por raiz. Dentro de un while verificamos si la información del parámetro coincide con la información del nodo apuntado por reco, en caso afirmativo salimos de la función retornando un 1, en caso contrario si la información a buscar es mayor a la del nodo procedemos a avanzar reco con la dirección del subárbol derecho:
int existe(int x)
{
struct nodo *reco = raiz;
while (reco != NULL)
{
if (x == reco->info)
return 1;
else
if (x>reco->info)
reco = reco->der;
else
reco = reco->izq;
}
return 0;
}
Para retornar la cantidad de nodos del árbol le enviamos a la función la dirección del nodo a visitar y la dirección de una variable entera para que la incremente:
void cantidad(struct nodo *reco,int *cant)
{
if (reco != NULL)
{
(*cant)++;
cantidad(reco->izq, cant);
cantidad(reco->der, cant);
}
}
Para imprimir todos los nodos en entre orden junto al nivel donde se encuentra planteamos una función recursivo que llegue la referencia del nodo a imprimir junto al nivel de dicho nodo.
Cada vez que descendemos un nivel le pasamos la referencia del subárbol respectivo junto al nivel que se encuentra dicho nodo:
void imprimirEntreConNivel(struct nodo *reco, int nivel)
{
if (reco != NULL) {
imprimirEntreConNivel(reco->izq, nivel + 1);
printf("%i(%i) - ", reco->info, nivel);
imprimirEntreConNivel(reco->der, nivel + 1);
}
}
Para obtener la altura del árbol procedemos a enviarle la dirección de una variable donde almacenamos el máximo nivel visitado:
void retornarAltura(struct nodo *reco, int nivel,int *altura)
{
if (reco != NULL)
{
retornarAltura(reco->izq, nivel + 1,altura);
if (nivel>*altura)
*altura = nivel;
retornarAltura(reco->der, nivel + 1,altura);
}
}
Para imprimir el mayor valor del árbol debemos recorrer siempre por derecha hasta encontrar un nodo que almacene NULL en el puntero der:
void mayorValor()
{
if (raiz != NULL)
{
struct nodo *reco = raiz;
while (reco->der != NULL)
reco = reco->der;
printf("Mayor valor del arbol:%i\n", reco->info);
}
}
Para borrar el menor valor del árbol lo primero que comprobamos es si el subárbol izquierdo es nulo luego el menor del árbol es el nodo apuntado por raiz, en este caso disponemos un puntero auxiliar bor que apunte a raiz, luego avanzamos a raiz y finamente borramos el nodo que era raiz hasta este momento. Luego si el subárbol izquierdo no está vacío procedemos a descender siempre por la izquierda llevando un puntero en el nodo anterior. Cuando llegamos al nodo que debemos borrar procedemos a enlazar el puntero izq del nodo que se encuentra en el nivel anterior con la referencia del subárbol derecho del nodo a borrar (reco queda apuntantado al nodo a borrar):
void borrarMenor()
{
if (raiz != NULL) {
struct nodo *bor;
if (raiz->izq == NULL)
{
bor = raiz;
raiz = raiz->der;
free(bor);
}
else {
struct nodo *atras = raiz;
struct nodo *reco = raiz->izq;
while (reco->izq != NULL)
{
atras = reco;
reco = reco->izq;
}
atras->izq = reco->der;
free(reco);
}
}
}