ARBOLES BINARIOS

1. INTRODUCCIÓN.

Un árbol binario puede definirse como un árbol que en cada nodo puede tener como mucho grado 2,es decir,a lo más 2 hijos.Los hijos suelen denominarse hijo a la izquierda e hijo a la derecha,estableciéndose de esta forma un orden en el posicionamiento de los mismos.

Todas las definiciones básicas que se dieron para árboles generales permanecen inalteradas sin más que hacer las particularizaciones correspondientes.En los árboles binarios hay que tener en cuenta el orden izqda-drcha de los hijos.Por ejemplo:los árboles binarios a) y b) de la figura 1(adoptamos el convenio de que los hijos a la izquierda son extraídos extendiéndonos hacia la izquierda y los hijos a la derecha a la derecha) son diferentes,puesto que difieren en el nodo 5.El árbol c por convenio se supone igual al b) y no al a).

2. EL TIPO DE DATO ABSTRACTO ARBOL BINARIO.

Para construir el TDA Arbol Binario bastaría con utilizar las primitivas de los árboles generales pero dado la gran importancia y peculiaridades que tienen este tipo de árboles, construiremos una serie de operaciones específicas.Consideraremos las siguientes:

1. CREAR(e,Ti,Td).Devuelve un árbol cuya raíz contiene la etiqueta e asignando como hijo a la izquierda Ti y como hijo a la derecha Td.


2. DESTRUIR(T).Libera los recursos que mantienen el árbol T de forma que para volver a usarlo se debe asignar un nuevo valor con la operación de creación.


3. PADRE(n,T).Esta función devuelve el padre del nodo n en el árbol T.En caso de no existir,devuelve NODO_NULO.Como precondición n no es NODO_NULO.


4. HIJO_IZQDA(n,T).Devuelve el hijo a la izquierda del nodo n en el árbol T,y devuelve NODO_NULO si n no tiene hijo a la izquierda.Como precondición, n no es NODO_NULO.


5. HIJO_DRCHA(n,T).Devuelve el hijo a la derecha del nodo n en el árbol T,y devuelve NODO_NULO si n no tiene hijo a la derecha.Como precondición, n no es NODO_NULO.


6. ETIQUETA(n,T).Devuelve la etiqueta del nodo n en el árbol T. Como precondición, n no es NODO_NULO.


7. REETIQUETA(e,n,T).Asigna una nueva etiqueta e al nodo n en el árbol T.Como precondición n no es NODO_NULO.


8. RAIZ(T).Devuelve el nodo que está en la raíz del árbol T o NODO_NULO si T es el árbol vacío.


9. INSERTAR_HIJO_IZQDA(n,Ti,T).Inserta el árbol Ti como hijo a la izquierda del nodo n que pertenece al árbol T.En el caso de que existiese ya el hijo a la izquierda,la primitiva se encarga de que sea destruído junto con sus descendientes. Como precondiciones,Ti no es ARBOL_VACIO y n no es NODO_NULO.


10. INSERTAR_HIJO_DRCHA(n,Td,T).Inserta el árbol Td como hijo a la derecha del nodo n que pertenece al árbol T.En el caso de que existiese ya el hijo a la derecha,la primitiva se encarga de que sea destruído junto con sus descendientes.Como precondiciones,Td no es ARBOL_VACIO y n no es NODO_NULO.


11. PODAR_HIJO_IZQDA(n,T).Devuelve el subárbol con raíz hijo a la izquierda de n del árbol T el cual se ve privado de estos nodos.Como precondición, n no es NODO_NULO.


12. PODAR_HIJO_DRCHA(n,T).Devuelve el subárbol con raíz hijo a la derecha de n del árbol T el cual se ve privado de estos nodos.Como precondición, n no es NODO_NULO.

3. IMPLEMENTACIÓN DEL TDA ARBOL BINARIO Y DE LOS RECORRIDOS.

Vamos a realizar una implementación mediante punteros,para la cual hay que realizar la siguiente declaración de tipos:

#define BINARIO_VACIO NULL
#define NODO_NULO NULL

typedef int tEtiqueta                   /*Algun tipo adecuado*/
typedef struct tipoceldaB{
           struct tipoceldaB *padre,*hizqda,*hdrcha;
           tEtiqueta etiqueta;
         }*nodoB;
