CENTRO UNIVERSITARIO DE CIENCIAS EXACTAS E INGENIERAS El rbol Binario de Bsqueda, implementacin dinmica Actividad: Actividad 13.

Nombre: Godinez Romero Manuel Alejandro

Matricula: 207038836

Carrera: Ingeniera En Informtica

Materia: Estructura de datos 1

Profesor: Gutirrez Hernndez Alfredo

Turno: Matutino

Das: Martes y Jueves

Horario: 7:00 a.m. a 9:00 a.m.

Problema: Haga un programa que genere una cantidad N (definida por el usuario) de valores aleatorios de tipo entero en el rango de 0 a 65,535 que se inserte al rbol conforme cada valor sea generado. El programa mostrar en pantalla los valores generados en el orden en que se insertan, enseguida el resultado de los recorridos preorder, inorder y postorder, seguido de la altura correspondiente al subrbol izquierdo y al subrbol derecho debajo de la raz del rbol. Requerimientos:

a) El estilo de programacin debe ser Orientado a Objetos

Reporte. Este programa lo comenc pensando como a ser el nodo del rbol binario de bsqueda pensando que tena que recibir todo por referencia para que fuera modificable entonces primeramente comenc declarando de tipo templete un dato despus un hijo izquierdo y un hijo derecho un nodo padre que toda va o utilizo en este programa pero que me servir para el siguiente despus de tipo mita de entero declare una altura para saber la altura del rbol y un peso para saber el nmero de nodos en el rbol despus comenc en mi parte publica a declarar mis mtodos pblicos de mi nodo comenc por declarar mi constructor mis geter y seter y comenc a poner todo en una posicin nula y tambin a declarar mis datos de los geter y despus de los seter despus hice una funcin para saber el peso del rbol donde primero verifico que no se nulo los hijos del rbol y despus digo que si el hijo izquierdo es nulo entonces a peso le doy el valor del sub rbol izquierdo mas uno por la raz despus comienzo a tomar la altura desde el nodo que la verdad no estoy seguro que sea as y por eso solo la declare pero no la uso donde se est actualizando constante mente la altura del rbol y es una funcin extra a la del get y set de le nodo asta aqui dejo mi nodo del rbol despus comienzo por declarar mi nuevo .h donde comienzo a ser una clase para las operaciones del rbol donde trato de tomar lo que dijo el profe y usar mtodos privados y pblicos para

practicar ms el polimorfismo y as no dejar al usuario saber que est trabajando con otros mtodos de mas donde no tendr acceso y comenc a declarar una raz para el rbol despus en mis parte protegida comienzo a ser un insertar que recibe una posicin y un dato tambin un borrar el rbol que solo recibe una posicin tambin tengo los mtodos de imprimir el rbol en in orden pos orden y pre orden tambin tengo un mtodo para la altura un busca dato y dos geter uno mayor y uno menor y todos estos mtodos reciben una posicin excepto el buscar porque recibes una posicin y un objeto y ya en mi parte publica tengo mi constructor y mi destructor mi geter izquierdo y mi geter derecho un busca dato un inicializa uno de vaca un insertar dato un borra posicin que no tengo privado tambin tengo un borrar dato que recibe un dato un imprime de pre orden, otro de in orden y por ultimo otro de pos orden un borrar todo y un geter altura y un get peso despus comienzo a implementar mis mtodos privados en el insertar donde resido una posicin y un dato donde verifico si tengo memoria para poder insertar despus comenc con el borra todo donde elimina todos los nodos del rbol donde la mayora de las funciones son recursivas se mandan a llamar por si solas despus en el imprime en pre orden in orden y pos orden lo nico que hice fue darle la posicin del hijo izquierdo y del derecho y el imprimir el dato y lo nico que ese fue verificar que la posicin no fuera nulo e ir moviendo dependiendo el orden de impresin el getDato que imprimo despus en la altura de mis mtodos privados lo que hago tal y como viene en el algoritmo verifico que no sea nula la posicin y creo dos auxiliares del tipo entero una para cada hijo derecho e izquierdo despus los comparo con un if y as se cul es el que debo regresar y le sumo uno por la raz despus en los geter menor y mayo hago un recorrido pero el menor Asia la izquierda y el mayor Asia la derecha despus en mis mtodos pblicos en mi constructor mando llamar la funcin inicializa y despus en mi destructor mando llamar mi mtodo de elimina todo y as me deshago de todo el rbol despus en cada uno de mis mtodos pblicos mando llamar mis mtodos privados y as el usuario no sabr que hay de tras de cada mtodo y ni como se est trabajando tambin los mtodos que no pude a ser en privado son los que resido solo un dato hay no pude a ser lo as ya por ultimo ice un men en un .h para que no se viera en el cp. donde imprimo el pre orden el pos orden y el in orden tambin verifico que el usuario no meta un nmero mayor a los 65535 que pide la practica ;

