graficar arboles binarios

Iniciado por PABLOING, 30 Julio 2013, 15:06 PM

0 Miembros y 1 Visitante están viendo este tema.

PABLOING

hola que tal

necesito una pequeña ayuda, ya que tengo una tarea de arboles binario en c++

se me pide graficar el arbol pero me tiene confundido, les agradezco por su ayuda

les agrego el codigo que llevo

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <iostream.h>
#include <string.h>
#define n 50;
   struct arbol
   {
      int info;

      struct arbol *left;
      struct arbol *right;
   };

   typedef struct arbol nodetree;
   typedef nodetree *arbolptr;


   void insertar(arbolptr*r,int x)
   {
      arbolptr pnuevo,panterior,pactual;
      pnuevo=(arbol*)malloc(sizeof(arbol));
      if(pnuevo!=NULL)
      {
         pnuevo->info=x;
         pnuevo->right=NULL;
         pnuevo->left=NULL;
         panterior=NULL;
         pactual=*r;
         printf("%d",pnuevo->info);

         while(pactual!=NULL && x>pactual->info)
         {
            panterior=pactual;
             pactual=pactual->left;
         }

         if(panterior==NULL)
         {
            pnuevo->left=*r;
            *r=pnuevo;
         }

         else
         {
            panterior->left=pnuevo;
            pnuevo->left=pactual;
         }
      }
   }

    void arbolgrafico(arbolptr *r, int x)
   {
      arbolptr pactual, pizq;
      if(pactual== NULL)
      {
         printf("la lista esta vacia\n");
      }


   }


   void instrucciones()
   {
      printf("\n\n ************PROGRAMA DE ARBOL***************");
      printf(" \n\n\t*****MENU PRINCIPAL********\n");
      printf("\n 1- INTRODUZCA UN ELEMENTO AL ARBOL");
      printf("\n 2- MOSTRAR");
      printf("\n 3- ARBOL GRAFICO");
        printf("\n 4-SALIR\n");
   }

   void imprimir(arbolptr pactual)
   {
      if(pactual==NULL)
      printf("\n La lista esta vacia\n");

      else
      {
         printf("\n La cadena de elementos del Arbol es:\n");

         while(pactual!=NULL)
         {
            printf("%d->\n",pactual->info);
            pactual=pactual->left;
         }

         printf("NULL\n\n");
      }
   }

   void main()
   {
      arbolptr L=NULL;
      int inf, opcion;
      instrucciones(),
      (" \n Seleciona la opcion: \n");
      scanf("%d",&opcion);
      while(opcion!=4){
      switch(opcion)
      {

         case 1:
         {
            printf("\n Introduzca el elemento:");
            scanf("%d",&inf);
            insertar(&L,inf);
            imprimir(L);
            instrucciones();
            break;
         }

         case 2:
         {
            printf("MOSTRAR");
            imprimir(L);
            break;
         }

         case 3:
         {
            printf("Arbol Grafico");
            arbolgrafico(&L,inf);
            instrucciones();
            break;
          }

         case 4:
         {
            printf("Fin del programa");
            break;
         }
         default:
         printf("Operacion invalida");
         instrucciones();
         break;
      }

      printf("\n SELECCIONA UNA OPCION: ");
      scanf("%d",&opcion);
   }// Fin del While

   printf("Fin del proyecto");

}

saludos

eferion

#1
1. El código muéstralo legible... en el combo de GeSHi elige c y mete el código dentro de esa etiqueta para que al menos pueda ser leído sin dejarse la vista en el intento.

2. Si no usas una librería... elimínala. En un programa de c no tiene sentido que haya librerías de c++ "iostream", la cual encima no se usa. Como nota también decir que las librerías de c++ no tienen el .h en el include.

3. Intenta no usar scanf... te puede dar problemas ante entradas de usuario no esperadas además de errores por desbordamiento de buffer. Lee: http://foro.elhacker.net/programacion_cc/lo_que_no_hay_que_hacer_en_cc_nivel_basico-t277729.0.html

4. Aunque al finalizar un programa toda la memoria que tuviese reservada se libera... no deja de ser una buena práctica liberar la memoria que resevamos de forma dinámica... evitarás lagunas de memoria en programas más grandes así como otros tantos problemas.

5. Entiendo que lo que te pasa es que no sabes cómo graficar el arbol, cierto ?? No tienes ningún ejemplo sobre qué es lo que quieres sacar ?? No se, digo yo que tendrás algún ejemplo sobre cómo tiene que ser la salida.

PABLOING

Gracias amigo te comento esta es la forma que tendria q representar el arbol

                    5
                  /   \
                7      6
              /   \    /  \
             2    3  3   3
Algo asi tendria q ser el arbol como es binario

eferion

Eres consciente de que el arbol que estás generando está mal montado, no ??

Para montar un árbol tu partes de un primer nodo llamado nodo raiz... este nodo tiene dos hijos, uno derecho y otro izquierdo.

El nodo izquierdo, si existe, tiene un valor inferior al nodo padre... el nodo derecho es superior. Cuando tienes que añadir un nodo nuevo... tienes que navegar por el árbol siguiendo las reglas de mayor y menor hasta que encuentres un nodo vacío y ahí es donde se añade dicho nodo.

si tu introduces la secuencia 5 2 8 3 6 7 1 el árbol que debería generarse es:


      5
    /    \
   2      8
  / \    /
1   3  6
         \
          7


