Implementarea unui arbore binar folosind liste înlanţuite

Un arbore binar este un arbore în care fiecare nod are cel mult doi fii, arborele din stânga şi arborele din dreapta. Fiecare nod dintr-un arbore binar se reprezintă de obicei printr-o structură în care folosim un câmp pentru a stoca informaţia (eticheta) şi doi pointeri către cele două noduri, pointerul către nodul fiu din stânga si pointerul către nodul fiu din dreapta. Dacă unul sau amândoi fiii unui nod lipsesc, pointerii corespunzători au valoarea zero.

Definim structura cu specificaţiile de mai sus.

typedef struct NodeTree {

    char info;   //informaţia conţinută în nod

    struct NodeTree *stg; //legatura către nodul stang

    struct NodeTree *drp;       //legatura către nodul drept

} NodeTree;

Acum că avem definită structura NodeTree, trecem la funcţia ce va crea un arbore binar dintr-o secvenţa de caractere primită ca parametru. Secvenţa este constituită din litere mari şi caracterele ( , ) $. Seminificaţia acestora este următoarea:

• literele reprezintă informaţia dintr-un nod;
• '(' defineşte un nivel inferior;
• ',' separă sub-arborele stâng de cel drept;
• ')' marchează stârşitul nivelului inferior;
• '$' marchează lipsa sub-arborelui respectiv.

Exemplu: "A ( B , C ( D , E ( F , $ ) )", iar arborele va arăta cam asa:

Funcţia "create(char *)" va primi ca argument secvenţa de caractere şi va returna nodul rădăcină al arborelui. Logica din spatele acestei funcţii este următoarea:

• parcugem secvenţa de caractere şi verificăm dacă caracterul este literă mare. Dacă da, atunci alocăm spaţiu pentru un nod de tip NodeTree, în campul pentru informaţie salvăm caracterul, fii săi vor fi nuli, apoi îl punem pe o stivă.
  
  
  
  
  
  
  
  Cam aşa va arata stiva noastră după ce au fost introduse toate nodurile.


• după ce avem elementele pe stivă începem să facem legăturile dintre noduri şi fii lor.
  
  
  Ultimul element de pe stivă va fi nodul rădăcină pe care funcţia noastă îl va returna.

Legăturile dintre noduri şi fii lor sunt realizate de următoarea scvenţă de cod:

NodeTree *fs, *fd;
     fs=(NodeTree*)malloc(sizeof(NodeTree));
     fd=(NodeTree*)malloc(sizeof(NodeTree));
     fd=top(&S);   //scoatem fiul drept de pe stivă
     pop(&S);      //eliminăm fiul drept
     fs=top(&S);   //scoatem fiul stâng de pe stivă
     pop(&S);      //eliminăm fiul stâng
     v=top(&S);    //scoatem nodul părinte pentru cei doi fii
     pop(&S);      //îl eliminăm de pe stivă
     v->stg=fs;    //realizăm legăturile dintre aceştia
     v->drp=fd;
     push(&S,v);   //îl punem din nou pe stivă

Acum că avem arborele avem nevoie de o modalitate de a-l afişa. Exista 4 modalităţi de afişare a unui arbore binar: PreOrdine, InOrdine, PostOrdine şi parcurgerea BFS( Breadth-first Search ). Primele 3 metode diferă doar prin ordinea în care sunt vizitate cele 3 componente ale arborelui.

• în parcurgerea PreOrdine mai întâi este vizitată rădăcina apoi subarborele stâng apoi cel drept. 

void RSD(NodeTree* v, void viziteaza(NodeTree*))
{
    if (v ==NULL)return;
    else
    {
        viziteaza(v); // o procedură ce afisează informaţia din nod
        RSD(v->stg, viziteaza); // parcurgere recursivă pentru fiecare subarbore
        RSD(v->drp, viziteaza);
    }
}

• în parcurgerea InOrdine mai întâi este vizitat subarborele stâng, rădăcina apoi cel drept.
• în parcurgerea PostOrdine mai întâi este vizitat subarborele stâng, subarborele drept apoi rădăcina.

În ultima metodă de afişare a arborelui parcurgerea este realizată pe nivele, începând cu rădăcina şi continuând cu fiecare nivel.

void BFS(NodeTree *t, void viziteaza(NodeTree*))
{
    if (t==NULL) return;
    else
    {
        Queue q;
  q.prim=NULL;
  q.nrElt=0;
        insert(&q, t);
        while (!isEmpty(&q))
        {
            NodeTree* v;
            v=read(&q);
            viziteaza(v);
            if (v->stg!=NULL)insert(&q, v->stg);
            if (v->drp!=NULL)insert(&q, v->drp);
            remove(&q);
        }
    }
}