NodoABL.h // // NodoABl.h // Actividad 13 // // Created by manuel romero on 21/05/14. // Copyright (c) 2014 manuel romero. All rights reserved. // #ifndef Actividad_13_NodoABl_h #define Actividad_13_NodoABl_h template class ablNodo{ private : T dato; ablNodo* hijoIzq; ablNodo* hijoDer; ablNodo* nodoPadre; unsigned altura; unsigned peso; public: ablNodo(); ablNodo(T); T getDato(); ablNodo*& gethijoIzq(); ablNodo*& gethijoDer(); ablNodo*& getNodoPadre(); unsigned getPeso(); unsigned getAltu(); //int getBalaFact();

void setDato(T); void sethijoIzq(ablNodo*&); void sethijoDer(ablNodo*&); void setNodoPadre(ablNodo*&); void setAltu(unsigned); void setPeso(unsigned); void getActuAltu(); void actualizarPeso(); }; template ablNodo::ablNodo(){ nodoPadre=hijoIzq=hijoIzq=nullptr; peso = 1; } template ablNodo::ablNodo(T e){ dato = e; nodoPadre=hijoIzq=hijoIzq=nullptr; peso = 1; } template T ablNodo::getDato(){ return dato; } template ablNodo*& ablNodo::gethijoIzq(){ return hijoIzq; } template ablNodo*& ablNodo::gethijoDer(){ return hijoDer; }

template ablNodo*& ablNodo::getNodoPadre(){ return nodoPadre; } template unsigned ablNodo::getPeso(){ return peso; } template unsigned ablNodo::getAltu(){ return altura; } template void ablNodo::setDato(T e){ dato=e; } template void ablNodo::sethijoIzq(ablNodo*& pos){ hijoIzq = pos; } template void ablNodo::sethijoDer(ablNodo*& pos){ hijoDer = pos; } template void ablNodo::setNodoPadre(ablNodo*& pos){ nodoPadre = pos; } template void ablNodo::setPeso(unsigned pe){ peso = pe; }

template void ablNodo::setAltu(unsigned al){ altura = al; } template void ablNodo::actualizarPeso(){ if((hijoIzq == nullptr && hijoDer == nullptr)){ peso = 0; } else{ if(hijoIzq == nullptr){ peso = hijoDer->getPeso() + 1; } else{ if(hijoDer == nullptr){ peso = hijoIzq->getPeso() + 1; } else{ if(hijoIzq->getPeso() > hijoDer->getPeso()){ peso = hijoIzq->getPeso() + 1; } else{ peso = hijoDer->getPeso() + 1; } } } } } template void ablNodo::getActuAltu(){ unsigned IzquiAltu = 0; unsigned DereAltu = 0; if(hijoIzq != nullptr){ IzquiAltu = hijoIzq->getAltu();

} if(hijoDer != nullptr){ DereAltu = hijoDer->getAltu(); } if(IzquiAltu > DereAltu ){ altura = IzquiAltu +1; } else{ altura = DereAltu +1; } }

Arbol.h // // Arbol.h // Actividad 13 // // Created by manuel romero on 23/05/14. // Copyright (c) 2014 manuel romero. All rights reserved. // #ifndef Actividad_13_Arbol_h #define Actividad_13_Arbol_h #include "NodoABl.h" #include using namespace std; class AblException:public exception { private: string msg; public:

virtual const char* what() const throw() { return msg.c_str(); } AblException(string m) { msg=m; }; }; template class Arbol{ private: ablNodo* arbl; void inserDato(ablNodo*& , T&); void borrarAbl(ablNodo*&); void imprPreor(ablNodo*&); void imprIno(ablNodo*&); void imprPos(ablNodo*&); int getAltura(ablNodo*&); ablNodo*& busDato (ablNodo*& , T&); ablNodo*& getMenor(ablNodo*&); ablNodo*& getMayor(ablNodo*&); public: Arbol(); ~Arbol(); ablNodo*& getIzque(); ablNodo*& getDerech(); ablNodo*& busDato(T&); void inicializa();

bool etaVacia(); void inserDato(T&); void borraPos(ablNodo*&); void borraDato(T&); void imprPreor(); void imprIno(); void imprPos(); void borraTodo(); int getAltura(); unsigned getPeso(); }; //********************************************************************* //Metodos privados template void Arbol::inserDato(ablNodo*& pos , T& e){ if(pos == nullptr){ pos = new ablNodo (e); if(!pos){ throw AblException ("Error de posicion"); } }else{ if(e < pos->getDato()){ inserDato(pos->gethijoIzq(), e); }else{ inserDato(pos->gethijoDer(), e); }

