API tools faq
paste
Guest User

Untitled

a guest
Nov 20th, 2017
369
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 9.27 KB | None | 0 0
raw download clone embed print report
  1. /*
  2. * PROGRAM: Binary Search Tree (Data Structure)
  3. *
  4. * @author Serrato Guerrero Michael Brandon <mikebsg01@gmail.com>
  5. */
  6. #include <iostream>
  7. #include <cstdlib>
  8. using namespace std;
  9.  
  10. struct Nodo {
  11. int dato;
  12. Nodo* der;
  13. Nodo* izq;
  14. };
  15.  
  16. Nodo* arbol = NULL;
  17.  
  18. /* --------------------------------- P R O T O T I P O S ----------------------------------- */
  19. void menu();
  20. Nodo *crearNodo(int n);
  21. void insertar(Nodo *&arbol, int n);
  22. void mostrarArbol(Nodo *&arbol, int contadorDeNiveles);
  23. bool busqueda(Nodo *arbol, int n);
  24. void recorridoPreOrder(Nodo *arbol);
  25. void recorridoInOrder(Nodo *arbol);
  26. void recorridoPostOrder(Nodo *arbol);
  27. void copiarNodo(Nodo** nodoB, Nodo** nodoA);
  28. void remplazarPorPredecesor(Nodo **subarbolIzquierdo, Nodo **nodoARemplazar);
  29. bool borrar(Nodo **arbol, int n);
  30. /* ------------------------------ F I N P R O T O T I P O S ------------------------------ */
  31.  
  32. int main() {
  33. menu();
  34. return 0;
  35. }
  36.  
  37. void menu() {
  38. int dato, opcion, contador = 0;
  39.  
  40. do {
  41. cout << "\t === MENU ===" << endl << endl
  42. << "1. Insertar un nuevo nodo." << endl
  43. << "2. Mostrar el Arbol Completo." << endl
  44. << "3. Buscar un elemento en el Arbol." << endl
  45. << "4. Recorrido PreOrder del Arbol." << endl
  46. << "5. Recorrido InOrder del Arbol." << endl
  47. << "6. Recorrido PostOrder del Arbol." << endl
  48. << "7. Eliminar nodo" << endl
  49. << "8. Salir" << endl
  50. << "Opcion: ";
  51. cin >> opcion;
  52. cout << endl;
  53.  
  54. switch(opcion) {
  55. case 1: cout << "\nDigite un numero: ";
  56. cin >> dato;
  57. cout << endl;
  58. insertar(arbol, dato);
  59. break;
  60. case 2: cout << "Mostrar el arbol.\n\n";
  61. cout << endl;
  62. mostrarArbol(arbol, contador);
  63. cout << endl << endl;
  64. //cout << "<ENTER> para continuar..." << endl;
  65. system("pause");
  66. break;
  67. case 3: cout << "Buscar un elemento en el arbol.\n\n";
  68. cout << "\nDigite un numero: ";
  69. cin >> dato;
  70. cout << endl;
  71. if (busqueda(arbol, dato) == true) {
  72. cout << "El elemento " << dato << " ha sido encontrado." << endl;
  73. } else
  74. cout << "El elemento " << dato << " No existe." << endl;
  75. cout << endl << endl;
  76. system("pause");
  77. break;
  78. case 4: cout << "\nRecorrido en PreOrder: " << endl << endl;
  79. recorridoPreOrder(arbol);
  80. cout << endl << endl;
  81. system("pause");
  82. break;
  83. case 5: cout << "\nRecorrido en InOrder: " << endl << endl;
  84. recorridoInOrder(arbol);
  85. cout << endl << endl;
  86. system("pause");
  87. break;
  88. case 6: cout << "\nRecorrido en PostOrder: " << endl << endl;
  89. recorridoPostOrder(arbol);
  90. cout << endl << endl;
  91. system("pause");
  92. break;
  93.  
  94. case 7: cout << "\nEliminar un elemento en el arbol.\n\n";
  95. cout << "\nDigite un numero: ";
  96. cin >> dato;
  97. cout << endl;
  98. if (busqueda(arbol, dato) == true) {
  99. int op;
  100. // Mostrar la información del Elemento en Pantalla y preguntar si se desea eliminar.
  101. // Según lo que conteste el usuario, proceder a eliminar o no eliminar.
  102. cout << "El elemento " << dato << " ha sido encontrado.\n"
  103. << "\n\tDesea eliminarlo?\n"
  104. << "\t1.- Si\n"
  105. << "\t2.- No\n"
  106. << "\tRespuesta: ";
  107. cin >> op;
  108. cout << endl;
  109.  
  110. if (op == 1) {
  111. if (borrar(&arbol, dato)) {
  112. cout << "\tEl elemento " << dato << " ha sido eliminado exitosamente! :)";
  113. }
  114. } else {
  115. cout << "\tOperacion cancelada, elemento no eliminado.";
  116. }
  117. } else
  118. cout << "El elemento " << dato << " No existe." << endl;
  119. cout << endl << endl;
  120. system("pause");
  121. break;
  122. case 8:
  123. cout << "\tSaliendo...\n" << endl;
  124. system("pause");
  125. return;
  126. break;
  127. default:
  128. cout << "\tLa opcion ingresada no existe!\n" << endl;
  129. system("pause");
  130. break;
  131. }
  132. system("cls");
  133. } while(opcion != 8);
  134. }
  135.  
  136. Nodo *crearNodo(int n) {
  137. Nodo* nuevo_nodo = new Nodo();
  138. nuevo_nodo->dato = n;
  139. nuevo_nodo->der = NULL;
  140. nuevo_nodo->izq = NULL;
  141.  
  142. return nuevo_nodo;
  143. }
  144.  
  145. void insertar(Nodo *&arbol, int n) {
  146. if (arbol == NULL) { // si está vacio
  147. Nodo* nuevo_nodo = crearNodo(n);
  148. arbol = nuevo_nodo;
  149. } else {
  150. int valorRaiz = arbol->dato;
  151. if (n < valorRaiz) {
  152. insertar(arbol->izq, n);
  153. } else {
  154. insertar(arbol->der, n);
  155. }
  156. }
  157. }
  158.  
  159. // Utiliza un recorrido en profundidad: inorder
  160. // pero inicia por la derecha
  161. void mostrarArbol(Nodo *&arbol, int contadorDeNiveles) {
  162. if (arbol == NULL) {
  163. return;
  164. } else {
  165. mostrarArbol(arbol->der, contadorDeNiveles+1);
  166. for (int i=0; i < contadorDeNiveles; i++) {
  167. cout << " ";
  168. }
  169. cout << arbol->dato << endl;
  170. mostrarArbol(arbol->izq, contadorDeNiveles+1);
  171. }
  172. }
  173.  
  174. bool busqueda(Nodo *arbol, int n) {
  175. if (arbol == NULL) {
  176. return false;
  177. } else if (arbol->dato == n) {
  178. return true;
  179. } else if (n < arbol->dato) {
  180. return busqueda(arbol->izq, n);
  181. } else {
  182. return busqueda(arbol->der, n);
  183. }
  184. }
  185.  
  186.  
  187. void recorridoPreOrder(Nodo *arbol) {
  188. if (arbol == NULL) {
  189. return;
  190. }
  191.  
  192. cout << arbol->dato << " ";
  193. recorridoPreOrder(arbol->izq);
  194. recorridoPreOrder(arbol->der);
  195. }
  196.  
  197. void recorridoInOrder(Nodo *arbol) {
  198. if (arbol == NULL) {
  199. return;
  200. }
  201.  
  202. recorridoInOrder(arbol->izq);
  203. cout << arbol->dato << " ";
  204. recorridoInOrder(arbol->der);
  205. }
  206.  
  207. void recorridoPostOrder(Nodo *arbol) {
  208. if (arbol == NULL) {
  209. return;
  210. }
  211.  
  212. recorridoPostOrder(arbol->izq);
  213. recorridoPostOrder(arbol->der);
  214. cout << arbol->dato << " ";
  215. }
  216.  
  217. void copiarNodo(Nodo** nodoB, Nodo** nodoA) {
  218. (*nodoB)->dato = (*nodoA)->dato;
  219. }
  220.  
  221. void remplazarPorPredecesor(Nodo **subarbolIzquierdo, Nodo **nodoARemplazar) {
  222. if ((*subarbolIzquierdo)->der != NULL) {
  223. remplazarPorPredecesor(&(*subarbolIzquierdo)->der, &(*nodoARemplazar));
  224. } else {
  225. copiarNodo(&(*nodoARemplazar), &(*subarbolIzquierdo));
  226. *nodoARemplazar = *subarbolIzquierdo;
  227. *subarbolIzquierdo = (*subarbolIzquierdo)->izq;
  228. }
  229. }
  230.  
  231. bool borrar(Nodo **arbol, int n) {
  232. if (*arbol == NULL)
  233. return false;
  234.  
  235. if (n < (*arbol)->dato) {
  236. return borrar(&(*arbol)->izq, n);
  237. } else if (n > (*arbol)->dato) {
  238. return borrar(&(*arbol)->der, n);
  239. } else if (n == (*arbol)->dato) {
  240. Nodo *temp = *arbol;
  241.  
  242. if ((*arbol)->izq != NULL and (*arbol)->der != NULL) {
  243. remplazarPorPredecesor(&(*arbol)->izq, &temp);
  244. } else if ((*arbol)->izq != NULL and (*arbol)->der == NULL) {
  245. (*arbol) = (*arbol)->izq;
  246. } else if ((*arbol)->der != NULL) {
  247. (*arbol) = (*arbol)->der;
  248. } else {
  249. delete *arbol;
  250. *arbol = NULL;
  251. return true;
  252. }
  253.  
  254. delete temp;
  255. temp = NULL;
  256. return true;
  257. }
  258. return false;
  259. }
  260.  
  261. /* --------------------------------------------------------------------------------------------------- //
  262. CORRIDAS - Programa: ÁRBOL BINARIO
  263. ------------------------------------------------------------------------------------------------------ //
  264.  
  265. Opcion: 1
  266. *** OPCION INSERTAR ***
  267. Digite un numero: 16
  268.  
  269. Opcion: 1
  270. *** OPCION INSERTAR ***
  271. Digite un numero: 59
  272.  
  273. Opcion: 1
  274. *** OPCION INSERTAR ***
  275. Digite un numero: 8
  276.  
  277. Opcion: 1
  278. *** OPCION INSERTAR ***
  279. Digite un numero: 22
  280.  
  281. Opcion: 1
  282. *** OPCION INSERTAR ***
  283. Digite un numero: 70
  284.  
  285. Opcion: 1
  286. *** OPCION INSERTAR ***
  287. Digite un numero: 7
  288.  
  289. Opcion: 1
  290. *** OPCION INSERTAR ***
  291. Digite un numero: 74
  292.  
  293. Opcion: 2
  294. *** OPCION MOSTRAR ARBOL COMPLETO ***
  295. Mostrar el arbol.
  296. 74
  297. 70
  298. 59
  299. 22
  300. 16
  301. 8
  302. 7
  303.  
  304. Opcion: 7
  305. *** OPCION ELIMINAR UN ELEMENTO DEL ARBOL ***
  306. Digite un numero: 59
  307.  
  308. El elemento 59 ha sido encontrado.
  309.  
  310. Desea eliminarlo?
  311. 1.- Si
  312. 2.- No
  313. Respuesta: 1
  314.  
  315. El elemento 59 ha sido eliminado exitosamente! :)
  316.  
  317. Opcion: 2
  318. *** OPCION MOSTRAR ARBOL COMPLETO ***
  319. Mostrar el arbol.
  320. 74
  321. 70
  322. 22
  323. 16
  324. 8
  325. 7
  326.  
  327. Opcion: 8
  328. *** OPCION SALIR ***
  329.  
  330. Saliendo...
  331.  
  332. **** Programa finalizado ****
  333.  
  334. ------------------------------------------------------------------------------------------------------ */
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!