elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Security Series.XSS. [Cross Site Scripting]


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  graficar arboles binarios
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: graficar arboles binarios  (Leído 16,557 veces)
PABLOING

Desconectado Desconectado

Mensajes: 5


Ver Perfil
graficar arboles binarios
« en: 30 Julio 2013, 15:06 pm »

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


« Última modificación: 30 Julio 2013, 15:12 pm por PABLOING » En línea

eferion


Desconectado Desconectado

Mensajes: 1.248


Ver Perfil
Re: graficar arboles binarios
« Respuesta #1 en: 30 Julio 2013, 15:36 pm »

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.


« Última modificación: 30 Julio 2013, 16:32 pm por eferion » En línea

PABLOING

Desconectado Desconectado

Mensajes: 5


Ver Perfil
Re: graficar arboles binarios
« Respuesta #2 en: 30 Julio 2013, 21:12 pm »

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
En línea

eferion


Desconectado Desconectado

Mensajes: 1.248


Ver Perfil
Re: graficar arboles binarios
« Respuesta #3 en: 31 Julio 2013, 12:12 pm »

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:

Código:
      5
    /    \
   2      8
  / \    /
 1   3  6
         \
          7

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


Código:
            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.

Código
  1. #define CIFRAS 3
  2.  
  3. #define EXPAND_STRING(X) #X
  4. #define STRING(X) EXPAND_STRING(X)
  5. #define STR_CIFRAS STRING(CIFRAS)
  6.  
  7. void poner_espacios( int cantidad )
  8. {
  9.  while ( cantidad > 0 )
  10.  {
  11.    --cantidad;
  12.    putchar( ' ' );
  13.  }
  14. }
  15.  
  16. void pintar_nodo( arbolptr nodo, int offset )
  17. {
  18.  int i;
  19.  poner_espacios( offset );
  20.  
  21.  if ( nodo == NULL )
  22.  {
  23.    printf ( "%"STR_CIFRAS"c", ' ' );
  24.  }
  25.  else
  26.    printf( "%"STR_CIFRAS"d", nodo->info );
  27.  
  28.  poner_espacios( offset );
  29. }
  30.  
  31. void recorrer_nodo(arbolptr nodo, int nivel, int offset )
  32. {
  33.  if ( nivel == 0 )
  34.  {
  35.    // Hemos llegado al nivel buscado
  36.    pintar_nodo( nodo, offset );
  37.  }
  38.  else
  39.  {
  40.    // Seguimos bajando, si no hay nodos, los simulamos
  41.    if ( nodo == NULL )
  42.    {
  43.      recorrer_nodo( NULL, nivel - 1, offset );
  44.      recorrer_nodo( NULL, nivel - 1, offset );
  45.    }
  46.    else
  47.    {
  48.      recorrer_nodo( nodo->left, nivel-1, offset );
  49.      recorrer_nodo( nodo->right, nivel-1, offset );
  50.    }
  51.  }
  52. }
  53.  
  54. int ancho_nivel( int nivel, int nivel_max )
  55. {
  56.  if ( nivel == nivel_max )
  57.    return CIFRAS;
  58.  else
  59.    return 2 * ancho_nivel( nivel + 1, nivel_max ) + 1;
  60. }
  61.  
  62. int max_niveles_arbol( arbolptr nodo )
  63. {
  64.  int niveles = 0;
  65.  
  66.  if ( nodo != NULL )
  67.  {
  68.    ++niveles;
  69.  
  70.    int niveles_left = max_niveles_arbol( nodo->left );
  71.    int niveles_right = max_niveles_arbol( nodo->right );
  72.  
  73.    niveles += ( niveles_left > niveles_right )? niveles_left : niveles_right;
  74.  }
  75.  
  76.  return niveles;
  77. }
  78.  
  79. void pintar_nivel( arbolptr root, int nivel, int max_niveles )
  80. {
  81.  // Vamos a comprobar el ancho de los niveles empezando por el mas bajo.
  82.  // Si un nivel no entra en pantalla subimos al anterior.
  83.  // La idea es que se puedan centrar todos los niveles que entren en la pantalla
  84.  int max_length = max_niveles * 4 + 3;
  85.  
  86.  while ( max_length > 80 )
  87.  {
  88.    --max_niveles;
  89.    max_length = max_niveles * 4 + 3;
  90.  }
  91.  
  92.  int elems_ultimo_nivel = pow( 2.0, max_niveles );
  93.  
  94.  int offset_base = ( 80 - 4 * elems_ultimo_nivel - 1 ) / 2;
  95.  
  96.  int offset_nivel = ( ancho_nivel( nivel, max_niveles ) - CIFRAS ) / 2;
  97.  
  98.  // Primero se pintan los nodos
  99.  poner_espacios( offset_base );
  100.  recorrer_nodo( root, nivel, offset_nivel );
  101.  
  102.  putchar( '\n' );
  103.  // Y despues las barras ( esta parte está sin hacer )
  104.  //poner_espacios( offset_base );
  105.  //poner_barras( root, nivel, offset_nivel );
  106.  
  107.  putchar( '\n' );
  108. }
  109.  
  110. void arbolgrafico(arbolptr root )
  111. {
  112.  int niveles = max_niveles_arbol( root );
  113.  int nivel;
  114.  for ( nivel=0; nivel < niveles; ++nivel )
  115.  {
  116.    pintar_nivel( root, nivel, niveles );
  117.  }
  118. }

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...
En línea

PABLOING

Desconectado Desconectado

Mensajes: 5


Ver Perfil
Re: graficar arboles binarios
« Respuesta #4 en: 1 Agosto 2013, 04:51 am »

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
En línea

eferion


Desconectado Desconectado

Mensajes: 1.248


Ver Perfil
Re: graficar arboles binarios
« Respuesta #5 en: 1 Agosto 2013, 07:03 am »

me alegra haber sido de ayuda.

Un saludo
En línea

DarkSorcerer

Desconectado Desconectado

Mensajes: 69



Ver Perfil
Re: graficar arboles binarios
« Respuesta #6 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.

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.
En línea

eferion


Desconectado Desconectado

Mensajes: 1.248


Ver Perfil
Re: graficar arboles binarios
« Respuesta #7 en: 4 Agosto 2013, 22:13 pm »

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í:

El nodo izquierdo, si existe, tiene un valor inferior al nodo padre... el nodo derecho es superior.

En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
¿Arboles binarios en VB?....¿imposible?
Programación Visual Basic
GRANLUPIN23 0 3,057 Último mensaje 4 Diciembre 2007, 20:07 pm
por GRANLUPIN23
Arboles binarios
Programación C/C++
josue_tux 3 10,009 Último mensaje 9 Mayo 2010, 20:18 pm
por leogtz
Arboles binarios
Java
soser 0 1,910 Último mensaje 27 Octubre 2010, 08:45 am
por soser
ayuda en arboles binarios
Programación C/C++
josue_tux 1 2,829 Último mensaje 25 Junio 2011, 14:10 pm
por satu
Ayuda con arboles binarios en c++
Programación C/C++
cyntiao. 1 3,299 Último mensaje 22 Julio 2013, 22:25 pm
por eferion
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines