elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Rompecabezas de Bitcoin, Medio millón USD en premios


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  [C++] Problema con Arbol binario
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: [C++] Problema con Arbol binario  (Leído 2,522 veces)
BoniElProgramador

Desconectado Desconectado

Mensajes: 5


Ver Perfil
[C++] Problema con Arbol binario
« en: 28 Febrero 2017, 20:56 pm »

Buenas tardes casi noches,

este es mi primer post en este foro asi que si cometo algun error pido perdon  :D

bueno alli voy, resulta que tengo el reto de hacer un programa el cual lea datos de un archivo y los inserte en un Arbol Binario, insisto en lo de Arbol binario y no Arbol binario de busqueda.

Mi problema viene cuando al insertar los datos solo me rellena los 3 primeros nodos.

A continuacion mi codigo:

Código
  1. struct binaryTree
  2. {
  3. int nro;
  4. struct binaryTree *left;
  5. struct binaryTree *right;
  6. };
  7.  
  8. bool ProcessDataFromFile(char filename)
  9. {
  10. ifstream F(filename);
  11. int num;
  12.  
  13. while (!F.eof())
  14. {
  15. F >> num;
  16. cout << "numero :" << num << endl;
  17. createNode(num);
  18. insertNode(btTree, num);
  19. }
  20. return 1;
  21. }
  22.  
  23. BT createNode(int x)
  24. {
  25. BT newNode = new (struct binaryTree);
  26. newNode->nro = x;
  27. newNode->left = NULL;
  28. newNode->right = NULL;
  29. newNode->parent = NULL;
  30.  
  31. return newNode;
  32. }
  33.  
  34. //Insertar nodo
  35. void insertNode(BT &tree, int x)
  36. {
  37.  
  38.  
  39. if (tree == NULL)
  40. {
  41. tree = createNode(x);
  42. }
  43. else
  44. {
  45. if (tree->left == NULL)
  46. {
  47. insertNode(tree->left, x);
  48. tree->left->parent = tree;
  49. }
  50. else if (tree->right == NULL)
  51. {
  52. insertNode(tree->right, x);
  53. tree->right->parent = tree;
  54. }
  55. {


Gracias de antemano, un saludo
P.D. hay partes del codigo que no he puesto porque no vienen al tema


· Los códigos deben ir en etiquetas GeSHi
>aquí las reglas del foro
-Engel Lex


« Última modificación: 28 Febrero 2017, 22:38 pm por engel lex » En línea

ivancea96


Desconectado Desconectado

Mensajes: 3.412


ASMático


Ver Perfil WWW
Re: [C++] Problema con Arbol binario
« Respuesta #1 en: 28 Febrero 2017, 23:02 pm »

Fíjate en insertNode. if left == NULL, inserta ahí el número. Si right == NULL, lo inserta en right. Pero si ninguno es NULL (en la tercera iteración), no hace nada. ¿Dónde quieres que lo inserte si ninguna rama es NULL?


En línea

do-while


Desconectado Desconectado

Mensajes: 1.276


¿Habra que sacarla de paseo?


Ver Perfil
Re: [C++] Problema con Arbol binario
« Respuesta #2 en: 1 Marzo 2017, 03:11 am »

Fíjate en insertNode. if left == NULL, inserta ahí el número. Si right == NULL, lo inserta en right. Pero si ninguno es NULL (en la tercera iteración), no hace nada. ¿Dónde quieres que lo inserte si ninguna rama es NULL?

Dado que ha insistido (no se cuándo ni dónde, ya que solo lo ha mencionado una sola vez) en que no se trata de un árbol binario de búsqueda entiendo que el orden de los nodos no importa, así que completaría el código con:
Código
  1. else if(rand() % 2)
  2. {
  3.    //insertar en la rama izquierda
  4. }
  5. else
  6. {
  7.    //lo metemos en la derecha...
  8. }
  9.  
En línea

- Doctor, confundo los números y los colores.
- Vaya marrón.
- ¿Marrón? ¡Por el culo te la hinco!
BoniElProgramador

Desconectado Desconectado

Mensajes: 5


Ver Perfil
Re: [C++] Problema con Arbol binario
« Respuesta #3 en: 1 Marzo 2017, 08:39 am »

Un arbol binario se rellena de izquierda a derecha segun tengo entendido, primero la rama izquierda luego la derecha, si esa rama esta llena pasaremos a la segunda rama, rellenando hijo izquierdo e hijo derecho y asi sucesivamente hasta llenar el "piso" y bajar la profundidad.

Se que tengo que poner algo en el insertNode
despues de
         
Código:
else if (tree->right == NULL)
                                  {
                                         ....
                                  }

He probado cosas y llego hasta el segundo piso, pero de una manera muy manual, me gustaria usar recursividad o algo así para que si mi archivo tiene 500 números insertarlos en un arbol de manera correcta


Engel Lex tomo nota!! Perdon  :o :o

P.D. pensaba que estaba borrando el post de arriba y le he debido quitar reputación......   :¬¬ :¬¬
« Última modificación: 1 Marzo 2017, 08:44 am por BoniElProgramador » En línea

ivancea96


Desconectado Desconectado

Mensajes: 3.412


ASMático


Ver Perfil WWW
Re: [C++] Problema con Arbol binario
« Respuesta #4 en: 1 Marzo 2017, 12:45 pm »

Lo dicho. Tu código rellena 1 capa. Luego, ya no hace más. Tienes que ponerle que, si el nodo ya está completo, inserte en los nodos de abajo. Para elegir en qué nodo insertar, puedes mirar cual tiene menos elementos, si el izquierdo o el derecho. Si el derecho tiene menos elementos, insertas ahí. Sinó, en el izquierdo. (Para contar elementos, o almacenas una variable en el nodo de la cantidad de elementos que tiene, o haces una función recursiva)
En línea

BoniElProgramador

Desconectado Desconectado

Mensajes: 5


Ver Perfil
Re: [C++] Problema con Arbol binario
« Respuesta #5 en: 1 Marzo 2017, 13:22 pm »

Gracias por contestar Ivan, me gustaría utilizar la recursiva porque como decía lo de intentar contar nodos ya lo he probado y hay un momento en el que es mi cabeza la que entra en bucle infinito, pero no se como empezar a usarla necesitaría un poco mas de informacion
En línea

ivancea96


Desconectado Desconectado

Mensajes: 3.412


ASMático


Ver Perfil WWW
Re: [C++] Problema con Arbol binario
« Respuesta #6 en: 1 Marzo 2017, 13:31 pm »

Si ya tienes la función de contar nodos hecha (si no la tienes o te da problemas, ponla por aquí), ya solo falta poner condiciones despues de los 2 if NULL.

De todos modos, para empezar, si ni la derecha ni la izquierda son NULL, haz que lo inserte siempre en la izquierda. No está bien, pero es el comienzo. Luego, ya solo será poner una comprobación para ver que nodo tiene más elementos.
En línea

BoniElProgramador

Desconectado Desconectado

Mensajes: 5


Ver Perfil
Re: [C++] Problema con Arbol binario
« Respuesta #7 en: 1 Marzo 2017, 13:43 pm »

Lo del padre lo borre.. porque no me convencia para nada, actualmente el codigo que me gustaria modificar porque me ha dado un poco mejor resultado es el siguiente:

Código
  1. void insertNode(BT &tree, int x)
  2. {
  3.  
  4.  
  5. if (tree == NULL)
  6. {
  7. tree = createNode(x);
  8. }
  9. else
  10. {
  11. if (tree->left == NULL)
  12. {
  13. insertNode(tree->left, x);
  14. tree->left->parent = tree;
  15. }
  16. else if (tree->right == NULL)
  17. {
  18. insertNode(tree->right, x);
  19. tree->right->parent = tree;
  20. }
  21. else
  22. {
  23.                             if (changeLeftRight)
  24. {
  25. insertNode(tree->left, x);
  26. leftOrRight++;
  27. if (leftOrRight == limitLeftOrRight) //(tree->left->right != NULL)
  28. {
  29. changeLeftRight = false;
  30. leftOrRight = 0;
  31. }
  32. }
  33. else if (!changeLeftRight)
  34. {
  35. insertNode(tree->right, x);
  36. leftOrRight++;
  37. if (leftOrRight == limitLeftOrRight)//(tree->right->right != NULL)
  38. {
  39. changeLeftRight = true;
  40. leftOrRight = 0;
  41. limitLeftOrRight = 5;
  42. }
  43. }
  44.                         }
  45.                 }
  46. }
  47.  
« Última modificación: 1 Marzo 2017, 14:00 pm por BoniElProgramador » En línea

ivancea96


Desconectado Desconectado

Mensajes: 3.412


ASMático


Ver Perfil WWW
Re: [C++] Problema con Arbol binario
« Respuesta #8 en: 1 Marzo 2017, 14:40 pm »

Hay alguna cosa de ese código que no entiendo, como ese limitLeftOrRight = 5;, que viendo ese código, no tiene sentido (siempre le asignas 5).

En cualquier caso, si quieres que el árbol esté siempre balanceado, bastaría con algo como:

Código
  1. if(countElements(tree->left) > countElements(tree->right)) {
  2.    insertNode(tree->right, x);
  3. }else{
  4.    insertNode(tree->left, x);
  5. }

Ahí el tema ya sería hacer la función countElements(). Dado que sería recursiva, podría ser más útil simplemente guardar en cada nodo la cantidad de elementos que tiene.
En línea

BoniElProgramador

Desconectado Desconectado

Mensajes: 5


Ver Perfil
Re: [C++] Problema con Arbol binario
« Respuesta #9 en: 1 Marzo 2017, 15:18 pm »

Lo del limitLeftOrRight = 5 es porque estaba probando cosas realmente antes lo tenia

limitLeftOrRight = limitLeftOrRight * limitLeftOrRight ;

Debido a que había observado que en el primer piso son 4 nodos a rellenar, de los cuales al llegar a la mitad había que cambiar de lado, en el segundo son 8, pero entraba en mi función 16 veces.. etc

Son cosas que se me ocurren y voy probando para ver como actua mi programa  ;D ;D ;D

Voy a trabajar con dicha recursiva que seguramente sea mas sencillo para que mi cabeza no entre en bucle infinito  :xD

En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Altura de arbol binario
Java
l337* 4 36,489 Último mensaje 5 Diciembre 2009, 13:08 pm
por imnohacker
Arbol binario Ejemplo
.NET (C#, VB.NET, ASP)
S1dD3xt35 0 7,434 Último mensaje 21 Abril 2010, 07:18 am
por S1dD3xt35
arbol binario
Programación C/C++
karmi 2 4,105 Último mensaje 14 Diciembre 2010, 22:08 pm
por ANTÓN RAMIREZ
Arbol binario
Java
pabelsbf 2 1,807 Último mensaje 14 Diciembre 2016, 01:20 am
por pabelsbf
Problema de violación de acceso. Árbol recubridor
Programación C/C++
FranAI 1 4,400 Último mensaje 15 Noviembre 2021, 09:28 am
por Eternal Idol
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines