• Lunes 18 de Noviembre de 2024, 15:44
« anterior próximo »
Páginas: [1]

Autor Tema:  Arboles Binarios  (Leído 1746 veces)

vab

  • Nuevo Miembro
  • *
  • Mensajes: 6
    • Ver Perfil
Arboles Binarios
« en: Lunes 18 de Septiembre de 2006, 23:01 »
0
quisiera saber quien me puede ayudar con el metodo insertar para un arbol binario de busqueda, aun no se si tengo q mandar un parametro (el numero a insertar) o dos parametros (la raiz y el numero a insertar) tambien quisiera que me ayudaran con la impresion del tipo preorden y con el numero de ramas y la altura del arbol gracias x la ayuda

Max_D

  • Miembro MUY activo
  • ***
  • Mensajes: 117
    • Ver Perfil
    • http://sitioteca.spaces.live.com/
Re: Arboles Binarios
« Respuesta #1 en: Martes 19 de Septiembre de 2006, 02:17 »
0
Para insertar un nodo en un ABB, se podria hacer asi:

Código: Text
  1. void insertar(Objeto b)  {
  2.  
  3.    insertarNodo(b, nodo_raiz);
  4. }
  5.  
  6. void insertarNodo(Objeto b, puntero_nodo p) {
  7.  
  8.    puntero_nodo n;
  9.  
  10.    if (p == NULL)  {
  11.        p = new Nodo(b);
  12.    }
  13.    else  {
  14.        if (b < p->getObjeto()  {
  15.            n = p->getIzquierdo();
  16.            insertarNodo(b, n);
  17.            p->SetIzquierdo(n);
  18.        }
  19.        else  {
  20.            if (b > p->getObjeto())  {
  21.                n = p->getDerecho();
  22.                insertarNodo(b,n);
  23.                p->SetDerecho(n);
  24.           }
  25.        }
  26.    }
  27. }
  28.  


donde nodo_raiz es el nodo raiz del ABB declarado en la parte privada, las funciones getObjeto (devulve el valor que contiene el nodo), getIzquierdo (devuelve un puntero a la rama izquierda), getDerecho (devuelve un puntero a la rama derecha), SetIzquierdo (asgina el valor que se le pasa a la rama izquierda), idem para SetDerecho , estan todas contenidas en la parte publica de la clase ABB. Tambien deben definirse los nodos que componen el ABB.

Sobre el contenido en preorden, solo hay que saber que recorre el arbol siguiendo la regla de: primero el nodo padre, luego el nodo hijo izquierdo y luego el nodo hijo derecho.

Espero haberte servido de ayuda  :smartass:

Bicholey

  • Moderador
  • ******
  • Mensajes: 1234
    • Ver Perfil
Re: Arboles Binarios
« Respuesta #2 en: Martes 19 de Septiembre de 2006, 08:25 »
0
:P  :P  :P


no hagas mal uso de este codigo solo tomalo de ejemplo:


Código: Text
  1.  
  2. #include <stdio.h>
  3. #include <ctype.h>
  4. #include <stdlib.h>
  5. #include <string.h>
  6. #include <conio.h>
  7. #define true 1
  8.  
  9. void PORTADA(void);
  10. void intro_nodo(void);
  11. void lista_nodos(void);
  12. void borra_nodo(void);
  13. void lista_preorden();
  14. void lista_inorden();
  15. void lista_postorden();
  16.  
  17. struct arbol *borra();
  18. struct arbol *crea_arbol();
  19.  
  20. struct arbol{
  21.   char clave;
  22.   struct arbol *izquierda;
  23.   struct arbol *derecha;
  24. };
  25.  
  26. struct arbol *raiz;
  27.  
  28. struct arbol *borra (struct arbol *raiz, char nodo){
  29.   struct arbol *d1, *d2;
  30.   if(raiz->clave == nodo){
  31.     if(raiz->izquierda == raiz->derecha){
  32.       free(raiz);
  33.       return (NULL);
  34.     }
  35.     else if(raiz->izquierda == NULL){
  36.       d1 = raiz->derecha;
  37.       free(raiz);
  38.       return (d1);
  39.     }
  40.     else if(raiz->derecha == NULL){
  41.       d1 = raiz->izquierda;
  42.       free(raiz);
  43.       return (d1);
  44.     }
  45.     else{
  46.       d2 = raiz->derecha;
  47.       d1 = raiz->derecha;
  48.       while(d1->izquierda)d1 = d1->izquierda;
  49.       d1->izquierda = raiz->izquierda;
  50.       free(raiz);
  51.       return(d2);
  52.     }
  53.   }
  54.   if(raiz->clave<nodo)
  55.     raiz->derecha = (struct arbol *)borra(raiz->derecha, nodo);
  56.   else
  57.     raiz->izquierda = (struct arbol *)borra(raiz->izquierda, nodo);
  58.   return raiz;
  59. }
  60.  
  61.  
  62.  
  63. struct arbol *crea_arbol(struct arbol *raiz, struct arbol *aux, char dato){
  64.   if(!aux){
  65.     aux = (struct arbol *)malloc (sizeof(struct arbol));
  66.     aux->izquierda = (struct arbol *)NULL;
  67.     aux->derecha = (struct arbol *)NULL;
  68.     aux->clave = dato;
  69.     if(!raiz)raiz = (struct arbol *) crea_arbol(raiz, raiz, dato);
  70.     else raiz->derecha = aux;
  71.     return aux;
  72.   }
  73.   if
  74.     (dato < aux->clave) (struct arbol*)crea_arbol(aux, aux->izquierda, dato);
  75.   else
  76.     if(dato > aux->clave) (struct arbol *)crea_arbol(aux, aux->derecha, dato);
  77. }
  78.  
  79.  
  80.  
  81. void intro_nodo(void){
  82.   char dato;
  83.   do{
  84.     printf("\n\tIntroduzca dato: ");
  85.     gets(&dato);
  86.     if(!raiz)raiz = (struct arbol *)crea_arbol(raiz, raiz, dato);
  87.     else (struct arbol *) crea_arbol(raiz, raiz, dato);
  88.   }while(dato);
  89. }
  90.  
  91.  
  92.  
  93. void borra_nodo(void){
  94.   char dato;
  95.   printf("\n\tDato a borrar: ");
  96.   gets(&dato);
  97.   (struct arbol *) borra (raiz, dato);
  98. }
  99.  
  100.  
  101.  
  102. void lista_preorden(struct arbol *aux){
  103.   int orden;
  104.   if(!aux)return;
  105.   printf("\n\t%c\t", aux->clave);
  106.   lista_preorden(aux->izquierda);
  107.   lista_preorden(aux->derecha);
  108. }
  109.  
  110.  
  111.  
  112. void lista_inorden(struct arbol *aux){
  113.   int orden;
  114.   if(!aux)return;
  115.   lista_inorden(aux->izquierda);
  116.   printf("\n\t%c\t", aux->clave);
  117.   lista_inorden(aux->derecha);
  118. }
  119.  
  120.  
  121.  
  122. void lista_postorden(struct arbol *aux){
  123.   int orden;
  124.   if(!aux)return;
  125.   lista_postorden(aux->izquierda);
  126.   lista_postorden(aux->derecha);
  127.   printf("\n\t%c\t", aux->clave);
  128. }
  129.  
  130.  
  131.  
  132. void lista_nodos(void){
  133.   clrscr();
  134.   printf("\n\tListado de los nodos del arbol");
  135.   printf("\n\tP.............Preorden");
  136.          printf("\n\tI.............Inorden");
  137.   printf("\n\tS.............Postorden");
  138.   switch(toupper(getche())){
  139.     case 'P': lista_preorden(raiz);
  140.         break;
  141.     case 'I': lista_inorden(raiz);
  142.         break;
  143.     case 'S': lista_postorden(raiz);
  144.         break;
  145.   }
  146. }
  147.  
  148.  
  149.  
  150.  
  151. void main(void){
  152.   raiz = (struct arbol *)NULL;
  153.   while(true){
  154.     clrscr();
  155.     printf("\n\tMenu del programa de un arbol");
  156.     printf("\n\tA.............Añadir nodo");
  157.            printf("\n\tL.............Listado de nodos");
  158.     printf("\n\tB.............Borrar nodos");
  159.     printf("\n\tX.............Terminar");
  160.     switch(toupper(getche())){
  161.       case 'A': intro_nodo();
  162.           break;
  163.       case 'L': lista_nodos();
  164.           break;
  165.       case 'B': borra_nodo();
  166.           break;
  167.       case 'X': exit(0);}}}
  168.  
  169.  
  170.  
  171.  
  172.  
[size=109]LOS GATOS SIEMPRE CAEMOS DE PIE !!![/size]

vab

  • Nuevo Miembro
  • *
  • Mensajes: 6
    • Ver Perfil
Re: Arboles Binarios
« Respuesta #3 en: Viernes 22 de Septiembre de 2006, 03:29 »
0
Gracias x la ayuda, ahora tengo otra pregunta como podre contar los nodos totales q tiene mi arbol??? me servira el metodo de postorden??? xq ahi recorro el arbol entero por lo que estaba pensando en un contador pero no se si esta correcta mi idea

geobeid

  • Miembro activo
  • **
  • Mensajes: 88
    • Ver Perfil
Re: Arboles Binarios
« Respuesta #4 en: Sábado 30 de Septiembre de 2006, 06:55 »
0
eso me recuerda que rindo algoritmos y estructuras de datos en 5 dias y no estudie nada todabia  :kicking:  :unsure:
[size=109]
SI QUERES ENCONTRAR A JESÚS GOOGLEALO [/size]

geobeid

  • Miembro activo
  • **
  • Mensajes: 88
    • Ver Perfil
Re: Arboles Binarios
« Respuesta #5 en: Viernes 6 de Octubre de 2006, 06:53 »
0
Citar
eso me recuerda que rindo algoritmos y estructuras de datos en 5 dias y no estudie nada todabia   
TODABIA!!!!!!!!! CON B QUE BRUTO QUE SOY DIOS!!!!!
RINDO EN 13 HS.
EN EL HORNO  :kicking:
[size=109]
SI QUERES ENCONTRAR A JESÚS GOOGLEALO [/size]
Páginas: [1]
« anterior próximo »