Logo Studenta

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:

Otros materiales