Índex

 
  
Capítol113.zip Exercicis
 
Capítol 13

Estructures de dades. Arbres

  1. Els arbres, definicions.
  2. Estructura per a un node d'arbre binari en C
  3. Arbres perfectament equilibrats
  4. Operacions bàsiques amb arbres binaris
    1. Recorregut d'un arbre
    2. Buscar en un arbre binari
    3. Cerca e inserció en arbres binaris
    4. Esborrar nodes d'arbres
  5. Arbres equilibrats
  6. Altres tipus d'arbres
  7. Exercicis

 

13.1. Els arbres, definicions.

Un arbre es composa de nodes. Cada node te informació i punters a nodes de manera que podem dir que de cada node surten subarbres. Els subarbres de cada node han de ser disjunts, es a dir que no pot haver cap node que pertany a dues branques de l'arbre.

Un cas particular és el d'arbres binaris, en els que cada node té dos subarbres. En aquest capítol estudiarem aquests tipus d'arbre.

Arbre binari ordenat: és aquell arbre en el que les branques de cadascun dels nodes estan ordenades. Per tant, els dos arbres de la figura són diferents segons haguem definit el tipus d'ordenació.

Definició recursiva d'arbre binari: Un arbre binari és:

      1. O bé un conjunt de nodes que està buit,
      2. O bé un conjunt de nodes que està format per un node arrel amb dos arbres binaris disjunts, anomenats subarbre esquerra i subarbre dreta del node arrel.
Exemples típics d'arbres:

13.2. Estructura per a un node d'arbre binari en C

Hem de declara un nou tipus de dades amb dues parts diferents:
 
typedef struct Node 
{ 
    //Zona de dades ············································· 
    //Aqui inserim  totes les dades necessàries 
     int Num; 

    //Zona de punters ············································· 
    //Aquí declarem els dos punters 
     struct Node *  pDret; 
     struct Node *  pEsquerra; 
};
Per a poder fer ús d'un arbre hem de declarar un punter a node que podem anomenar punter Arrel de l'arbre. A partir d'aquest punter arrel podem accedir a tots els nodes.

Mirant la figura veuràs els enllaços que haurem de crear en el moment de construir un arbre binari.

13.3. Arbres perfectament equilibrats

Són els arbres en els que, per a cada node, el número de nodes en el subarbre esquerra i en el subarbre dreta es diferència com a màxim en una unitat. Són exemples d'arbres perfectament equilibrats tots els arbres de la figura.

Per a expressar la forma en que han de distribuïr-se els nodes en un arbre perfectament equilibrat podem fer ús de la recursivitat. Per a construir un arbre de n nodes hem de seguir la regla següent:

  1. Fer ús d'un node com a node arrel
  2. Generar el subarbre esquerra amb ni= n div 2 nodes fent ús de la mateixa regla.
  3. Generar el subarbre dreta amb nd= n - ni -1 nodes fent ús de la mateixa regla.
D'aquesta manera, amb un algoritme recursiu podem construir arbres com els de la figura:
 
 
Tipus de dades i declaració de funcions
  • NodeArbreEnters: Aquest tipus de dades  conte un camp de dades (int Numero) i dos punters a elements NodeArbreEnters (pDret i pEsquerra).
  • ArbreEnters: Definim aquest tipus de dades per tal de fer coincidir el programa amb la definició recursiva d'arbre com un node arrel i dos subarbres (tant com es pot en C) 
 #include <stdio.h> 

typedef struct NodeArbreEnters 
{ 
     int Numero; 
     NodeArbreEnters * pDret; 
     NodeArbreEnters * pEsquerra; 
}; 

typedef NodeArbreEnters ArbreEnters; 

