SoloCodigo

Programación General => C/C++ => Mensaje iniciado por: jonaseduardo en Sábado 27 de Diciembre de 2008, 23:45

Título: arbol binario de busqueda(insertar)
Publicado por: jonaseduardo en Sábado 27 de Diciembre de 2008, 23:45

saludos soy nuevo en el foro, para ver quien me ayuda con arboles binarios , bueno estoy confundido en como hacer el metodo insertar de manera recursiva, los nodos tengo que hacerlos como clases y no como struct, entiendo que al metodo insertar tengo que pasarle un puntero al nodo raiz pero como lo hago o deberia pasar el arbol?,gracias de antemano


#include<iostream>

using namespace std;

template<class Tipo> class arbol;

template<class Tipo>
class Nodo{

      //Atributos
      private:
       Tipo clave;
       Nodo<Tipo> *izquierdo;
       Nodo<Tipo> *derecho;      

       //metodo constructor
       public:
       Nodo(){
             
              izquierdo=derecho=NULL;
             
              }
             
         friend class arbol<Tipo>;    
};


template<class Tipo>
class arbol{
 
      //atributos
      private:
       Nodo<Tipo> *raiz;
       Nodo<Tipo> *actual;
       
      //metodo constructor
      public:
      arbol(){
             
              raiz=NULL;
              actual=NULL;
             
              }        
      //metodos      
   //   ~arbol();
      bool Esvacio();
      void Insertar(arbol **,Tipo);
 
 
 
     
};

template<class Tipo>
void arbol<Tipo>::Insertar(arbol **a,const Tipo dato){
     
    if(*a==NULL){
   
       *a= new Nodo<Tipo>();
       *a->clave=dato;
             
         
    }
    else if((*a)->clave<dato)
         Insertar(&(*a)->derecho,dato);
         
    else if((*a)->clave>dato)
         Insertar(&(*a)->izquierdo,dato);
     
}


int main(){
   
   
    arbol<int> tree;
    tree.Insertar(&tree,8);
   
   
    system("PAUSE");
    return 0;
    }

Título: Re: arbol binario de busqueda(insertar)
Publicado por: Claudisimo en Lunes 5 de Enero de 2009, 06:44

De hecho no se como hacerlo de forma no recursiva XD (bueno, me imagino que en un ciclo). Como sea, aqui tienes las instrucciones (se puede hacer de otras formas, así es como yo lo hago):
1) Primero (obviamente) declaras el árbol y sus nodos. Dentro del arbol declaras la función nodoaux.
2) Dentro de la funcion principal (o donde sea que vallas a insertar los elementos al arbol en realidad) llamas a la función nodoaux declarada. Ahora, esta función solo se preocupa de crear un nodo auxiliar:

Código: Text

1. void arbol::nodoaux(int x)
2. {
3.   nodo *aux;
4.   aux=R;
5.   aux=ingreso(aux,x);
6.   R=aux;
7. }
8.  

3) Y aquí finalmente tienes la función ingreso:

Código: Text

1. nodo* ingreso(nodo *A,int x)
2. {
3.     if (A==NULL)
4.    {
5.        A= new nodo;
6.        if (!A)
7.        {
8.              cout << "NO HAY SUFICIENTE MEMORIA ";
9.              return A;
10.        }
11.        A->dato=x;
12.        A->izq=A->der=NULL;
13.       }
14.      else if (A->dato < x)
15.          A->der=ing1(A->der,x);
16.      else if (A->dato > x)
17.          A->izq=ing1(A->izq,x);
18.      else
19.          cout << "EL ELEMENTO YA EXISTE, NO PUEDE ESTAR REPETIDO";
20.      return A;
21. }
22.  
23.  

Siendo x el dato a ingresar.

Saludos.