ARBORELE - Arbore binar, parcurgerea arborelui

Arborele

Listele reprezinta mijloace simple si practice de a reprezenta organizarea liniara a obiectelor.

Realitatea complexa pe care o modelam ne arata insa legaturi intre obiecte care depasesc modelul liniar. Grafurile, digrafurile si ca un caz particular al acestora - arborii - reprezinta structuri capabile sa surprinda complexitatea legaturilor dintre obiecte.

Arborele

Cu ajutorul arborilor se pot descrie foarte fidel structurile de tip ierarhic (piramidal). Iata cateva exemple: structura de conducere a unei firme, organizarea administrativ teritoriala dintr-o tara, organizarea unei armate, structura unei carti, descrierea unui obiect ca o reuniune de obiecte componente care, la randul lor, se descompun in obiecte s.a.m.d.

Ultimul exemplu reliefeaza cel mai bine caracterul recursiv al structurii arborescente. Definim recursiv un arbore ca un set finit de unul sau mai multe noduri, astfel incat sunt indeplinite conditiile:

exista un nod unic numit radacina arborelui;

celelalte noduri sunt repartizate in k>0 seturi disjuncte, fiecare set fiind la randul sau un arbore.

Grafic, putem reprezenta un arbore ca o multime de noduri sau varfuri (fiecare obiect are asociat un nod) legate intre ele prin arce care reflecta natura relatiei dintre obiecte.

Terminologia folosita in descrierea arborilor este imprumutata din asemanarea structurii cu un arbore intors sau din paralelismul cu arborii genealogici.

Definim nivelul unui nod, recursiv, astfel:

Nivelul nodului radacina este 1;

Nivelul oricarui nod diferit de nodul radacina este nivelul tatalui sau +1.

Un subarbore B pentru arborele A este orice arbore care indeplineste conditiile:

nodurile lui B sunt si noduri in A;

arcele lui B sunt si arce in A;

orice frunza din A care poate fi atinsa din radacina arborelui B trebuie sa apartina multimii nodurilor lui B.

Inaltimea unui arbore este maximum dintre nivelele nodurilor terminale sau echivalent 1+maximul dintre inaltimile subarborilor sai.

Un tip de arbore special, cu aplicatii interesante in tehnicile de programare este arborele binar.

Arborele binar este arborele in care un nod are cel mult doi fii. In aceasta situatie se poate vorbi (pentru un arbore nevid) de cei doi subarbori (stang si drept) ai unui arbore. Schematic avem:

Arbore binar

Reprezentarea in memorie a arborilor poate fi statica sau dinamica. In cazul static arborii se pot simula cu ajutorul tablourilor.

Avantajul acestei implementari este urmatorul: fiecarui nod avand cel mult un tata, ii atasam in tablou o singura informatie (Luam arbore(i)=0 daca nodul i este radacina).

Datorita dinamismului structurilor modelate printr-un arbore, varianta de implementare dinamica este preferabila variantei statice. In acest caz, daca arborele este binar, o celula va contine trei campuri: un camp pentru memorarea informatiei specifice nodului (informatia utila) si doua campuri care contin adresa radacinii subarborelui stang, respectiv drept.

Operatiile fundamentale asupra arborilor includ: parcurgerea arborelui, stergerea, cautarea sau adaugarea unui nod.

Vom prezenta operatia de parcurgere a unui arbore, care consta in vizitarea fiecarui nod o singura data si prelucrarea informatiei continuta in el.

Doua tipuri de parcurgere a unui arbore sunt folosite frecvent: parcurgerea in latime si parcurgerea in inaltime.

In cazul parcugerii in latime se viziteaza si prelucreaza nodurile in ordinea: radacina, nodurile de la stanga spre dreapta de pe primul nivel, de pe al doilea nivel etc. Astfel, rezultatul parcurgerii in latime a arborelui din figura 12.18 este lista de noduri 1, 2, 5, 6, 3, 4, 7, 8, 9, 10.

Putem realiza pacurgerea in latime a unui arbore binar printr-un algoritm care utilizeaza o coada drept element ajutator:

Algoritm Parc_latime (radacina):

Initializeaza coada

Adauga radacina in coada

Cat timp coada nu este vida executa

Extrage element p din coada

Prelucreaza informatia utila din p

Daca p are fiu stang atunci

Adauga fiu stang in coada

Daca p are fiu drept atunci

Adauga fiu drept in coada

Sfarsit.

In cazul parcurgerii in adancime trecerea de la un nod x la fratele sau y din dreapta se face numai dupa ce s-au vizitat si prelucrat toate nodurile descendente din x. Liniarizarea arborelui din figura 12.18 prin parcurgerea in adancime este urmatoarea: 1, 2, 3, 4, 5, 7, 8, 9, 10, 6. Revenirea la fratele y dupa vizitarea descendentilor lui x poate fi realizata utilizand o stiva ajutatoare.

Pentru arborii binari, trei tipuri de parcurgere in adancime sunt uzuale: parcurgerea in preordine (RSD), in inordine (SRD) si in postordine (SDR). Prescurtarile au urmatoarea semnificatie:

• RSD - Radacina, Stanga, Dreapta - se prelucreaza radacina, subarborele stang, subarborele drept;
• SRD - Stanga, Radacina, Dreapta - se prelucreaza subarborele stang, radacina, subarborele drept;
• SDR - Stanga, Dreapta, Radacina - se prelucreaza subarborele stang, subarborele drept, radacina.

Pentru executia programelor care urmeaza aveti nevoie sa generati mai intai un arbore (optiune G). Introducerea de date se va face mai intai pentru subarborele stang, apoi pentru cel drept. Pentru a intelege mai bine, analizati figura de mai jos:

Arborele propriu-zis contine doar nodurile colorate. Zerourile 'legate' de arbore prin linii punctate doresc doar sa ilustreze locurile in care trebuie intordus terminatorul de ramura (0 pentru programele date).

Urmatorul esantion desprins din executia programului este comun pentru ambele variante (recursiv, nerecursiv) si va ajuta sa intelegeti modul in care se genereaza arborele (care va fi ulterior parcurs prin cele 3 metode).

Pentru arborele din figura, procedura de generare a arborelui in cele doua programe va decurge astfel:

G: Generare Arbore Binar 1. Parcurgere in preordine (RSD) 2. Parcurgere in inordine (SRD) 3. Parcurgere in postordine (SDR) 4. Numar noduri arbore 5. Inaltime arbore S. Sfarsit program Optiunea dvs. va rog: g x=100 x=20 x=0 x=10 x=0 x=0 x=30 x=40 x=0 x=50 x=0 x=0 x=0 G: Generare Arbore Binar 1. Parcurgere in preordine (RSD) 2. Parcurgere in inordine (SRD) 3. Parcurgere in postordine (SDR) 4. Numar noduri arbore 5. Inaltime arbore S. Sfarsit program Optiunea dvs. va rog:

//ArbRec

# include 'stdio.h'

# include 'conio.h'

# include 'alloc.h'

const max_aloc=50;

struct pstruct

;

typedef struct pstruct PSTRUCT;

PSTRUCT *rad,*p;

int x,m;

char ch;

PSTRUCT *Gener_Arb()

else return NULL;

void RSD(PSTRUCT *p)

void SRD(PSTRUCT *p)

void SDR(PSTRUCT *p)

int NumarNod(PSTRUCT *p)

int Inaltime(PSTRUCT *p)

void main(void)

clrscr();

}

while (ch!='S');

TEMA

Pentru fixarea cunostintelor dobandite pana in prezent, inainte de a trece mai departe, este bine sa rezolvati aceste teme. Dupa rezolvarea lor puteti selecta o noua conversatie.

Intrebari de control

Probleme

Definiti: lista, stiva, coada, arborele.

Ce este o lista dublu inlantuita?

Listati functiile programului Static_Stiva

Listati functiile programului Dinamic_Coada

Listati functiile programului ArbRec

Sa se elaboreze programe / subprograme (Borland) C pentru:

Calculul numarului de aparitii ale unui numar intreg a printre componentele unei liste implementate static;

Calculul sumei termenilor de rang impar dintr-o lista simplu inlantuita;

Calculul sumei termenilor mai mari strict decat un numar intreg a dintr-o lista dublu inlantuita;

Calculul numarului de elemente pozitive dintr-o stiva (implementata static sau dinamic);

Concatenarea (alipirea) a doua cozi implementate dinamic;

Calculul sumei valorilor din nodurile unui arbore binar, cuprinse in intervalul [a,b].