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).
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:
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);
}
}