Sin embargo, ante esta entrada, tu árbol queda así:



            1
           /
          2
         /
        3
       /
      5
     /
    6
   /
  7
/
8


Se parecen como un huevo a una castaña.

Además repites la llamada a "instrucciones" en cada "case"... si lo mueves al bucle while te ahorras tener que repetir esa llamada tantas veces... además de que se te ha olvidado ponerla en el case 3.

Las variables deberían tener nombres claros y concisos... r, x, inf no aportan nada, en cambio, root, node, value si.

En cuanto a lo de graficar el árbol ya te digo yo que tiene cierta miga...

yo en un ratillo he sacado una versión que yo diría que a grandes rasgos funciona ( obviamente es mejorable y tiene ciertas limitaciones ( como que si algún nodo tiene más de 3 cifras se escacharra la línea, no imprime las barras, ... ) pero funciona.


#define CIFRAS 3

#define EXPAND_STRING(X) #X
#define STRING(X) EXPAND_STRING(X)
#define STR_CIFRAS STRING(CIFRAS)

void poner_espacios( int cantidad )
{
  while ( cantidad > 0 )
  {
    --cantidad;
    putchar( ' ' );
  }
}

void pintar_nodo( arbolptr nodo, int offset )
{
  int i;
  poner_espacios( offset );

  if ( nodo == NULL )
  {
    printf ( "%"STR_CIFRAS"c", ' ' );
  }
  else
    printf( "%"STR_CIFRAS"d", nodo->info );

  poner_espacios( offset );
}

void recorrer_nodo(arbolptr nodo, int nivel, int offset )
{
  if ( nivel == 0 )
  {
    // Hemos llegado al nivel buscado
    pintar_nodo( nodo, offset );
  }
  else
  {
    // Seguimos bajando, si no hay nodos, los simulamos
    if ( nodo == NULL )
    {
      recorrer_nodo( NULL, nivel - 1, offset );
      recorrer_nodo( NULL, nivel - 1, offset );
    }
    else
    {
      recorrer_nodo( nodo->left, nivel-1, offset );
      recorrer_nodo( nodo->right, nivel-1, offset );
    }
  }
}

int ancho_nivel( int nivel, int nivel_max )
{
  if ( nivel == nivel_max )
    return CIFRAS;
  else
    return 2 * ancho_nivel( nivel + 1, nivel_max ) + 1;
}

int max_niveles_arbol( arbolptr nodo )
{
  int niveles = 0;

  if ( nodo != NULL )
  {
    ++niveles;

    int niveles_left = max_niveles_arbol( nodo->left );
    int niveles_right = max_niveles_arbol( nodo->right );

    niveles += ( niveles_left > niveles_right )? niveles_left : niveles_right;
  }

  return niveles;
}

void pintar_nivel( arbolptr root, int nivel, int max_niveles )
{
  // Vamos a comprobar el ancho de los niveles empezando por el mas bajo.
  // Si un nivel no entra en pantalla subimos al anterior.
  // La idea es que se puedan centrar todos los niveles que entren en la pantalla
  int max_length = max_niveles * 4 + 3;

  while ( max_length > 80 )
  {
    --max_niveles;
    max_length = max_niveles * 4 + 3;
  }

  int elems_ultimo_nivel = pow( 2.0, max_niveles );

  int offset_base = ( 80 - 4 * elems_ultimo_nivel - 1 ) / 2;

  int offset_nivel = ( ancho_nivel( nivel, max_niveles ) - CIFRAS ) / 2;

  // Primero se pintan los nodos
  poner_espacios( offset_base );
  recorrer_nodo( root, nivel, offset_nivel );

  putchar( '\n' );
  // Y despues las barras ( esta parte está sin hacer )
  //poner_espacios( offset_base );
  //poner_barras( root, nivel, offset_nivel );

  putchar( '\n' );
}

void arbolgrafico(arbolptr root )
{
  int niveles = max_niveles_arbol( root );
  int nivel;
  for ( nivel=0; nivel < niveles; ++nivel )
  {
    pintar_nivel( root, nivel, niveles );
  }
}


Como puedes ver sólo pintar los nodos en su sitio en un entorno de consola a pelo, sin librerías específicas e intentando que quede mínimamente colocado tiene su curro...

PABLOING

gracias Amigo creeme que he entendido mas tus observaciones que las del teacher que me imparte clases jejeje realmente me has sacado de la duda gracias

eferion

me alegra haber sido de ayuda.

Un saludo

DarkSorcerer

Quiero dar un pequeño aporte, un "Arbol Binario de Busqueda" (tipo especifico de Arbol Binario) cumple que siempre el hijo izquierdo es menor que la raiz, y el de la derecha es mayor.

Yo crearía una clase  Nodo (como dijiste que tu tarea debes hacerlo en C++) que son las hojas y que referencian tanto a los hijos izquierdos y derechos y una clase Arbol, con un nodo raiz (root) para empezar.

eferion

Cita de: DarkSorcerer en  3 Agosto 2013, 07:12 AM
Quiero dar un pequeño aporte, un "Arbol Binario de Busqueda" (tipo especifico de Arbol Binario) cumple que siempre el hijo izquierdo es menor que la raiz, y el de la derecha es mayor.

Eso mismo lo había dicho yo más o menos aquí:

Cita de: eferion en 31 Julio 2013, 12:12 PM
El nodo izquierdo, si existe, tiene un valor inferior al nodo padre... el nodo derecho es superior.