[C++] Problema con Arbol binario

[BoniElProgramador]

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:

Código (cpp) [Seleccionar] Expandir

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

[ivancea96]

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?

[do-while]

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 (cpp) [Seleccionar] Expandir


else if(rand() % 2)
{
    //insertar en la rama izquierda
}
else
{
    //lo metemos en la derecha...
}


[BoniElProgramador]

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 [Seleccionar] Expandir

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......   

[ivancea96]

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)

[BoniElProgramador]

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

[ivancea96]

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.

[BoniElProgramador]

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 (cpp) [Seleccionar] Expandir


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;
}
}
                        }
                }
}


[ivancea96]

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 (cpp) [Seleccionar] Expandir

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.

[BoniElProgramador]

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