#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
typedef struct nodo
{
int numero;
struct nodo *derecho;
struct nodo *izquierdo;
}*ptr;
void Insertar(ptr *nodo, int dato);
void Eliminar_nodo(ptr *a, int dato);
int Buscar(ptr nodo, int dato);
int EsHoja(ptr h);
int Num_Nodos(ptr nodo, int* c);
int Altura_Arbol(ptr nodo, int *altura);
int Nivel_Nodo(ptr nodo, int dat);
void InOrden(ptr nodo, void (*func)(int*));
void PreOrden(ptr nodo, void (*func)(int*));
void PostOrden(ptr nodo, void (*func)(int*));
void Eliminar_Arbol(ptr *nodo);
void auxContador(ptr nodo, int*);
void auxAltura(ptr nodo, int, int*);
void Mostrar(int *a);
int Vacio(ptr r);
int main()
{
ptr Arbol = NULL;
int i, num, ndatos, opcion;
do
{
printf("\n");
printf("\n****** arbol ********");
printf("\n1. Insertar arbol *");
printf("\n2. Nivel nodo *");
printf("\n3. Buscar nodo *");
printf("\n4. Eliminar nodo *");
printf("\n5. Eliminar árbol *");
printf("\n6. Salir *");
printf("\n*********************");
printf("\n\n\n");
printf(" Elija opción ");
scanf("%d",&opcion);
switch (opcion)
{
case 1: system("cls");
printf("\n Indique cuantos datos desea insertar ");
scanf("%d",&ndatos);
system("cls");
printf("\n Introduzca %d datos\n\n", ndatos);
for(i=1; i<=ndatos; i++)
{
scanf("%d",&num);
Insertar(&Arbol, num);
}
system("cls");
printf("\n Numero nodos ----> %d ", Num_Nodos(Arbol, &num));
printf("\n\n Altura arbol ----> %d ", Altura_Arbol(Arbol, &num));
printf("\n\n InOrden ----> ");
InOrden(Arbol, Mostrar);
printf("\n\n PreOrden ----> ");
PreOrden(Arbol, Mostrar);
printf("\n\n PostOrden ----> ");
PostOrden(Arbol, Mostrar);
printf("\n\n\n\n\n\n\n\n");
system("pause");
system("cls");
break;
case 2: system("cls");
printf("\n\n Introduzca nodo ");
scanf("%d", &num);
system("cls");
printf("\n\n Nivel de %d ----> %d\n",num, Nivel_Nodo(Arbol, num));
printf("\n\n\n\n\n\n\n\n");
system("PAUSE");
system("cls");
break;
case 3: system("cls");
printf("\n Introduzca dato a buscar ");
scanf("%d", &num);
system("cls");
Buscar(Arbol, num);
printf("\n\n\n\n\n\n\n\n");
system("PAUSE");
system("cls");
break;
case 4: system("cls");
printf("\n Introduzca dato a eliminar ");
scanf("%d", &num);
system("cls");
Eliminar_nodo(&Arbol, num);
printf("\n\n Eliminado ----> %d ",num);
printf("\n\n InOrden ----> ");
InOrden(Arbol, Mostrar);
printf("\n\n Número nodos ----> %d", Num_Nodos(Arbol, &num));
printf("\n\n Altura árbol ----> %d", Altura_Arbol(Arbol, &num));
printf("\n\n\n\n\n\n\n\n");
system("PAUSE");
system("cls");
break;
case 5: system("cls");
Eliminar_Arbol(&Arbol);
printf("\n ARBOL ELIMINADO");
printf("\n\n\n\n\n\n\n\n");
system("PAUSE");
system("cls");
break;
case 6: break;
default: system("cls");
break;
}
} while (opcion!=6);
return 0;
}
int Vacio(ptr r)
{
return r==NULL;
}
void Insertar(ptr *a, int dato){
ptr padre = NULL;
ptr actual = *a;
while(!Vacio(actual) && dato != actual->numero) {
padre = actual;
if(dato < actual->numero)
actual = actual->izquierdo;
else if(dato > actual->numero)
actual = actual->derecho;
}
if(!Vacio(actual))
return;
if(Vacio(padre)) {
*a = (ptr)malloc(sizeof(struct nodo));
(*a)->numero = dato;
(*a)->izquierdo = (*a)->derecho = NULL;
}
else if(dato < padre->numero) {
actual = (ptr)malloc(sizeof(struct nodo));
padre->izquierdo = actual;
actual->numero = dato;
actual->izquierdo = actual->derecho = NULL;
}
else if(dato > padre->numero) {
actual = (ptr)malloc(sizeof(struct nodo));
padre->derecho = actual;
actual->numero = dato;
actual->izquierdo = NULL;
actual->derecho = NULL;
}
}
void Eliminar_nodo(ptr *a, int dato){
ptr padre = NULL;
ptr actual;
ptr nodo;
int aux;
actual = *a;
while(actual!=NULL) {
if(dato == actual->numero) {
if(EsHoja(actual)) {
if(padre)
if(padre->derecho == actual)
padre->derecho = NULL;
else if(padre->izquierdo == actual)
padre->izquierdo = NULL;
free(actual);
actual = NULL;
}else {
padre = actual;
if(actual->derecho) {
nodo = actual->derecho;
while(nodo->izquierdo) {
padre = nodo;
nodo = nodo->izquierdo;}
}else {
nodo = actual->izquierdo;
while(nodo->derecho) {
padre = nodo;
nodo = nodo->derecho;}
}
aux = actual->numero;
actual->numero = nodo->numero;
nodo->numero = aux;
actual = nodo;}
}else {
padre = actual;
if(dato > actual->numero)
actual = actual->derecho;
else if(dato < actual->numero)
actual = actual->izquierdo;}
}
}
void InOrden(ptr nodo, void (*func)(int*))
{
if(nodo->izquierdo)
InOrden(nodo->izquierdo, func);
func(&(nodo->numero));
if(nodo->derecho)
InOrden(nodo->derecho, func);
}
void PreOrden(ptr nodo, void (*func)(int*))
{
func(&nodo->numero);
if(nodo->izquierdo)
PreOrden(nodo->izquierdo, func);
if(nodo->derecho)
PreOrden(nodo->derecho, func);
}
void PostOrden(ptr nodo, void (*func)(int*))
{
if(nodo->izquierdo)
PostOrden(nodo->izquierdo, func);
if(nodo->derecho)
PostOrden(nodo->derecho, func);
func(&nodo->numero);
}
int Buscar(ptr nodo, int dato)
{
ptr actual = nodo;
while(actual!= NULL)
{
if(dato == actual->numero)
{
printf("\n %d EXISTE", dato);
return TRUE;
}
else if(dato < actual->numero)
actual = actual->izquierdo;
else if(dato > actual->numero)
actual = actual->derecho;
}
printf("\n %d NO EXISTE", dato);
return FALSE;
}
int Nivel_Nodo(ptr nodo, int dato)
{
int altura = 0;
ptr actual = nodo;
while(actual != NULL)
{
if(dato == actual->numero)
return altura;
else {
altura++;
if(dato < actual->numero)
actual = actual->izquierdo;
else if(dato > actual->numero)
actual = actual->derecho;
}
}
return -1;
}
void auxContador(ptr nodo, int *c)
{
(*c)++;
if(nodo->izquierdo)
auxContador(nodo->izquierdo, c);
if(nodo->derecho)
auxContador(nodo->derecho, c);
}
int Num_Nodos(ptr nodo, int *cont)
{
*cont = 0;
auxContador(nodo, cont);
return *cont;
}
void auxAltura(ptr nodo, int a, int *altura)
{
if(nodo->izquierdo)
auxAltura(nodo->izquierdo, a+1, altura);
if(nodo->derecho)
auxAltura(nodo->derecho, a+1, altura);
if(EsHoja(nodo) && a > *altura)
*altura = a;
}
int Altura_Arbol(ptr nodo, int *altura)
{
*altura = 0;
auxAltura(nodo, 0, altura);
return *altura;
}
void Eliminar_Arbol(ptr *nodo)
{
if(*nodo)
{
Eliminar_Arbol(&(*nodo)->izquierdo);
Eliminar_Arbol(&(*nodo)->derecho);
free(*nodo);
*nodo = NULL;
}
}
int EsHoja(ptr nodo)
{
return !nodo->derecho && !nodo->izquierdo;
}
int comparar(int a,int b)
{
if(a > b)
return 1;
if(a < b)
return -1;
return 0;
}
void Mostrar(int *a)
{
printf("%d, ", *a);
}
No hay comentarios:
Publicar un comentario