Descarga la aplicación para disfrutar aún más
Vista previa del material en texto
UNIVERSIDAD DE GUADALAJARA Centro Universitario de Ciencias Exactas e Ingenierías Estructura de datos I Actividad de Aprendizaje 12. El Árbol Binario de Búsqueda, implementación dinámica Alumno: Sandoval Padilla Fernando Cesar Docente: Gutiérrez Hernández Alfredo Código: 215685409 Sección: D12 16 de Noviembre de 2019 Resumen personal: Lo complejo de la actividad fue el hecho de recibir y mandar nodos de puntero por referencia pero por otra parte el programa es bastante útil ya que nos ayuda en muchas cosas el tener todo siempre organizado y aunque este árbol no tenga la misma altura en sus sub árboles o más bien no está balanceado ayudara mucho cuando queramos implementar el método de búsqueda en el árbol. Código fuente: Main.cpp 1 #include <iostream> 2 #include <chrono> 3 #include <random> 4 #include <functional> 5 6 #include "btree.h" 7 8 using namespace std; 9 10 int main() { 11 default_random_engine generator(chrono::system_clock::now().time_since_epoch().count()); 12 uniform_int_distribution<int> intDistribution(111, 999); 13 auto intDice = bind(intDistribution, generator); 14 15 BTree<int> myArbol; 16 BTree<int>::Node* pos; 17 int data, ing, myInt; 18 char opc; 19 do{ 20 21 cout << "Menu" << endl << endl; 22 cout << "A) Insertar elementos" << endl; 23 cout << "B) Recorridos In order, Post order, Pre order" << endl; 24 cout << "C) Altura del arbol" << endl; 25 cout << "D) Eliminar elemento" << endl; 26 cout << "E) Eliminar todo" << endl; 27 cout << "F) Salir" << endl; 28 cin >>opc; 29 opc = toupper(opc); 30 31 switch(opc){ 32 case 'A': 33 cout << "Cuantos numeros aleatorios deseas ingresar" << endl; 34 cin >>myInt; 35 try { 36 for(int i(0); i < myInt; i++) { 37 data = intDice(); 38 39 cout << " Insertando: " << data << endl; 40 41 myArbol.insertData(data); 42 } 43 } 44 catch(BTree<int>::Exception ex) { 45 cout << ex.what() << endl; 46 } 47 break; 48 case 'B': 49 try{ 50 cout << "In Order" << endl; 51 myArbol.parseInOrder(); 52 }catch (BTree<int>::Exception ex){ 53 cout << ex.what() << endl; 54 } 55 cout << endl << endl; 56 try{ 57 cout << "Post Order" << endl; 58 myArbol.parsePostOrder(); 59 }catch (BTree<int>::Exception ex){ 60 cout << ex.what() << endl; 61 } 62 cout << endl << endl; 63 try{ 64 cout << "Pre Order" << endl; 65 myArbol.parsePreOrder(); 66 }catch (BTree<int>::Exception ex){ 67 cout << ex.what() << endl; 68 } 69 cout << endl << endl; 70 break; 71 case 'C': 72 cout << "De donde deseas saber la altura?" << endl; 73 cout << "A)Sub arbol izquierdo" << endl; 74 cout << "B)Sub arbpñ derecho" << endl; 75 cout << "C)Todo el arbol" << endl; 76 cin>>opc; 77 opc = toupper(opc); 78 79 switch (opc){ 80 case 'A': 81 cout << " Altura del sub arbol izquierdo: " << myArbol.getLeftHeight() << endl; 82 break; 83 case 'B': 84 cout << " Altura total del arbol: " << myArbol.getRightHeight() << endl; 85 break; 86 case 'C': 87 cout << " Altura total del arbol: " << myArbol.getHeigth() << endl; 88 break; 89 90 } 91 92 break; 93 case 'D': 94 myArbol.parseInOrder(); 95 cout << endl << endl; 96 cout << " Que elemento deseas eliminar?: " << endl; 97 cin>>ing; 98 99 pos = myArbol.findData(ing); 100 101 if(pos != nullptr) { 102 myArbol.deleteData(pos); 103 } 104 cout << endl << endl; 105 myArbol.parseInOrder(); 106 cout << endl << endl; 107 break; 108 case 'E': 109 cout << "Eliminando..." << endl; 110 myArbol.deleteAll(); 111 break; 112 default: cout << "Opcion invalida, intenta de nuevo" << endl; 113 break; 114 } 115 system("pause"); 116 system("cls"); 117 }while(opc != 'F'); 118 119 return 0; 120 } btree.h 1 #ifndef BTREE_H_INCLUDED 2 #define BTREE_H_INCLUDED 3 4 #include <exception> 5 #include <string> 6 #include <iostream> 7 8 template <class T> 9 class BTree { 10 public: 11 class Node { 12 private: 13 T* dataPtr; 14 Node* left; 15 Node* right; 16 public: 17 class Exception : public std::exception { 18 private: 19 std::string msg; 20 21 public: 22 explicit Exception(const char* message) : msg(message) { } 23 24 explicit Exception(const std::string& message) : msg(message) { } 25 26 virtual ~Exception() throw () { } 27 28 virtual const char* what() const throw () { 29 return msg.c_str(); 30 } 31 }; 32 Node(); 33 Node(const T&); 34 35 ~Node(); 36 37 T* getDataPtr(); 38 T& getData(); 39 40 Node*& getLeft(); 41 Node*& getRight(); 42 43 void setDataPTr(T*); 44 void setData(const T&); 45 void setLeft(Node*&); 46 void setRight(Node*&); 47 }; 48 49 class Exception : public std::exception { 50 private: 51 std::string msg; 52 53 public: 54 explicit Exception(const char* message) : msg(message) { } 55 56 explicit Exception(const std::string& message) : msg(message) { } 57 58 virtual ~Exception() throw () { } 59 60 virtual const char* what() const throw () { 61 return msg.c_str(); 62 } 63 }; 64 65 private: 66 Node* root; 67 68 void copyAll(Node*&, Node*&); 69 70 void insertData(Node*&, const T&); 71 72 Node*& findData(Node*&, const T&); 73 74 void deleteAll(Node*); 75 76 Node*& getTheLowest(Node*&); 77 78 Node*& getTheHighest(Node*&); 79 80 int getHeigth(Node*&); 81 82 int getLeftHeight(Node*&); 83 84 int getRightHeight(Node*&); 85 86 void parsePreOrder(Node*&); 87 88 void parseInOrder(Node*&); 89 90 void parsePostOrder(Node*&); 91 92 public: 93 BTree(); 94 BTree(const BTree&); 95 96 ~BTree(); 97 98 bool isEmpty() const; 99 100 void insertData(const T&); 101 102 Node*& findData(const T&); 103 104 T& retrieve(Node*&); 105 106 void parsePreOrder(); 107 108 void parseInOrder(); 109 110 void parsePostOrder(); 111 112 void deleteData(Node*&); 113 114 bool isLeaf(Node*&) const; 115 116 int getHeigth(); 117 118 int getLeftHeight(); 119 120 int getRightHeight(); 121 122 void deleteAll(); 123 124 BTree& operator = (const BTree&); 125 }; 126 127 ///Nodo 128 129 template <class T> 130 BTree<T>::Node::Node() : dataPtr(nullptr), left(nullptr), right(nullptr) { } 131 132 template <class T> 133 BTree<T>::Node::Node(const T& e) : dataPtr(new T(e)), left(nullptr), right(nullptr) { 134 if(dataPtr == nullptr) { 135 throw Exception(" Memoria no disponible, creando nodo"); 136 } 137 } 138 139 template <class T> 140 BTree<T>::Node::~Node() { 141 delete dataPtr; 142 } 143 144 template <class T> 145 T* BTree<T>::Node::getDataPtr() { 146 return dataPtr; 147 } 148 149 template <class T> 150 T& BTree<T>::Node::getData() { 151 return *dataPtr; 152 } 153 154 template <class T> 155 typename BTree<T>::Node*& BTree<T>::Node::getLeft() { 156 return left; 157 } 158 159 template <class T> 160 typename BTree<T>::Node*& BTree<T>::Node::getRight() { 161 return right; 162 } 163 164 template <class T> 165 void BTree<T>::Node::setDataPTr(T* p) { 166 dataPtr = p; 167 } 168 169 template <class T> 170 void BTree<T>::Node::setData(const T& e) { 171 if(dataPtr == nullptr and (dataPtr = new T(e)) == nullptr) { 172 173 throw Exception(" Memoria no disponible, Node::setData"); 174 } 175 else { 176 *dataPtr = e; 177 } 178 } 179 180 template <class T> 181 void BTree<T>::Node::setLeft(BTree<T>::Node*& p) { 182 left = p; 183 } 184 185 template <class T> 186 void BTree<T>::Node::setRight(BTree<T>::Node*& p) { 187 right = p; 188 } 189 190 ///BTree 191 192 ///private 193 194 template <class T> 195 void BTree<T>::copyAll(Node*& from, Node*& to) { 196 if(from == nullptr){ 197 return; 198 } 199 try{ 200 if((to = new Node(from->getData()))==nullptr){ 201 throw Exception ("Memoria no disponible, copyAll"); 202 } 203 }catch(typename Node::Exception ex){ 204 throw Exception(ex.what()); 205 } 206 copyAll(from->getLeft(),to->getLeft()); 207 copyAll(from->getRight(),to->getRight()); 208 } 209 210 template <class T> 211 void BTree<T>::insertData(BTree<T>::Node*& r, const T& e) { 212 if(r == nullptr) { 213 try { 214 if((r = new Node(e)) == nullptr) { 215 throw Exception(" Memoria no disponible, insertData."); 216 } 217 } 218 catch(typename Node::Exception ex) { 219 throw Exception(ex.what()); 220 } 221 222 return; 223 } 224 225 if(e < r->getData()) { 226 insertData(r->getLeft(), e); 227 } 228 else { 229 insertData(r->getRight(), e); 230 } 231 } 232 233 template <class T> 234 typename BTree<T>::Node*& BTree<T>::findData(BTree<T>::Node*& r, const T& e) { 235 if(r == nullptr or r->getData() == e) { 236 return r; 237 } 238 239 if(e < r->getData()) { 240 return findData(r->getLeft(), e); 241 } 242 else { 243 return findData(r->getRight(), e); 244 } 245 } 246 247 template <class T> 248 void BTree<T>::deleteAll(BTree<T>::Node* r) { 249 if (r == nullptr){ 250 return; 251 } 252 deleteAll(r->getLeft()); 253 deleteAll(r->getRight()); 254 255 delete r; 256 r = nullptr; 257 } 258 259 template <class T> 260 typename BTree<T>::Node*& BTree<T>::getTheLowest(BTree<T>::Node*& r) { 261 if(r == nullptr or r->getLeft() == nullptr) { 262 return r; 263 } 264 265 return getTheLowest(r->getLeft()); 266 } 267 268 template <class T> 269 typename BTree<T>::Node*& BTree<T>::getTheHighest(BTree<T>::Node*& r) { 270 if(r == nullptr or r->getRight() == nullptr) { 271 return r; 272 } 273 274 return getTheHighest(r->getRight()); 275 } 276 277 template <class T> 278 int BTree<T>::getHeigth(BTree<T>::Node*& r) { 279 if(r == nullptr) { 280 return 0; 281 } 282 283 int leftHeigth(getHeigth(r->getLeft())); 284 int rightHeigth(getHeigth(r->getRight())); 285 286 return (leftHeigth > rightHeigth ? leftHeigth : rightHeigth) + 1; 287 } 288 289 template <class T> 290 int BTree<T>::getLeftHeight(BTree<T>::Node*& r){ 291 if(r == nullptr){ 292 return 0; 293 } 294 int leftHeigth(getHeigth(r->getLeft())); 295 296 return leftHeigth + 1; 297 } 298 299 template <class T> 300 int BTree<T>::getRightHeight(BTree<T>::Node*& r){ 301 if(r == nullptr){ 302 return 0; 303 } 304 int rightHeigth(getHeigth(r->getRight())); 305 306 return rightHeigth + 1; 307 } 308 309 310 template <class T> 311 void BTree<T>::parsePreOrder(BTree<T>::Node*& r) { 312 if(r == nullptr) { 313 return; 314 } 315 316 std::cout << r->getData() << ", "; 317 parsePreOrder(r->getLeft()); 318 parsePreOrder(r->getRight()); 319 } 320 321 template <class T> 322 void BTree<T>::parseInOrder(BTree<T>::Node*& r) { 323 if(r == nullptr) { 324 return; 325 } 326 327 parseInOrder(r->getLeft()); 328 std::cout << r->getData() << ", "; 329 parseInOrder(r->getRight()); 330 } 331 332 template <class T> 333 void BTree<T>::parsePostOrder(BTree<T>::Node*& r) { 334 if(r == nullptr) { 335 return; 336 } 337 338 parsePostOrder(r->getLeft()); 339 parsePostOrder(r->getRight()); 340 std::cout << r->getData() << ", "; 341 } 342 343 ///public 344 345 template <class T> 346 BTree<T>::BTree() : root(nullptr) { } 347 348 template <class T> 349 BTree<T>::BTree(const BTree<T>& t) : root(nullptr) { 350 copyAll(t.root,root); 351 } 352 353 template <class T> 354 BTree<T>::~BTree() { 355 deleteAll(); 356 } 357 358 template <class T> 359 bool BTree<T>::isEmpty() const { 360 return root == nullptr; 361 } 362 363 template <class T> 364 void BTree<T>::insertData(const T& e) { 365 insertData(root, e); 366 } 367 368 template <class T> 369 typename BTree<T>::Node*& BTree<T>::findData(const T& e) { 370 return findData(root, e); 371 } 372 373 template <class T> 374 T& BTree<T>::retrieve(BTree<T>::Node*& r) { 375 if(r == nullptr) { 376 throw Exception(" Posicion invalida, retireve."); 377 } 378 379 return r->getData(); 380 } 381 382 template <class T> 383 void BTree<T>::parsePreOrder() { 384 parsePreOrder(root); 385 } 386 387 template <class T> 388 void BTree<T>::parseInOrder() { 389 parseInOrder(root); 390 } 391 392 template <class T> 393 void BTree<T>::parsePostOrder() { 394 parsePostOrder(root); 395 } 396 397 template <class T> 398 void BTree<T>::deleteData(BTree<T>::Node*& r ) { 399 if(r == nullptr){ 400 throw Exception("Posicion invalida"); 401 } 402 if(isLeaf(r)){ 403 delete r; 404 r=nullptr; 405 return; 406 } 407 408 Node*& substitute(r->getLeft() != nullptr ? getTheHighest(r->getLeft()) : getTheLowest(r->getRight())); 409 std::swap(r->getData(),substitute->getData()); 410 411 deleteData(substitute); 412 } 413 414 template <class T> 415 bool BTree<T>::isLeaf(BTree<T>::Node*& r) const { 416 return r != nullptr and r->getLeft() == r->getRight(); 417 } 418 419 template <class T> 420 int BTree<T>::getHeigth() { 421 return getHeigth(root); 422 } 423 424 template <class T> 425 int BTree<T>::getLeftHeight() { 426 return getLeftHeight(root); 427 } 428 429 template <class T> 430 int BTree<T>::getRightHeight() { 431 return getRightHeight(root); 432 } 433 434 template <class T> 435 void BTree<T>::deleteAll() { 436 deleteAll(root); 437 } 438 439 template <class T> 440 BTree<T>& BTree<T>::operator=(const BTree<T>& t) { 441 deleteAll(); 442 443 copyAll(t.root, root); 444 445 return *this; 446 } 447 448 #endif // BTREE_H_INCLUDED Capturas de pantalla:
Compartir