ArbreEnters * ConstrueixArbre(int nNodes); 
void ImprimeixArbre(ArbreEnters * Arrel, int h);
La funció main
Aquesta funció demana el número de nodes que ha de tenir l'arbre, fa construir l'arbre i desprès el fa imprimir.		 main() 
{ 
     int nNodes; 
     ArbreEnters * ArbreProva; 

     printf("Número de nodes: "); 
     scanf("%d",&nNodes); 
     ArbreProva = ConstrueixArbre(nNodes); 
     ImprimeixArbre(ArbreProva,0); 

     return 0; 
}
La funció ConstrueixArbre
Aquesta funció és una funció recursiva. Rep el número de nodes que ha de tenir l'arbre i fa la construcció del node corresponent assignant la informació següent a un node: 
 
  • Demana un número per al camp de dades i l'assigna.
  • Calcula el número de nodes per al subarbre dret i per al subarbre esquerra (ni i nd).
  • Assigna aquest subarbres als punters i per a fer-ho primer els construeix fent una crida a la mateixa funció amb els números de nodes calculats.
 ArbreEnters * ConstrueixArbre(int nNodes) 
{ 
     NodeArbreEnters * NouNode, * Arrel; 
     int Numero, ni, nd; 

     if (nNodes == 0) Arrel = NULL; 
     else 
     { 
          printf ("Introdueix un número com a dada d'un node: "); 
          scanf("%d",&Numero); 

          NouNode = new ArbreEnters; 
          NouNode->Numero = Numero; 

          ni = (int)(nNodes/2); 
          nd = nNodes - ni -1; 
          NouNode->pEsquerra = ConstrueixArbre(ni); 
          NouNode->pDret = ConstrueixArbre(nd); 
          Arrel = NouNode; 
     } 
     return Arrel; 
}
La funció ImprimeixArbre
Aquesta funció rep l'arbre a imprimir i treu per pantalla una figura com la de la dreta. 

Aquesta forma d'imprimir s'ha fet per comoditat i facilitat de comprensió de l'exercici. 

La funció rep l'arbre a imprimir i primer imprimeix el subarbre esquerra cap amunt i desprès el subarbre dret cap avall. Aquesta impressió de dades es fa de manera recursives amb crides a la mateixa funció.

 void ImprimeixArbre(ArbreEnters * Arrel, int nivell) 
{ 
     int i;
     if (Arrel) 
     { 
          ImprimeixArbre(Arrel->pEsquerra, nivell+1); 
          for (i=0;i<nivell;i++) printf("   "); 
          printf("%d\n",Arrel->Numero); 
          ImprimeixArbre(Arrel->pDret, nivell+1); 
    } 
}

13.4. Operacions bàsiques amb arbres binaris

13.4.1. Recorregut d'un arbre

Podem fer el recorregut d'un arbre de tres formes possibles.
 
Suposem que tenim definit un arbre com el de la dreta. Tenim els tres recorreguts següents: 
 
1. Pre-ordre: Visitar el node arrel abans que els subarbres: R, A, B o R, B, A.
2. Ordre central: Visitar primer un subarbre, després el node arrel i en darrer lloc el subarbre que queda: A, R B o B, R A.
3. Post-ordre: Visitar el node arrel després dels subarbres: A, B, R o B, A, R.
 
Així si tenim una estructura com la del problema anterior tenim les funcions genèriques per a fer el recorregut dun arbre, fent una operació P amb la informació continguda en els nodes son les següents:
 
void VisitaPreOrdre(ArbreEnters * a) 
{ 
    if (a != NULL) 
    { 
        P(a); 
        VisitaPreOrdre(a->pDret); 
        VisitaPreOrdre(a->pEsquerra); 
    } 
}
void VisitaOrdreCentral(ArbreEnters * a) 
{ 
    if (a != NULL) 
    { 
        VisitaOrdreCentral(a->pDret); 
        P(a); 
        VisitaOrdreCentral(a->pEsquerra); 
    } 
}
void VisitaPostOrdre(ArbreEnters * a) 
{ 
    if (a != NULL) 
    { 
        VisitaPostOrdre(a->pDret); 
        VisitaPostOrdre(a->pEsquerra); 
         P(a); 
    } 
}

13.4.2. Buscar en un arbre binari.

La forma més natural d'organitzar un arbre, que només té un camp clau, és fer que en tot node A totes les claus del subarbre esquerra i de A son menors que A i totes les claus del subarbre dret de A som majors que A. L'arbre de la figura esta organitzat d'aquesta manera.

La cerca d'una dada clau es farà començant pel node arrel i seguint per la branca de l'esquerra o per la branca de la dreta segons que la clau sigui major o menor (respectivament) que la dada del node arrel i així successivament fins arribar a les fulles (NULL) o fins a trobar la dada.

Si un arbre binari, a més d'estar organitzat d'aquesta manera, és perfectament equilibrat llavors la cerca es fa molt ràpidament i es realitza quasi en el mateix número de passos que en el cas de la cerca binària en vectors.

L'algoritme per a buscar en arbres organitzats d'aquesta manera és el següent:
 

