implementación árboles binarios y colas

[paula23andrea]

Buen día, quisiera pedir orientación sobre éste programa, es un programa que captura datos y los forma en un árbol binario, ya comprobé y el árbol está bien creado, el problema está en el recorrido, que es por amplitud y necesita el uso de colas, en la función eliminar señalé un system pause en la instrucción donde está ''reventando'' que ni siquiera es un ciclo...

Código C++:

#include <iostream>
using namespace std;
 
struct nodo
{
 int info, p;
 nodo *llink;
 nodo *rlink;
};
 
#define maxcola 30
struct COLA
{
 int fr;
 int fin;
 struct nodo *cont[maxcola];
}; 
 
bool colallena (struct COLA *cola)
{
     bool valor;
     int pos;
     if (cola->fin==maxcola) pos = 0;
     else pos = cola->fin;
     
     if ((cola->fr==pos)&& (cola->fin!=0)) valor=true;
     else valor = false;
     
     return valor;
}      
 
void insertarcola(struct COLA *cola, struct nodo *p) 
{
  if (colallena (cola) == false){
  if (cola->fin==maxcola)  cola->fin=1;         
  else cola->fin=cola->fin + 1;
         
  cola->cont[cola->fin]=p;          
  }
  else cout << "\nERROR: No se puede insertar en la cola, ya que esta llena";
}
 
bool colavacia (struct COLA *cola)
{
     bool valor;
     if ((cola->fr==0)&& (cola->fin==0))valor=true;
     else valor = false;
     return valor;
} 
 
void limpiarcola(struct COLA *cola) {
    cola->fr=0;
    cola->fin=0;
}
 
void eliminarcola(struct COLA *cola, struct nodo **q){
    
    
    if (colavacia(cola)==false){
        system("pause");  // al ejecutarse llega acá y revienta.
        if (cola->fr == maxcola) cola -> fr = 1; // no sé qué tiene mal esa instrucción
        else cola->fr=cola->fr + 1;
        
        *q=cola->cont[cola->fr];
        
        if (cola->fr == cola->fin) limpiarcola (cola);
                
        }
    else cout << "\nERROR: No se puede eliminar de la cola, ya que esta vacia";    
    
    
    
    } 
 
int pedir_info();
nodo *crear_nodo(int);
void insertar_nodo(nodo **, int);
void recorrer(nodo *);
 
int pedir_info()
{
 int dato;
 cout<<endl<<"Ingrese el valor para el arbol: "<<endl;
 cin>>dato;
 return dato;
}
 
nodo *crear_nodo(int dato)
{
      nodo *aux;
      aux=(nodo *)malloc(sizeof(nodo));
      aux->info=dato;
      aux->llink=NULL;
      aux->rlink=NULL;
 
      return aux;
}   
 
void insertar_nodo(nodo **arbol, int dato)
{
     if(*arbol != NULL)
     {
        if(dato < (*arbol)->info)
           insertar_nodo(&((*arbol)->llink), dato);
        else
           insertar_nodo(&((*arbol)->rlink), dato);
    }
     else
         *arbol=crear_nodo(dato);
}
 
 
void recorrer(nodo *arbol)
{
 COLA actual;   
 nodo *p;    
 insertarcola(&actual, arbol);
 
 while(colavacia(&actual)==false)
 {
 eliminarcola(&actual, &p); // acá hace el llamado a la función
 cout<<p->info; 
  
 if(p->llink!=NULL)
 insertarcola(&actual, p->llink);
 
 if(p->rlink!=NULL)
 insertarcola(&actual, p->rlink);
}
}
 
    
 