pos->actualizarPeso(); } } template void Arbol::borrarAbl(ablNodo*& pos){ if(pos == nullptr){ return; } borrarAbl(pos->gethijoIzq()); borrarAbl(pos->gethijoDer()); delete pos; pos = nullptr; } template void Arbol::imprPreor(ablNodo*& pos){ if(pos == nullptr){ return; } coutgetDato()gethijoDer()); } template void Arbol::imprIno(ablNodo*& pos){ if(pos == nullptr){ return; } imprIno(pos->gethijoIzq()); coutgetDato()

} imprPos(pos->gethijoIzq()); imprPos(pos->gethijoDer()); coutgetDato()gethijoDer()); if (altuIzquie > altuDere) { return altuIzquie + 1; }else{ return altuDere + 1; } } template ablNodo*& Arbol::busDato (ablNodo*& pos, T& e){ if(pos == nullptr || e == pos->getDato()){ return pos; } if(e < pos->getDato()){ return busDato(pos->gethijoIzq(), e); } else{ return busDato(pos->gethijoDer(), e); } } template ablNodo*& Arbol::getMenor(ablNodo*& pos){ if(pos == nullptr){ return nullptr; }

ablNodo*& aux = pos; while (aux->gethijoIzq() != nullptr) { aux = aux->gethijoIzq(); } return aux; } template ablNodo*& Arbol::getMayor(ablNodo*& pos){ if(pos == nullptr){ return nullptr; } ablNodo*& aux = pos; while (aux->gethijoDer() != nullptr) { aux = aux->gethijoDer(); } return aux; } //****************************************************************** //Metodos publicos template Arbol::Arbol(){ inicializa(); } template Arbol::~Arbol(){ borraTodo(); } template ablNodo*& Arbol::getIzque(){ return arbl->gethijoIzq(); } template ablNodo*& Arbol::getDerech(){

return arbl->gethijoDer(); } template ablNodo*& Arbol::busDato(T& e){ return busDato(arbl, e); } template void Arbol::inicializa(){ arbl = nullptr; } template bool Arbol::etaVacia(){ return arbl == nullptr; } template void Arbol::inserDato(T& e){ inserDato(arbl, e); } template void Arbol::borraPos(ablNodo*& pos){ if(pos == nullptr){ throw AblException ("Error de insuficiencia de datos"); } if(pos->gethijoIzq() == nullptr && pos->gethijoDer()){ ablNodo*& elPadre = pos->getNodoPadre(); delete pos; pos = nullptr; ablNodo*& aux = elPadre; while (aux != nullptr) { aux->actualizarPeso(); aux = aux->getNodoPadre(); }

} else{ ablNodo*& cambiaNodo = getPeso(pos->gethijoIzq()); if(cambiaNodo == nullptr){ cambiaNodo = getMenor(pos->gethijoDer()); } T sustitulleNodo = cambiaNodo->getDato(); borraPos(cambiaNodo); pos->setDato(sustitulleNodo); } } template void Arbol::borraDato(T& e){ ablNodo*& pos = busDato(e); if(pos != nullptr){ borraPos(pos); } } template void Arbol::imprPreor(){ imprPreor(arbl); } template void Arbol::imprIno(){ imprIno(arbl); } template void Arbol::imprPos(){ imprPos(arbl); } template void Arbol::borraTodo(){ borrarAbl(arbl); }

template int Arbol::getAltura(){ return getAltura(arbl); } template unsigned Arbol::getPeso(){ return arbl->gethijoIzq()->getPeso(); } #endif

Menu.h // // Menu.h // Actividad 13 // // Created by manuel romero on 23/05/14. // Copyright (c) 2014 manuel romero. All rights reserved. // #ifndef Actividad_13_Menu_h #define Actividad_13_Menu_h #include #include #include #include "Arbol.h" using namespace std; class menu{ public: void menuArbol( Arbol); }; void menu::menuArbol( Arbol Arbo){

int dato,i,temp; srand(time_t(NULL)); cout

cout

Capturas.