 Autor
|
Tema: [C++] Problema con Arbol binario (Leído 2,867 veces)
|
BoniElProgramador
 Desconectado
Mensajes: 5
|
Buenas tardes casi noches, este es mi primer post en este foro asi que si cometo algun error pido perdon  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: struct binaryTree { int nro; struct binaryTree *left; struct binaryTree *right; }; bool ProcessDataFromFile(char filename) { ifstream F(filename); int num; while (!F.eof()) { F >> num; cout << "numero :" << num << endl; createNode(num); insertNode(btTree, num); } return 1; } BT createNode(int x) { BT newNode = new (struct binaryTree); newNode->nro = x; newNode->left = NULL; newNode->right = NULL; newNode->parent = NULL; return newNode; } //Insertar nodo void insertNode(BT &tree, int x) { if (tree == NULL) { tree = createNode(x); } else { if (tree->left == NULL) { insertNode(tree->left, x); tree->left->parent = tree; } else if (tree->right == NULL) { insertNode(tree->right, x); tree->right->parent = tree; } {
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
Mensajes: 3.412
ASMático
|
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
Mensajes: 1.276
¿Habra que sacarla de paseo?
|
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: else if(rand() % 2) { //insertar en la rama izquierda } else { //lo metemos en la derecha... }
|
|
|
|
|
En línea
|
- Doctor, confundo los números y los colores.
- Vaya marrón.
- ¿Marrón? ¡Por el culo te la hinco!
|
|
|
BoniElProgramador
Desconectado
Mensajes: 5
|
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 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  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
Mensajes: 3.412
ASMático
|
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
Mensajes: 5
|
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
Mensajes: 3.412
ASMático
|
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
Mensajes: 5
|
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: void insertNode(BT &tree, int x) { if (tree == NULL) { tree = createNode(x); } else { if (tree->left == NULL) { insertNode(tree->left, x); tree->left->parent = tree; } else if (tree->right == NULL) { insertNode(tree->right, x); tree->right->parent = tree; } else { if (changeLeftRight) { insertNode(tree->left, x); leftOrRight++; if (leftOrRight == limitLeftOrRight) //(tree->left->right != NULL) { changeLeftRight = false; leftOrRight = 0; } } else if (!changeLeftRight) { insertNode(tree->right, x); leftOrRight++; if (leftOrRight == limitLeftOrRight)//(tree->right->right != NULL) { changeLeftRight = true; leftOrRight = 0; limitLeftOrRight = 5; } } } } }
|
|
|
|
« Última modificación: 1 Marzo 2017, 14:00 pm por BoniElProgramador »
|
En línea
|
|
|
|
ivancea96
Desconectado
Mensajes: 3.412
ASMático
|
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: if(countElements(tree->left) > countElements(tree->right)) { insertNode(tree->right, x); }else{ insertNode(tree->left, x); }
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
Mensajes: 5
|
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  Voy a trabajar con dicha recursiva que seguramente sea mas sencillo para que mi cabeza no entre en bucle infinito  |
|
|
|
|
En línea
|
|
|
|
|
| Mensajes similares |
|
Asunto |
Iniciado por |
Respuestas |
Vistas |
Último mensaje |
|
|
|
Altura de arbol binario
Java
|
l337*
|
4
|
36,766
|
5 Diciembre 2009, 13:08 pm
por imnohacker
|
|
|
|
Arbol binario Ejemplo
.NET (C#, VB.NET, ASP)
|
S1dD3xt35
|
0
|
7,627
|
21 Abril 2010, 07:18 am
por S1dD3xt35
|
|
|
|
arbol binario
Programación C/C++
|
karmi
|
2
|
4,444
|
14 Diciembre 2010, 22:08 pm
por ANTÓN RAMIREZ
|
|
|
|
Arbol binario
Java
|
pabelsbf
|
2
|
2,017
|
14 Diciembre 2016, 01:20 am
por pabelsbf
|
|
|
|
Problema de violación de acceso. Árbol recubridor
Programación C/C++
|
FranAI
|
1
|
4,864
|
15 Noviembre 2021, 09:28 am
por Eternal Idol
|
 |