Punter Busca(DadaABuscar, PunterANode) 
    Boolean Trobat 
    Trobat = Fals 
    Mentre (PunterANode i No(trobat) ) 
        Si (PunterANode.Clau = DadaABuscar) 
            Trobat = Cert 
          Sinó 
             Si (PunterANode.Clau > DadaABuscar) 
                    PunterANode = PunterANode.PunterEsquerra 
                Sinó 
                    PunterANode = PunterANode.PunterDret 
            Fi del si 
        Fi del si 
    Fi del mentre 
    Torna PunterANode 
Fi de la funció Busca

Aquesta funció torna un punter al node que conté la dada a cercar si es troba dins el arbre i si després de fer el recorregut per l'arbre no troba aquesta dada torna un punter a NULL. 

13.4.3. Cerca e inserció en arbres binaris

Ara farem un programa que crea un arbre amb rdenat amb les següent condicións: Hem de pensar que aques algoritme no mantindrà l'arbre perfecatment equilibrat.

A la figura veiem que si un arbre amb ordenat hem de inserir un nou node amb el camp clau Pablo l'algoritme busca primer aquesta dada a l'arbre i com que no la trova insereix el nou node com subarbre esquerra de Pedro per mantenir l'arbre ordenat, no per a mantenir l'arbre equilibrat.


Tipus de dades i declaració de funcions

Definim l'estructura de dades Alumnes com a nodes d'un arbre binari am dades, en aquest cas només el nom, i els punters dret i esquerra.

 #include <stdio.h>
#include <string.h> 

typedef struct Alumnes
{
     char Nom[50];
     Alumnes * pEsquerra;
     Alumnes * pDret;
}; 

void ImprimeixArbre(Alumnes * Arrel);
void BuscaInsereix(char nom[], Alumnes ** Arrel);
La funció main

La funció main té un punter a l'arbre que volem crear. 

En un bucle demana noms per pantalla i després insereix aquest nom a l'arbre. No és necessari introduir els noms en ordre alfabètic car la funció BuscaInsereix construeix l'arbre ordenat en el sentit expressat en l'apartat 4.2. 

Després imprimeix els noms que tenim a l'arbre ordenats en ordre alfabètic.

 main()
{
     Alumnes * Arrel;
     char Nom[50]; 

     Arrel=NULL;
     Nom[0]='\0'; 

     while (strcmp(Nom, "fin"))
     {
          printf("Dona'm un nom d'alumne (fin acaba): ");
          gets(Nom);
          if ((strcmp(Nom, "fin")))
           BuscaInsereix(Nom, &Arrel);
     }
     ImprimeixArbre(Arrel);
}
La funció BuscaInsereix

Aquesta funció rep l'adreça del punter arrel de l'arbre i un nom per a inserir en aquest arbre. 

És una funció recursiva:

  • Si l'arbre està buit insereix el nom en el node arrel.
  • Si no està buit fa una cerca binària del nom dins les branques de l'arbre fins que no el troba o arriba a un node full de l'arbre. En aquest cas afegeix el nom com a nou node apuntat per aquesta node full.
Cal esmentar que aquesta funció no fa arbres equilibrats.		 void BuscaInsereix(char Nom[], Alumnes ** Arrel)
{
     if ((*Arrel) == NULL)
     {
          //El nom nou (clau) no hi ‚s a l'arbre i l'inserim.
          * Arrel = new struct Alumnes;
          strcpy((*Arrel)->Nom,Nom);
          (* Arrel)->pDret=NULL;
          (* Arrel)->pEsquerra=NULL;
     }
     else if (strcmp(Nom, (*Arrel)->Nom ) < 0)
                BuscaInsereix(Nom,&(*Arrel)->pEsquerra);
            else if (strcmp(Nom, (*Arrel)->Nom ) > 0)
                BuscaInsereix(Nom,&(*Arrel)->pDret);
}
La funció ImprimeixArbre

Fa un recorregut de l'arbre de tipus ordre central i com que ja tenim fet l'ordre alfabètic de l'arbre en aquesta forma la funció ens imprimeix els noms en ordre alfabètic.

 void ImprimeixArbre(Alumnes * Arrel)
{
     if (Arrel!=NULL)
     {
          ImprimeixArbre(Arrel->pEsquerra);
          puts(Arrel->Nom);
          ImprimeixArbre(Arrel->pDret);
      }
}

A l'exemple següent veuràs un exercici on es fa ús d'un camp com a número d'entrada del registre. També afegeix una nova funció, la funció Localiza que serveix per a buscar una clau dins l'arbre.
 
 

#include <stdio.h>
#include <string.h>
#define CIERTO 1;
#define FALSO 0; 

typedef int Boolean; 

struct Alumnos 
{
     char Nombre[20];
     int NumeroEntrada;
     struct Alumnos * PIzquierdo;
     struct Alumnos * PDerecho;
}; 

void ImprimeArbol(struct Alumnos *  Puntero);
void BuscaInserta(struct Alumnos Datos, struct Alumnos * *Puntero);
struct Alumnos * Localiza(char Nom[],struct Alumnos * Raiz); 

main()
{
     struct Alumnos * Raiz=NULL;
     struct Alumnos * RegistroEncontrado=NULL;
     struct Alumnos DatoPantalla;
     char NombreABuscar[20]; 

     DatoPantalla.Nombre[0]='\0';
     while (strcmp(DatoPantalla.Nombre,"fin")) 
     {
          printf("Dame el nombre de un alumno (o fin) ");
          fflush(stdin);gets(DatoPantalla.Nombre);
          printf("Dame el nímero de entrada ");
          scanf("%d",&DatoPantalla.NumeroEntrada);
          if (strcmp(DatoPantalla.Nombre,"fin")) BuscaInserta(DatoPantalla,&Raiz);
     }
     ImprimeArbol(Raiz);
     printf("Dame un nombre a buscar ");
     fflush(stdin);gets(NombreABuscar);
     RegistroEncontrado=Localiza(NombreABuscar,Raiz);
     if (RegistroEncontrado)
              printf("%-24s%d\n",RegistroEncontrado->Nombre,RegistroEncontrado->NumeroEntrada);
     else printf("No encontrado");
} 

void ImprimeArbol(struct Alumnos * Puntero)
{
     int i;
     if (Puntero != NULL) 
     {
          ImprimeArbol(Puntero->PIzquierdo);
          printf("%-24s%d\n",Puntero->Nombre,Puntero->NumeroEntrada);
          ImprimeArbol(Puntero->PDerecho);
     }
} 

void BuscaInserta(struct Alumnos Datos, struct Alumnos * * Puntero)
{
     if ((*Puntero) == NULL) 
     {
          //El Nombre clave no está en el árbol, insertar registro
          * Puntero=new struct Alumnos ;
          strcpy((*Puntero)->Nombre,Datos.Nombre);
          (*Puntero)->NumeroEntrada = Datos.NumeroEntrada;
          (*Puntero)->PIzquierdo = NULL;
          (*Puntero)->PDerecho = NULL;
     }
     else if (strcmp(Datos.Nombre,(*Puntero)->Nombre)<0)
              BuscaInserta(Datos,&(*Puntero)->PIzquierdo);
            else if (strcmp(Datos.Nombre,(*Puntero)->Nombre)>0)
              BuscaInserta(Datos,&(*Puntero)->PDerecho);
} 

struct Alumnos * Localiza(char Nom[],struct Alumnos * Puntero)
{
     Boolean Encontrado; 

     Encontrado = FALSO;
     while ( (Puntero != NULL) && (!Encontrado) ) 
    {
          if  (!strcmp(Puntero->Nombre, Nom)) Encontrado = CIERTO
              else if (strcmp(Puntero->Nombre, Nom)>0) Puntero=Puntero->PIzquierdo;
                      else Puntero=Puntero->PDerecho;
     }
     return Puntero;
}

13.4.4 Esborrar nodes d'arbres

El problema és diferent al problema d'esborrar en llistes car es presenten dos casos diferents
  1. El node que ha d'imprimir-se és un node terminal, com l'element 13 de la figura, o té un sol descendent, com l'element 15.
  2. El node té dos descendents com l'element 10 de la figura. En aquest cas hem de substituir el node a esborrar bé per l'element més a la dreta en el subarbre esquerra o bé per l'element més a l'esquerra del subarbre dret.

La funció Esborra que hem fet distingeix tres casos

  1. L'element que volem li passem no hi és a l'arbre.
  2. L'element a esborrar té un descendent com a màxim
  3. L'element a esborrar té dos descendents.
La funció Esborra fa ús de la funció Elimina només l'activa en el cas 3 i desen per la branca més a la dreta de l'arbre.
 
Adaptem la funció main per tal de probar la funció Esborra.

Es fa notar que l'arbre que queda és el de la figura.

Podeu fer probes per tal d'esborrar diferents elemets de l'arbre.