int main()
{
 nodo *arbol=NULL;
 int dato=0;
 char fin='n';
 
 while(fin=='n')
 {
  dato=pedir_info();
  insertar_nodo(&arbol, dato); 
  cout<<endl<<"Termino de ingresar? (y/n)"<<endl;               
  cin>>fin;
  } 
  
 recorrer(arbol); 
 
system("pause");
 

Muchas gracias a quien se tome el tiempo de copiarlo a un compilador y me pueda explicar!

[vosk]

El problema lo tienes en que no inicializas los datos de la estructura COLA: cuando declaras una variable y no inicializas, cualquier operacion que no sea de asignacion se hace contra datos basura del bloque de memoria al que está apuntando la variable; te pongo un ejemplo de lo que sucede:

Código:

COLA actual;
actual.fin += 1;
printf("%d", actual.fin);

Que crees que se mostrará por pantalla? 1?? Se puede dar la remota casualidad que el dato basura guardado en actual.fin equivalga al entero 0 y el resultado de la suma sea 1, pero es posible que aun provando infinitas veces no se cumpliera.

En la funcion 'recorrer()' declaras 'COLA actual' y seguidamente la envias sin inicializar a la funcion 'insertarcola()' donde lo primero que hace es comprobar si la cola está llena, te dejo una ayuda para ver como funciona por dentro esta primera llamada, que provoca un error que se arrastra por las demas funciones (será tu tarea ver el flujo de datos por dentro de las demas funciones, y tambien sobre cualquier funcion que hagas a partir de ahora ya sea sobre este programa o sobre cualquier otro):

Código:

bool colallena (struct COLA *cola) {
        bool valor;
        int pos;
        
        if (cola->fin==maxcola) {
            pos = 0;
        }
        else {
            pos = cola->fin;
        }
        
        if((cola->fr==pos)&& (cola->fin!=0)) {
            valor=true;
        }
        else {
            valor = false;
        }
        
        return valor;
    }

El primer condicional raramente se cumplirá porque 'cola->fin' llegó sin inicializar y aun contiene datos basura, luego por defecto siempre se cumple el 'else', con lo que asignas a 'pos' el dato basura de 'cola->fin'. Vas al siguiente condicional y comparas otra variable no inicializada que contiene datos basura con la variable 'pos' que segun el condicional anterior le has asignado otro dato basura, el resultado es que nunca (sería mucha casualidad) se cumplirá el segundo condicional, con lo que resuelve diciendo siempre que COLA está vacía, ok?

Solucion: inicializar todas las variables antes de hacer operaciones sobre ellas. Por suerte para ti la implementacion es muy simple, antes de usar COLA actual tienes que asignar un dato base a las variables

Código:

COLA actual;

actual.fin = 0;
actual.fr = 0;

Ya tienes tu programa funcionando.

Ahora echa un vistazo a tu funcion 'nodo *crear_nodo(int dato)', que pasa con las variables 'llink' y 'rlink'? Que sucedería si no las inicializas con NULL y las dejas apuntando al bloque de memoria que se le asigna el procesador?

Mas cosas, cuando bloqueas memoria dinamica debes hacer la comprovacion de error para el caso de que no haya disponible:

Código:

nodo *aux = (nodo *)malloc(sizeof(nodo));
if(!aux) {/*error*/}

Pero esto se hace en C, en c++ se recomienda no usar malloc para bloquear memoria dinamica, con 'new' puedes hacer lo mismo (y obviamente hacer las comprovaciones de error que con 'new' tienes que hacer con exceptions). Ademas en c++ usa los 'static_cast<tipo>' en vez de los typecast de C. En tu caso creo que no hay problema con eso, de todas formas te lo comento:

Código:

aux = new (nothrow) nodo;
if(!aux) {/*error*/}

Y cuando usas memoria dinamica tienes que liberarla cuando ya no la necesites; todos los bloques de memoria reservados con 'malloc' (en c++ con 'new') tienes que liberarlos con 'free' (en c++ con 'delete') (en c++ con new y delete hay varias cosas a tener en cuenta, mejor echa un vistazo a algun manual).

Saludos
vosk

[alex_f]

En tu otro tema, te comente el algoritmo que podes utilizar en pseudocodigo, el mismo recorrera en amplitud el arbol.

Saludos.

[paula23andrea]

Aprendí muchísimo con la respuesta de vosk, y sí el problema esencial era no haber inicializado la cola, lo demás lo tendré en cuenta, porque el uso de malloc es formato obligatorio de mi profesor de estructuras...

Enserio muchas gracias por tomarte el tiempo, ya me ha quedado todo claro :D
Ahora debo enfrentarme a herencias con clases y objetos, pero es otro tema que si me causa mucha dificultad recurriré a ustedes :)