ARBOLES BINARIOS EN C++

hoy tenemos un codigo que maneja arboles binarios en c++
este codigo esta con sus respectivos comentarios para tener un mejor entendimiento del mismo igual podemos descargar el codigo


// Arboles.cpp: archivo de proyecto principal.
//librerias utilizadas
#include "stdafx.h"
#include
#include
using namespace std;
#define IZQ 1
#define DER 2
/*Estructura Utilizada para representar los nodos del arbol*/
struct NODO
{
int dato;
NODO * hijoIzq;
NODO * hijoDer;
};
/*VARIABLES GLOBALES*/
NODO * CAB_Arbol_1 = NULL; //cabecera del arbol 1
NODO * CAB_Arbol_2 = NULL; //cabecera del arbol 2
/*Prototipos de los procedimientos y funciones utilizados*/
void Generar_Arboles();
void Comparar_Arboles();
NODO* Generar_Nodo_Binario(int) ;
void Mostrar_Arbol(NODO *, int, int);
int Comparar_Igualdad(NODO *, NODO *);
/*Procedimiento que es el punto de partida del programa*/
int main()
{
//generamos los Arboles
Generar_Arboles();
printf("\n\n");
//comparamos los arboles
Comparar_Arboles();
printf("\n\n");
system("PAUSE");
return 0;
}
/*
* Metodo de Generacion de los arboles necesarios
*/
void Generar_Arboles()
{
//Generamos el primer arbol
printf("-----------------------------------------------------------------------------------\n");
printf(" GENERACION DEL PRIMER ARBOL BINARIO \n");
printf("-----------------------------------------------------------------------------------\n");
printf("\n");
//llamamos al metodo que genera los nodos
CAB_Arbol_1 = Generar_Nodo_Binario(0);
printf("\n");
printf("El arbol construido es: \n\n");
Mostrar_Arbol(CAB_Arbol_1, 0, 0);
printf("\n\n");
//Generamos el segundo arbol
printf("-----------------------------------------------------------------------------------\n");
printf(" GENERACION DEL SEGUNDO ARBOL BINARIO \n");
printf("-----------------------------------------------------------------------------------\n");
printf("\n");
//llamamos al metodo que genera los nodos
CAB_Arbol_2 = Generar_Nodo_Binario(0);
printf("\n");
printf("El arbol construido es: \n\n");
Mostrar_Arbol(CAB_Arbol_2, 0, 0);
}
/*
Procedimiento que utiliza la comparacion de igualdad de arboles y muestra el resultado
*/
void Comparar_Arboles()
{
printf("-----------------------------------------------------------------------------------\n");
printf(" COMPARACION DE IGUALDAD DE LOS ARBOLES \n");
printf("-----------------------------------------------------------------------------------\n");
printf("\n");
int resultado = Comparar_Igualdad(CAB_Arbol_1, CAB_Arbol_2);
if(resultado == 1)
{
printf(" Los Arboles SON Iguales \n");
}
else
{
printf(" Los Arboles NO SON Iguales \n");
}
}
/*
Definicion del procedimiento Generar Nodo Binario
Se genera un nodo, almacenando el dato corespondiente
Si se desea generar un hijo izq o derecho se llama
al mismo metodo y el nodo retonado es asignado al
respectivo enlace
*/
NODO* Generar_Nodo_Binario(int nivel)
{
char opcion;
NODO * nodo = new(NODO);
//imprimimos los espacios que representan el nivel
for(int i=1; i<=nivel*3; i++)
{
printf("-");
}
//pedimos al usuario que ingrese el valor
printf("Ingrese el valor del nodo: ");
cin >> nodo->dato;
//imprimimos los espacios que representan el nivel
for(int i=1; i<=nivel*3; i++)
{
printf(" ");
}
//preguntamos si se generara el hijo izquierdo
printf("Agregar el Hijo izquierdo del Nodo %d ? (S=Si; N=no) : ", nodo->dato);
cin >> opcion;
//validamos que ingrese un dato correcto
while (opcion != 'S' && opcion != 's' && opcion != 'N' && opcion != 'n')
{
printf(" *** Opcion no valida ***\n");
//imprimimos los espacios que representan el nivel
for(int i=1; i<=nivel*3; i++)
{
printf(" ");
}
printf("Agregar el Hijo izquierdo del Nodo %d ? (S=Si; N=no) : ", nodo->dato);
cin >> opcion;
}
//en caso que desee generar el hijo izquierdo....
if(opcion == 'S' || opcion == 's')
{
//se realiza un llamado recursivo de este mismo procedimiento para generar el nuevo nodo
nodo->hijoIzq = Generar_Nodo_Binario(nivel+1);
}
else
{
nodo->hijoIzq = NULL;
}
//imprimimos los espacios que representan el nivel
for(int i=1; i<=nivel*3; i++)
{
printf(" ");
}
//preguntamos si se generara el hijo derecho
printf("Agregar el Hijo Derecho del Nodo %d ? (S=Si; N=no) : ", nodo->dato);
cin >> opcion;
//validamos que ingrese un dato correcto
while (opcion != 'S' && opcion != 's' && opcion != 'N' && opcion != 'n')
{
printf(" *** Opcion no valida ***\n");
//imprimimos los espacios que representan el nivel
for(int i=1; i<=nivel*3; i++)
{
printf(" ");
}
printf("Agregar el Hijo Derecho del Nodo %d ? (S=Si; N=no) : ", nodo->dato);
cin >> opcion;
}
//en caso que desee generar el hijo derecho....
if(opcion == 'S' || opcion == 's')
{
//se realiza un llamado recursivo de este mismo procedimiento para generar el nuevo nodo
nodo->hijoDer = Generar_Nodo_Binario(nivel+1);
}
else
{
nodo->hijoDer = NULL;
}
//devolvemos el nodo creado
return nodo;
}
/*
Procedimiento para mostrar un arbol
*/
void Mostrar_Arbol(NODO * nodo, int nivel, int tipo)
{
//imprimimos los espacios que representan el nivel
for(int i=1; i<=nivel*5; i++)
{
printf("-");
}
//imprimimos el tipo del nodo
if(tipo == IZQ)
{
printf("IZQ: ");
}
else if (tipo == DER)
{
printf("DER: ");
}
//imprimimos el valor del nodo
printf("%d \n", nodo->dato);
//si el nodo tiene hijo izquierdo...
if(nodo->hijoIzq != NULL)
{
Mostrar_Arbol(nodo->hijoIzq, nivel+1, IZQ);
}
//si el nodo tiene hijo derecho...
if(nodo->hijoDer != NULL)
{
Mostrar_Arbol(nodo->hijoDer, nivel+1, DER);
}
}
/*
funcion que comprar si dos arboles binarios son iguales,
Esta funcion se ejecuta de forma recursiva asi:
primero se comparan los valores (datos) de los nodos datos
si son iguales se compara la existencia de los nodos izquiero y derechos
si ambos tiene hijos izquierdo o derecho se llama la funcion de comparacion para evaluar estos nodoso y sus hijos
retorna 1 si no iguales
retorna 0 si no son iguales
*/
int Comparar_Igualdad(NODO * nodo1, NODO * nodo2)
{
//si el valor de los nodos son diferentes
if(nodo1->dato != nodo2->dato)
{
return 0;
}
//si el nodo 1 tiene hijo izquierdo..
if(nodo1->hijoIzq != NULL)
{
//el nodo 2 no tiene hijo izquierdo...
if(nodo2->hijoIzq == NULL)
{
//los nodos no son iguales
return 0;
}
//realizamos una comparacion de igualdad de los nodos izquierdos
//y si este da como resultado que no son iguales...
if( Comparar_Igualdad( nodo1->hijoIzq, nodo2->hijoIzq) == 0)
{
//entonces tampoco son iguales los nodos padres
return 0;
}
}
//en caso que el nodo 1 no tenga hijo izquierdo...
else
{
//si el nodo 2 si tiene hijo izquierdo
if(nodo2->hijoIzq != NULL)
{
//los nodos no son semejantes
return 0;
}
}
//Si el nodo 1 tiene Hijo Derecho..
if(nodo1->hijoDer != NULL)
{
//si el nodo 2 no tiene hijo derecho...
if(nodo2->hijoDer == NULL)
{
//los nodos no son iguales
return 0;
}
//realizamos una comparacion de igualdad de los nodos derechos
//y si este da como resultado que no son iguales...
if( Comparar_Igualdad( nodo1->hijoDer, nodo2->hijoDer) == 0)
{
//entonces tampoco son iguales los nodos padres
return 0;
}
}
//en caso que el nodo 1 no tenga hijo izquierdo...
else
{
//si el nodo 2 si tiene hijo izquierdo
if(nodo2->hijoDer != NULL)
{
//los nodos no son semejantes
return 0;
}
}
return 1;
}