main()
{
     Alumnes * Arrel;
     char Nom[50];

     char Noms[7][50]={"jorge","nuria","pedro","maria","vicente","ana","pablo"};
     int i;

     Arrel=NULL;

     for(i=0;i<7;i++) BuscaInsereix(Noms[i], &Arrel);

     ImprimeixArbre(Arrel);
     Esborra("ana",&Arrel);
     printf("\Arbre després de esborrar\n");
     ImprimeixArbre(Arrel);
}
La funció Esborra
Rep el nom a esborrar i el punter arrel de l'arbre.

És una funció recursiva que primer busca el node on es troba la informació continguda en Nom i després contempla tots els casos dits abans.

Fem notar que en cas de esborrar un node hem d'alliberar la memòria d'aquest node.

 void Esborra(char Nom[], Alumnes ** Arrel)
{
     Alumnes **Auxiliar;

     if ((*Arrel) == NULL) printf("\nLa clau buscada no hi ‚s a l'arbre");
     else if (strcmp(Nom, (*Arrel)->Nom )<0) Esborra(Nom,&(*Arrel)->pEsquerra);
     else if (strcmp(Nom, (*Arrel)->Nom )>0) Esborra(Nom,&(*Arrel)->pDret);
     else
     {
          Auxiliar=Arrel;
          if ((*Auxiliar)->pDret == NULL)
          {
               (*Arrel)=(*Auxiliar)->pEsquerra;
               delete (*Auxiliar);
          }
          else if ((*Auxiliar)->pEsquerra== NULL)
          {
               (*Arrel)=(*Auxiliar)->pDret;
               delete (*Auxiliar);
          }
          else Elimina(&(*Auxiliar)->pEsquerra,&(*Auxiliar));
     }
}
La funció elimina void Elimina(Alumnes ** Punter, Alumnes ** Auxiliar)
{
     if ((*Punter)->pDret != NULL)
          Elimina(&(*Punter)->pDret,&(*Auxiliar));
     else
     {
          strcpy((*Auxiliar)->Nom,(*Punter)->Nom);
          (*Auxiliar)->pEsquerra=(*Punter)->pEsquerra;
          delete (*Punter);
     }
}

13.5.- Arbres equilibrats

Per a que un algoritme de creació e inserció d'arbres sigui bó ha de mantenir els arbres perfectament equilibrats. Peró, degut a consideracions teóriques més complexes, es va demostrar que un algoritme d'aquestes característiques no és eficient, car l'operació de restaurar l'equilibri perfect, després de la insercció d'un node, de m,anera que es conservi l'ordre, és una operació molt i molt complexa.

Així apareix el concepte d'arbre equilibrat: Un arbre està equilibrat si i només si per a cadascun dels seus nodes s'esdevé que les alçades dels seus dos arbres es diferencien com a molt en un.

Aques concepte d'arbre equilibrat permet crear algoritmes amb reequilibri bastant eficients.

A l'exemple següent s'escriu l'algoreitme de creació d'arbres equilibrats:
 
 
Tipus de dades i declaració de funcions

Es defineix una estructura Alumnes que serveix com a node per a construir l'arbre.
 

 #include <stdio.h>
#include <string.h>

#define CERT 1
#define FALS 0

typedef int Boolean;

typedef struct Alumnes
{
     char Nom[50];
     int Comptador;
     Alumnes * pEsquerra;
     Alumnes * pDret;
     int Equilibri;
};

void Busca(char Nom[], Alumnes ** Arrel, Boolean *h);
void ImprimeixArbre(Alumnes * Arrel);
La funció main

Declara el punter Arrel per a construir-hi l'arbre.

Es declara un vector de noms (NomMat) amb 7 noms per a incloure dins els nodes de l'arbre.

Desprès de construir l'arbre amb la funció Busca imprimim l'arbre.

 main()
{
     Alumnes * Arrel;
     char Nom[50];
     Boolean h=FALS;

     char NomMat[7][50]={"jorge","nuria","pedro","maria","vicente","ana","alma"};
     int i;

     Arrel=NULL;

     for(i=0;i<7;i++) Busca(NomMat[i], &Arrel,&h);

     ImprimeixArbre(Arrel);
}
La funció Busca

Aquesta és una funció que busca si la dada que rep està en el arbre.

Si no està dins l'arbre la insereix i després i en cas que sigui necessari reequilibra l'arbre.

 void Busca(char Nom[], Alumnes ** Arrel, Boolean *h)
{
     Alumnes ** Aux1;
     Alumnes ** Aux2;
     if ((*Arrel) == NULL)
     {
          //El registre no hi ‚s dins l'arbre i l'inserim.
          * Arrel = new Alumnes;
          strcpy((*Arrel)->Nom,Nom);
          (*Arrel)->Comptador = 1;
          (* Arrel)->pDret=NULL;
          (* Arrel)->pEsquerra=NULL;
          (* Arrel)->Equilibri = 0;
     }
     else
     if (strcmp(Nom, (*Arrel)->Nom ) < 0)
     {
          Busca(Nom,&(*Arrel)->pEsquerra,h);
          if (h) //La branca dreta ha crescut
          switch ((* Arrel)->Equilibri)
         {
                case  1: (* Arrel)->Equilibri=0; *h=FALS; break;
                case  0: (* Arrel)->Equilibri=-1; break;
                case -1: //Reequilibrar
               (*Aux1)=(*Arrel)->pEsquerra;
               if ((*Aux1)->Equilibri==-1)
               { //Rotació II simple
                    (*Arrel)->pEsquerra= (*Aux1)->pDret;
                    (*Aux1)->pDret=(*Arrel);
                    (*Arrel)->Equilibri=0;
                    (*Arrel)=(*Aux1);
               }
               else
               { //Rotació ID doble
                   (*Aux2)=(*Aux1)->pDret;
                    (*Aux1)->pDret=(*Aux2)->pEsquerra;
                    (*Aux2)->pEsquerra=(*Aux1);
                    (*Arrel)->pEsquerra=(*Aux2)->pDret;
                    (*Aux2)->pDret=(*Arrel);
                    if ((*Aux2)->Equilibri == -1) (*Arrel)->Equilibri=1;
                    else (*Arrel)->Equilibri=0;
                    if ((*Aux2)->Equilibri == 1) (*Aux1)->Equilibri=-1;
                    else (*Aux1)->Equilibri=0;
                    (*Arrel)=(*Aux2);
               }
               (*Arrel)->Equilibri=0;
               *h=FALS;
               break;
           }
     }
     else if (strcmp(Nom, (*Arrel)->Nom ) > 0)
     {
          Busca(Nom,&(*Arrel)->pDret,h);
          if (h) //La branca dreta ha crescut
          switch ((* Arrel)->Equilibri)
          {
                case -1: (* Arrel)->Equilibri=0; *h=FALS; break;
                case  0: (* Arrel)->Equilibri=+1; break;
                case  1: //Reequilibrar
                (*Aux1)=(*Arrel)->pDret;
               if ((*Aux1)->Equilibri==+1)
               { //Rotació DD simple
                    (*Arrel)->pDret= (*Aux1)->pEsquerra;
                    (*Aux1)->pEsquerra=(*Arrel);
                    (*Arrel)->Equilibri=0;
                    (*Arrel)=(*Aux1);
               }
               else
               { //Rotació DI doble
                    (*Aux2)=(*Aux1)->pEsquerra;
                    (*Aux1)->pEsquerra=(*Aux2)->pDret;
                    (*Aux2)->pDret=(*Aux1);
                    (*Arrel)->pDret=(*Aux2)->pEsquerra;
                    (*Aux2)->pEsquerra=(*Arrel);
                    if ((*Aux2)->Equilibri == 1) (*Arrel)->Equilibri=-1;
                    else (*Arrel)->Equilibri=0;
                    if ((*Aux2)->Equilibri == -1) (*Arrel)->Equilibri=-1;
                    else (*Arrel)->Equilibri=0;
                    (*Arrel)=(*Aux2);
               }
               (*Arrel)->Equilibri=0;
               h=FALS;
               break;
           }
     }
     else
     {
          (*Arrel)->Comptador++;
          *h=FALS;
     }
}
La funció ImprimeixArbre

És la mateixa que la de tots els exemples anteriors.

 void ImprimeixArbre(Alumnes * Arrel)
{
     int i;
     if (Arrel!=NULL)
     {
            ImprimeixArbre(Arrel->pEsquerra);
            puts(Arrel->Nom);
            ImprimeixArbre(Arrel->pDret);
     }
}

L'operació d'esborrar un registre és del mateix tipus de la inserció dins els arbres equilibrats. Es a dir, que quan esborrem un node d'un arbre es fa necessari comprovar l'equilibri i restablir-ho, aquest equilibri, cas que s'hagi perdut.

