Actividad de Aprendizaje 12 El Árbol Binario de Búsqueda, implementación dinámica - Fernando Cesar Sandoval Padilla

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: