Ayudita en programación en C

Question

Ayudita en programación en C

Jaime 19 dic 2004 19:54

En línea

3.376 mensajes
desde may 2001
en Madrid

Buenas, estoy haciendo una práctica en C, respecto a Árboles Binarios de Búsqueda.

El caso es que nos piden crear una función que introduzca los datos de un arbol en una tabla. Sería una función muy sencilla si pudiera ser recursiva, pero dada la cabecera (creo que) implica que no puede serlo, os dejo la cabecera a ver si me podeis echar una manilla. No pido el código sino una explicación de como puedo hacerlo porque me está resultando complicadísimo.

short Ordena_AB(pnodoab pab, int* tabla);
/* pnoadoab ->puntero a nodo de arbol */

No dan el tamaño de la tabla, porque al ir introduciendo los datos vamos aumentando el indice donde meterlo.

Gracias y un saludo.

4 respuestas

Answer 1 · 2004-12-19T19:04:55+00:00

No entiendo muy bien la funcion... si pudieras pegarnos la estructura que define el nodo del arbol y qué se espera que hagas con tabla...

gracias

Salu2.Ferdy

Answer 2 · 2004-12-19T19:30:34+00:00

Ferdy escribió:No entiendo muy bien la funcion... si pudieras pegarnos la estructura que define el nodo del arbol y qué se espera que hagas con tabla...

gracias

Salu2.Ferdy

Siento no haber sido claro. Tabla es una tabla "vacia" donde ir metiendo los datos, tiene la memoria justa para que quepan todos los datos del arbol.

typedef struct _nodoab { 
   int info; 
   struct _nodoab *izq; 
   struct _nodoab *der;
} nodoab, *pnodoab;

Un saludo.

PD: Acabo de hacer una implementación que es un poco cutre porque es una manera de evitar hacerlo sin recursividad, pero creo que me vale.

  short Ordena_AB(pnodoab pab,  int* tabla)
  {
   int i=0;
     
   return InsertaNodosTabla(pab,tabla,&i);     
  }
  
  short InsertaNodosTabla(pnodoab pab,int *tabla,int *i)
  {
     if (pab == NULL) return OK;
     
     InsertaNodosTabla(pab->izq,tabla,i);
     tabla[*i]=pab->info;
     (*i)++;
     InsertaNodosTabla(pab->der,tabla,i);
     
     return OK;
  }

Answer 3 · 2004-12-19T21:12:01+00:00

editado, no se leer. Si lo que buscaban es que no usaras recursividad desde luego que no lo han conseguido xDDD por cierto, supongo que buscarian que pasases de una solucion recursiva obvia (recorrerlo en inorden) a una solución iterativa, haz lo mismo en un while que se vaya separando en cada uno de los lados

Answer 4 · 2004-12-19T22:51:57+00:00

¿Puede que lo que quieran es que hagas un recorrido en anchura en vez de un recorrido en profundidad? Cuando usas recursividad, en realidad estas usando una pila para determinar el orden en que sacas los datos de la estructura (recuerda que por algo se llama una PILA de recursividad). Una pila es un recorrido en profundidad, se va profundizando en el árbol y se va "tocando fondo" todo lo que se puede.
Un recorrido en anchura, en cambio, necesita una cola y un bucle while. En pseudocodigo seria algo asi:

InsertarEnCola(Raiz, cola)
Mientras(!Vacia(cola))
  elem=Extraer de la Cola(cola)
  ProcesarElem(elem)
  if(elem->izq) InsertarEnCola(elem->izq, cola)
  if(elem->der) InsertarEnCola(elem->der, cola)
FinMientras

Otra posibilidad es que quieran que uses una pila externa para hacer un recorrido en profundidad (pre/in/post-orden). En ese caso, solo tienes que currarte la estructura y usarla de la misma forma (o parecido) que he hecho con la cola

Saludos