Les funcions necessàries per a esborrar un node en el mateix exemple que l'exemple precedent són les següents:
 
 
Declaració de funcions
La funció que elimina és la funció Esborra que ha fa ús de les altres per a realitzar la seva tasca.		 void Esborra(char Nom[], Alumnes ** Arrel, Boolean *h);
void Esbor(Alumnes ** Node, Boolean *h, Alumnes ** Aux);
void Equilibra1(Alumnes ** Node, Boolean *h);
void Equilibra2(Alumnes ** Node, Boolean *h);
La funció main
Hem declarat un vector amb noms per tal d'inserir dins l'arbre.
Fem notar que el paràmetre h es passa per referència a totes les funcions. Com que la funció Busca i la funció Esborra han de rebre h amb valor FALS hem de tenir curar de donar-li aquest valor abans de fer la crida a aquestes funcions.		 main()
{
     Alumnes * Arrel;
     char Nom[50];
     Boolean h=FALS;

     char NomMat[20][50]={"jorge","nuria","pedro","maria","vicente",
                                            "ana","alma","xavi","zampo","zambudio","lorena"};

     int i;

     Arrel=NULL;

     for(i=0;i<11;i++)   Busca(NomMat[i], &Arrel,&h);
     ImprimeixArbre(Arrel);

     h=FALS;
     Esborra("pedro",&Arrel,&h);
     ImprimeixArbre(Arrel);
}
La funció esborra
Funcions traduïdes del llibre 

ALGORITMOS +
ESTRUCTURAS
DE DATOS =
PROGRAMAS
NIKLAUS WIRTH
EDICIONES DEL CASTILLO

 void Esborra(char Nom[], Alumnes ** Arrel, Boolean * h)
{
     Alumnes ** Aux;
     if ((*Arrel) == NULL)
     {
          printf("El registre no hi és dins l'arbre");
          h=FALS;
     }
     else if (strcmp(Nom, (*Arrel)->Nom ) < 0)
     {
          Esborra(Nom,&(*Arrel)->pEsquerra,h);
          if (*h) Equilibra1(&(*Arrel),h);
     }
     else if (strcmp(Nom, (*Arrel)->Nom ) > 0)
     {
          Esborra(Nom,&(*Arrel)->pDret,h);
          if (*h) Equilibra2(&(*Arrel),h);
     }
     else
     { //Esborrar *Arrel
          (*Aux)=(*Arrel);
          if ((*Aux)->pDret==NULL)
         {
             (*Arrel)=(*Aux)->pEsquerra;
             *h=CERT;
           delete (*Aux);
         }
        else if ((*Aux)->pEsquerra==NULL)
        {
             (*Arrel)=(*Aux)->pDret;
             *h=CERT;
             delete (*Aux);
        }
        else
        {
             Esbor(&(*Aux)->pEsquerra,h,&(*Arrel));
             if (*h) Equilibra1(&(*Arrel),h);
        }
     }
}
  void Esbor(Alumnes ** Node, Boolean *h, Alumnes ** Aux)
{  //h = Fals
     Alumnes ** Aux2;
     if ((*Node)->pDret != NULL)
     {
          Esbor(&(*Node)->pDret,h,&(*Aux));
          if (*h) Equilibra2(&(*Node),h);
     }
     else
     {
          *Aux2 = *Node;
          strcpy((*Aux)->Nom,(*Node)->Nom);
          (*Aux)->Comptador=(*Node)->Comptador;
          (*Aux)->pEsquerra=(*Node)->pEsquerra;

          *h=CERT;
          delete (*Aux2);
     }
}
  void Equilibra1(Alumnes ** Node, Boolean *h)
{
     Alumnes ** Aux1;
     Alumnes ** Aux2;
     int e1,e2;

     //h = Cert, la branca esquerra ha disminuit

     switch ((* Node)->Equilibri)
     {
          case -1: (* Node)->Equilibri=0; break;
          case  0: (* Node)->Equilibri=1; *h=FALS;break;
          case  1: //Reequilibrar
                     (*Aux1)=(*Node)->pDret;
                     e1= (*Aux1)->Equilibri;
                     if (e1>=0)
                    { //Rotació DD simple
                        (*Node)->pDret= (*Aux1)->pEsquerra;
                        (*Aux1)->pEsquerra=(*Node);
                        if (e1==0)
                        {
                             (*Node)->Equilibri=1;
                             (*Aux1)->Equilibri=-1;
                             *h=FALS;
                      }
                      else
                      {
                             (*Node)->Equilibri=0;
                             (*Aux1)->Equilibri=0;
                      }
                      (*Node)=(*Aux1);
                 }
                 else
                 { //Rotació DI Doble
                      (*Aux2)=(*Aux1)->pEsquerra;
                      e2=(*Aux2)->Equilibri;
                      (*Aux1)->pEsquerra=(*Aux2)->pDret;
                      (*Aux2)->pDret=(*Aux1);
                      (*Node)->pDret=(*Aux2)->pEsquerra;
                      (*Aux2)->pEsquerra=(*Node);
                      if (e2==1) (*Node)->Equilibri=-1;
                      else (*Node)->Equilibri=0;
                      if (e2==-1) (*Aux1)->Equilibri=1;
                     else (*Aux1)->Equilibri=0;
                      (*Node)=(*Aux2);
                      (*Aux2)->Equilibri=0;
                 }
                 break;
         }
}
  void Equilibra2(Alumnes ** Node, Boolean *h)
{
     Alumnes ** Aux1;
     Alumnes ** Aux2;
     int e1,e2;

     //h = Cert, la branca esquerra ha disminuit

     switch ((* Node)->Equilibri)
     {
          case  1: (* Node)->Equilibri=0; break;
          case  0: (* Node)->Equilibri=-1; *h=FALS;break;
          case -1: //Reequilibrar
                         (*Aux1)=(*Node)->pEsquerra;
                         e1= (*Aux1)->Equilibri;
                         if (e1<=0)
                         { //Rotació II simple
                              (*Node)->pEsquerra= (*Aux1)->pDret;
                              (*Aux1)->pDret=(*Node);
                              if (e1==0)
                              {
                                   (*Node)->Equilibri=-1;
                                   (*Aux1)->Equilibri=1;
                                   *h=FALS;
                              }
                              else
                              {
                                   (*Node)->Equilibri=0;
                                   (*Aux1)->Equilibri=0;
                              }
                              (*Node)=(*Aux1);
                         }
                         else
                         { //Rotació ID Doble
                             (*Aux2)=(*Aux1)->pDret;
                             e2=(*Aux2)->Equilibri;
                             (*Aux1)->pDret=(*Aux2)->pEsquerra;
                             (*Aux2)->pEsquerra=(*Aux1);
                             (*Node)->pEsquerra=(*Aux2)->pDret;
                             (*Aux2)->pDret=(*Node);
                             if (e2==-1) (*Node)->Equilibri=1;
                              else (*Node)->Equilibri=0;
                             if (e2==1) (*Aux1)->Equilibri=-1;
                              else (*Aux1)->Equilibri=0;
                             (*Node)=(*Aux2);
                             (*Aux2)->Equilibri=0;
                         }
                         break;
                 }
}

