Lucrul cu arbori

Din punct de vedere matematic un arbore este un tip special de graf.

Un graf are noduri si laturi. Laturile leaga doua noduri. Laturile pot fi orientate sau neorientate. Ne putem imagina o latura orientata ca fiind o strada cu sens unic, iar o latura neorientata ca fiind o strada pe care se poate circula in ambele sensuri. Fiind date nodurile x si y convenim sa notam latura orientata ce permite trecerea de la nodul x la nodul y prin x-y. O latura ce leaga nodurile x si y este neorientata daca exista in graf si perechea y-x.

Un drum intr-un graf este un traseu parcurs de-a lungul laturilor unui graf. Convenim sa notam nodurile cu numere si laturile cu perechi de numere ca mai sus.

Spre exemplu sa consideram un graf format din nodurile 1, 2, 3, 4 si laturile: 1-2, 2-3, 3-1, 1-4, si 4-2. Un drum in acest graf poate fi 1-2-3. Un drum care se intoarce in acelasi nod venind pe o alta latura se numeste un ciclu. Un graf care nu ara cicluri se numeste arbore. Un exemplu de arbore este reprezentat in figura urmatoare:

Pornind de la oricare din nodurile sale, un arbore neorientat poate fi decris in mod unic prin asociind fiecarui nod multimea nodurilor legate la el, mai putin nodurile care au fost deja asociate. Spre exemplu graful urmator

poate fi descris prin asocierile

1-{2,3,4}; 2-{5,6,7}; 3-{8}; 4-{}; 5-{}; 6-{}; 7-{}; 8-{};

sau la fel de bine prin

2-{1,5,6,7}; 1-{3,4}; 3-{8}; 4-{}; 6-{}; 7-{}; 8-{};

Acest mod de descriere defineste de fapt o ierarhie de tip arbore genealogic. In prima descriere putem interpreta nodul 1 ca fiind tatal nodurilor 2, 3, si 4, in timp ce nodul 2 are descendenti  directi nodurile 5, 6 si 7, etc.

In toate limbajele de programare sunt necesari artfel de arbori. Exemplu urmator defineste o structura de tip arbore si o foloseste(arbori0.c)

/* lucrul cu arbori*/
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
typedef char * PString;
typedef struct TNod * PNod;
typedef struct TNod * NodArray[1];//
typedef NodArray * PNodArray;
struct TNod {
    PString Name;
    int ID;
    int Len;
    PNod Tata;
    PNodArray Next;
};

/**** rutina de alocare a stringurilor pe heap */
PString NewStr(PString str){
PString p=NULL;
int len=strlen(str);
if (len==0)return p;
p=(PString)malloc(len+1);
strcpy(p,str);
return p;
}

PNod NewNod(PString name,int id){
  PNod p;
  p=(PNod)malloc(sizeof(TNod)); /*aloc spatiu pentru Nod */
  p->Name=NewStr(name);
  p->ID=id;
  p->Tata=NULL;
  p->Len=0;
  p->Next=NULL;
  return p;
}
void RenameNod(PNod nod, PString name){
  free(nod->Name);
  nod->Name=NewStr(name);
}

void Addfiu(PNod tata, PNod fiu){
  PNodArray a;int i,len;
  if(tata->Len>=1){ /* ca sa nu adauge fii deja adaugati */
    for(i=0;i<tata->Len;i++){
      printf("---> Acum i=%d si len=%d\n",i,tata->Len);
      if(fiu==(*tata->Next)[i]) return;
    }
  }
  len=++(tata->Len);
  /* operatorii -> si ++ au aceeasi precedenta dar se evalueaza
      de la stanga la dreapta */
  a=(PNodArray)malloc((len)*sizeof(PNod));/*aloc spatiu pentru array-ul de ponteri la structuri de tip TNod */
  (*a)[len-1]=fiu;
  for(i=0;i<len-1;i++) {
    printf("Acum i=%d si len=%d\n",i,len);
    (*a)[i]=(*tata->Next)[i];
  }
  if(len>=2) free(tata->Next);
  tata->Next=a;
  fiu->Tata=tata;/* fac si legatura inversa */
}

void Delfiu(PNod tata, PNod fiu){
  if (tata->Len==0)return;int unde=-1;
  for(int i=0;i<tata->Len;i++){
    if((*tata->Next)[i]==fiu){
      unde=i;
      break;
    }
  }
  if(unde!=-1){/* n-am ce sterge daca nu exista */
    PNodArray a;int k=0;
    if(tata->Len>1) a=(PNodArray)malloc((tata->Len-1)*sizeof(PNod));
      else {tata->Len=0;free(tata->Next);tata->Next=NULL;return;}
    for(i=0;i<tata->Len;i++){
      if(i!=unde) { (*a)[k]= (*tata->Next)[i]; k++;}
    }
    free(tata->Next);
    tata->Next=a;tata->Len--;
  } else fprintf(stderr,"***** %s nu este fiu al lui %s!\n",fiu->Name,tata->Name);
  return;
}
main(){
clrscr();
PNodArray n;
n=(PNodArray)malloc(4*sizeof(PNod));
/* printf("4*sizeof(PNod)=%d\n",4*sizeof(PNod)); */
PNod Nods[4];
PNod unu,doi, trei, patru;
unu=NewNod("Unu",1);
doi=NewNod("Doi",2);
trei=NewNod("Trei",3);
patru=NewNod("Patru",4);
Nods[0]=unu;Nods[1]=doi;Nods[2]=trei;Nods[3]=patru;
for(int i=0;i<4;i++)printf("Nodul %d are numele %s\n",i,Nods[i]->Name);
(*n)[3]=unu;
(*n)[2]=doi;
(*n)[1]=trei;
(*n)[0]=patru;
printf("\n");
for(i=0;i<4;i++)printf("Nodul %d are numele %s\n",i,(*n)[i]->Name);
Addfiu(unu,doi);
Addfiu(unu,trei);
Delfiu(unu,patru);

for(i=0;i<unu->Len;i++)printf("fiul al %d-lea este %s\n",i+1,(*unu->Next)[i]->Name);
Addfiu(unu,doi);
for(i=0;i<unu->Len;i++)printf("fiul al %d-lea este %s\n",i+1,(*unu->Next)[i]->Name);
Addfiu(unu,patru);
RenameNod(patru,"Four");RenameNod(doi,"Two");
RenameNod(trei,"Three");
for(i=0;i<unu->Len;i++)printf("fiul al %d-lea este %s\n",i+1,(*unu->Next)[i]->Name);
Delfiu(unu,unu);printf("\n ****    Incerc sa sterg unu\n");
for(i=0;i<unu->Len;i++)printf("fiul al %d-lea este %s\n",i+1,(*unu->Next)[i]->Name);
Delfiu(unu,trei);printf("\n ****    Incerc sa sterg trei\n");
for(i=0;i<unu->Len;i++)printf("fiul al %d-lea este %s\n",i+1,(*unu->Next)[i]->Name);
Delfiu(unu,doi);printf("\n ****    Incerc sa sterg doi\n");
for(i=0;i<unu->Len;i++)printf("fiul al %d-lea este %s\n",i+1,(*unu->Next)[i]->Name);
Delfiu(unu,patru);printf("\n ****    Incerc sa sterg patru\n");
for(i=0;i<unu->Len;i++)printf("fiul al %d-lea este %s\n",i+1,(*unu->Next)[i]->Name);

}

Dupa rularea acestui cod la consola text se obtine:

Nodul 0 are numele Unu
Nodul 1 are numele Doi
Nodul 2 are numele Trei
Nodul 3 are numele Patru

Nodul 0 are numele Patru
Nodul 1 are numele Trei
Nodul 2 are numele Doi
Nodul 3 are numele Unu
---> Acum i=0 si len=1
Acum i=0 si len=2
fiul al 1-lea este Doi
fiul al 2-lea este Trei
---> Acum i=0 si len=2
fiul al 1-lea este Doi
fiul al 2-lea este Trei
---> Acum i=0 si len=2
---> Acum i=1 si len=2
Acum i=0 si len=3
Acum i=1 si len=3
fiul al 1-lea este Two
fiul al 2-lea este Three
fiul al 3-lea este Four

 ****    Incerc sa sterg unu
fiul al 1-lea este Two
fiul al 2-lea este Three
fiul al 3-lea este Four

 ****    Incerc sa sterg trei
fiul al 1-lea este Two
fiul al 2-lea este Four

 ****    Incerc sa sterg doi
fiul al 1-lea este Four

 ****    Incerc sa sterg patru
 

Cornel Mironel Niculae, 2003-2004

06-Jan-2004