typedef nodoB tArbolB;

Una posible implementación para las primitivas de árboles binarios es la siguiente:

tArbolBin Crear0(tEtiqueta et)
    	
    	
   
{
  tArbolBin raiz;

  raiz = (tArbolBin)malloc(sizeof(struct tipoceldaBin));
  if (raiz==NULL)
    error(\"Memoria Insuficiente.\");
  raiz->padre = NODO_NULO;
  raiz->hizda = NODO_NULO;
  raiz->hdcha = NODO_NULO;
  raiz->etiqueta = et;
  return(raiz);
}

tArbolBin Crear2(tEtiqueta et,tArbolBin ti,tArbolBin td)
    	
    	
   
{
  tArbolBin raiz; 
  
  raiz=(tarbolBin)malloc(sizeof(struct tipoceldaBin));
  if(!raiz){
    error("Memoria Insuficiente.");
  }
  raiz->padre=NULL;
  raiz->hizqda=ti;
  raiz->hdrcha=td;
  raiz->etiqueta=et;
  if(ti!=NULL)
    td->padre=raiz;

  return raiz;
}


void Destruir(tArbolBin A)
    	
    	
   
{
   
  if(A){
    Destruir(A->hizqda);
    Destruir(A->hdrcha);
    free(A);
  }
}


nodoBin Padre(nodoBin n,tArbolBin A)
    	
    	
   
{   
  return(n->padre);
}


nodoBin Hderecha(nodoBin n,tArbolBin A)
    	
    	
   
{   
  return(n->hdrcha);
}


nodoBin Hizquierda(nodoBin n,tArbolBin A)
    	
    	
   
{   
   return(n->hizqda);
}


tEtiqueta Etiqueta(nodoBin n,tArbolBin A)
    	
    	
   
{  
  return(n->etiqueta);
}


void ReEtiqueta(tEtiqueta e,nodoBin n,tArbolBin A)
    	
    	
   
{
  n->etiqueta=e;
}


nodoBin Raiz(tArbolBin A)
    	
    	
   
{
  return A;
}


void InsertarHijoIzda(nodoBin n,tArbolBin ah,tArbolBin A)
    	
    	
   
{
  Destruir(n->hizqda);
  n->hizqda=ah;
  ah->padre=n;
}


void InsertarHijoDrchaB(nodoBin n,tArbolBin ah,tArbolBin A)
    	
    	
   
{
  Destruir(n->hdrcha);
  n->hdrcha=ah;
  ah->padre=n;
}


tArbolBin PodarHijoIzqda(nodoBin n,tArbolBin A)
    	
    	
   
{
  tArbolBin Aaux;
   
  Aaux=n->hizqda;
  n->hizqda=BINARIO_VACIO;
  if(Aaux)
    Aaux->padre=BINARIO_VACIO;

  return Aaux;
}


tArbolBin PodarHijoDrcha(nodoBin n,tArbolBin A)
    	
    	
   
{
  tArbolBin Aaux;
   
  Aaux=n->hdrcha;
  n->hdrcha=BINARIO_VACIO;
  if(Aaux)
    Aaux->padre=BINARIO_VACIO;

  return Aaux;
}

Con las cuales podemos hacer la siguiente implementación de los recorridos en preorden, postorden e inorden:

void PreordenArbol(nodoBin n,tArbolBin A)
{
   
  if(n!=NODO_NULO){
    Escribir(Etiqueta(n,A));
    PreordenArbol(HizqdaB(n,A),A);
    PreordenArbol(HdrchaB(n,A),A);
  }
}


void PostordenArbol(nodoBin n,tArbolBin A)
{
   
  if(n!=NODO_NULO){
    PostordenArbol(Hizquierda(n,A),A);
    PostordenArbol(Hderecha(n,A),A);
    Escribir(etiquetaB(n,A));
  }
}


void InordenArbol(nodoBin n,tArbolBin A)
{
  
  if(n!=NODO_NULO){
    InordenArbol(Hizquierda(n,A),A);
    Escribir(Etiqueta(n,A));
    InordenArbol(HderechaB(n,A),A);
  }
}