13.6. Altres tipus d'arbres

Fins aquest apartat hem fet solament arbres binaris, és a dir arbres en els que de cada node surten com a màxim dos fills. Però aquesta situació no és la situació normal, ja que normalment, els exemples de la realitat, són d'arbres amb més de dues branques per node.

Així, l'arbre de directoris d'un disc dur, l'arbre genealògic en el que una persona pot tenir més de dos fills són exemples d'arbres que podem anomenar arbres multicamí.

Existeixen com a eina de treball fonamental els Arbres B que són arbres multicamí pensats per a treballar en dispositius d'enmagatzament extern i grans quantitats de dades, i en els que els algoritmes de cerca, inserció i esborrat necessiten molts menys passos que els mateixos algoritmes per a arbres binaris.

És recomanable la lectura del capítol corresponent a arbres del llibre esmentat anteriorment:

ALGORITMOS  + ESTRUCTURAS DE DATOS = PROGRAMAS
NIKLAUS WIRTH
EDICIONES DEL CASTILLO

13.7. Exercicis

  1. La pregunta tres té un algoritme de creació d'arbres perféctament equilibrats. Afegeix les funcions per a imprimir l'arbre creat en preordre, postordre i ordre central.

    2.  
  2. Fes a ma l'arbre que crea el programa de la pregunta tres (arbres perféctament equilibrats) amb les dades següents:


    3. 21     8     9    11     13     4     5     2     7     91
    13    15   26     3       1     6   10   12    23    19
     

  3. Escriu els algoritmes de la pregunta 4 (Cerca, cerca e inserció, esborrat) per a una estructura en la que les dades corresponent a una agenda d'almunes de la classe. El camp clau ha de contenir els primer cognom..

    4. Comproba el resultat. Per  a veure com ha quedat l'arbre has de fer ús del debug del C. Posa un punt de break després de fer totes les inserccions i amb l'opció Inspect ves fent el recorregut per tots els nodes a partir del node arrel.
     
  4. Fes el mateix exercici que abans pero ara amb els algoritmes per a arbres equilibrats.