• Domingo 13 de Junio de 2021, 10:29

Autor Tema:  Arbol de busqueda..!  (Leído 1173 veces)

Chicha88

  • Nuevo Miembro
  • *
  • Mensajes: 1
    • Ver Perfil
Arbol de busqueda..!
« en: Domingo 11 de Noviembre de 2012, 16:01 »
0
:ayuda: Buenas!! Tengo un problema con un arbol, en este caso, aparte de los subárboles derecho e izquierdo, debo agregarle un tercero, y la verdad no entiendo como, aqui mi código:

Código: C++
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. class Nodo
  5. {
  6. public:
  7. int ele, nhijos;
  8. Nodo *padre;
  9. Nodo *izq;
  10. Nodo *der;
  11. Nodo();
  12. };
  13.  
  14. Nodo::Nodo()
  15. {
  16. ele=0;
  17. nhijos=0;
  18. }
  19.  
  20. class ArbolBinario
  21. {
  22. public:
  23. Nodo *raiz;
  24. int cnodo, choja, con, sum, profu;
  25. ArbolBinario();
  26. void Insertar(int e);
  27. //void Eliminar();
  28. void Imprimir_Pre(Nodo *actual);
  29. void Imprimir_Orden(Nodo *actual);
  30. void Imprimir_Post(Nodo *actual);
  31. void Busqueda(Nodo *actual, int e);
  32. void Busqueda2(Nodo *actual, int e);
  33. void Recorrer(Nodo *actual);
  34. void Encontrar(Nodo *actual, int maymen);
  35. };
  36.  
  37. ArbolBinario::ArbolBinario()
  38. {
  39. raiz=NULL;
  40. cnodo=0;
  41. choja=0;
  42. sum=0;
  43. profu=-999;
  44. }
  45.  
  46. void ArbolBinario::Insertar(int e)
  47. {
  48. int nro=0;
  49. Nodo *actual, *siguiente;
  50. if (raiz==NULL)
  51. {
  52. Nodo *nuevo=new Nodo;
  53. nuevo->ele=e;
  54. nuevo->izq=NULL;
  55. nuevo->der=NULL;
  56. nuevo->padre=NULL;
  57. raiz=nuevo;
  58. sum+=e;
  59. cnodo++;
  60. }
  61. else
  62. {
  63. actual=raiz;
  64. siguiente=raiz;
  65. Nodo *nuevo=new Nodo;
  66. nuevo->ele=e;
  67. nuevo->izq=NULL;
  68. nuevo->der=NULL;
  69. nuevo->padre=NULL;
  70. actual->nhijos+=1;
  71. while(e!=nro && siguiente!=NULL)
  72. {
  73. nro=siguiente->ele;
  74. actual=siguiente;
  75. if (e<nro)
  76. {
  77. siguiente=actual->izq;
  78. }
  79. else
  80. {
  81. siguiente=actual->der;
  82. }
  83. }
  84. if (e==(actual->ele))
  85. {
  86. cout <<"Es un duplicado!\n";
  87. }
  88. else
  89. {
  90. cnodo++;
  91. sum+=e;
  92. //actual->nhijos+=1;
  93. if (e<(actual->ele))
  94. {
  95. actual->izq=nuevo;
  96. nuevo->padre=actual;
  97. }
  98. else
  99. {
  100. actual->der=nuevo;
  101. nuevo->padre=actual;
  102. }
  103. }
  104. }
  105. }
  106.  
  107. void ArbolBinario::Imprimir_Pre(Nodo *actual)
  108. {
  109. if (actual==NULL)
  110. {
  111. return;
  112. }
  113. else
  114. {
  115. cout <<actual->ele<<"\n";
  116. Imprimir_Pre(actual->izq);
  117. Imprimir_Pre(actual->der);
  118. }
  119. }
  120.  
  121. void ArbolBinario::Imprimir_Orden(Nodo *actual)
  122. {
  123. if (actual==NULL)
  124. {
  125. return;
  126. }
  127. else
  128. {
  129. Imprimir_Orden(actual->izq);
  130. cout <<actual->ele<<"\n";
  131. Imprimir_Orden(actual->der);
  132. }
  133. }
  134.  
  135. void ArbolBinario::Imprimir_Post(Nodo *actual)
  136. {
  137. if (actual==NULL)
  138. {
  139. return;
  140. }
  141. else
  142. {
  143. Imprimir_Post(actual->izq);
  144. Imprimir_Post(actual->der);
  145. cout <<actual->ele<<"\n";
  146. }
  147. }
  148.  
  149. void ArbolBinario::Busqueda(Nodo *actual, int e)
  150. {
  151. Nodo *papa=NULL, *abuelo=NULL;
  152. if (actual==NULL)
  153. {
  154. cout <<"No se encontro el elemento!\n";
  155. return;
  156. }
  157. else
  158. {
  159. papa=actual->padre;
  160. if (papa!=NULL)
  161. {
  162. abuelo=papa->padre;
  163. }
  164. if (actual->ele==e)
  165. {
  166. cout <<"El elemento "<<actual->ele<<" fue encontrado!\n";
  167. if (papa!=NULL) cout <<"El padre del mismo es: "<<papa->ele;
  168. if (abuelo!=NULL) cout <<"\nEl abuelo es: "<<abuelo->ele;
  169. cout <<"\n";
  170. }
  171. else if (e>actual->ele)
  172. {
  173. Busqueda(actual->der, e);
  174. }
  175. else
  176. {
  177. Busqueda(actual->izq, e);
  178. }
  179. }
  180. }
  181.  
  182. void ArbolBinario::Busqueda2(Nodo *actual, int e)
  183. {
  184. Nodo *antecesor=NULL;
  185. if (actual==NULL)
  186. {
  187. cout <<"No se encontro el elemento!\n";
  188. return;
  189. }
  190. else
  191. {
  192. if (actual->ele==e)
  193. {
  194. cout <<actual->ele<<"\n";
  195. antecesor=actual->padre;
  196. while (antecesor!=NULL)
  197. {
  198. cout <<antecesor->ele<<"\n";
  199. antecesor=antecesor->padre;
  200. }
  201. }
  202. else if (e>actual->ele)
  203. {
  204. Busqueda2(actual->der, e);
  205. }
  206. else
  207. {
  208. Busqueda2(actual->izq, e);
  209. }
  210. }
  211. }
  212.  
  213. void ArbolBinario::Recorrer(Nodo *actual)
  214. {
  215. Nodo *antecesor=NULL;
  216. if (actual==NULL)
  217. {
  218. return;
  219. }
  220. else
  221. {
  222. if (actual->izq==NULL && actual->der==NULL)
  223. {
  224. con=0;
  225. choja++;
  226. antecesor=actual->padre;
  227. while (antecesor!=NULL)
  228. {
  229. con++;
  230. antecesor=antecesor->padre;
  231. }
  232. con++;
  233. if (con>profu)
  234. {
  235. profu=con;
  236. }
  237. }
  238. Recorrer(actual->izq);
  239. Recorrer(actual->der);
  240. }
  241.  
  242. }
  243.  
  244. void ArbolBinario::Encontrar(Nodo *actual, int maymen)
  245. {
  246. Nodo *sucesor, *antecesor;
  247. antecesor=actual;
  248. if (maymen==1)
  249. {
  250. sucesor=actual->izq;
  251. while (sucesor!=NULL)
  252. {
  253. antecesor=sucesor;
  254. sucesor=sucesor->izq;
  255. }
  256. cout <<"El menor elemento es: "<<antecesor->ele;
  257. }
  258. else
  259. {
  260. sucesor=actual->der;
  261. while (sucesor!=NULL)
  262. {
  263. antecesor=sucesor;
  264. sucesor=sucesor->der;
  265. }
  266. cout <<"El mayor elemento es: "<<antecesor->ele;
  267. }
  268. cout <<"\n";
  269. }
  270.  

Basicamente es esto lo que debe realizar mi arbol ternario, desde ya muchas gracias!
 :gracias:
« última modificación: Domingo 11 de Noviembre de 2012, 16:03 por Chicha88 »