Pe lângă structurile liniare, există și structuri neliniare, prin care sunt definite legăturile de date ierarhice. Pentru aceasta, se folosesc grafice, printre care structuri de rețea și arbori. Luați în considerare un fel de copac - un copac binar.
Un binar (binar) arbore - este un set finit de elemente, care este fie gol sau conține un element numit rădăcina arborelui, iar elementele rămase ale pluralității sunt împărțite în două submulțimi disjuncte, fiecare dintre care este ea însăși un arbore binar. Aceste subseturi sunt numite subrețele stânga și dreapta ale arborelui sursă.
Fig. 8 Arbore binar
În Fig. 8 prezintă modul cel mai comun de reprezentare a unui arbore binar. Se compune din nouă noduri. Rădăcina arborelui este nodul A. subtree lăsat are o rădăcină B, iar subarborele dreapta - rădăcina C. Ele sunt conectate ramurile respective care provin din ramura A. Absența înseamnă subramificație gol. De exemplu, un subtree cu rădăcina C nu are subtree stânga, este gol. Substrat subțire și subțire cu rădăcină E. Subtreme binare cu rădăcini D. G. H și eu avem subtretre goale stânga și dreapta. Un nod care are substraturi goale dreapta și stânga se numește o frunză. Dacă fiecare nod al unui copac binar care nu este o frunză are subterne ne-goale și stânga, atunci arborele este numit strict binar
nod nivel în arborele binar este definită după cum urmează: nivelul rădăcină este întotdeauna zero, iar apoi numărul de nivel atunci când se deplasează de la rădăcină de copac este crescut cu 1 în ceea ce privește strămoșul lor imediată. Adâncimea copacului binar este nivelul maxim al frunzei copacului, cu alte cuvinte, lungimea celei mai lungi căi de la rădăcină la frunza copacului. Nodurile copacului pot fi numerotate în conformitate cu următoarea schemă (a se vedea figura 9)
Fig. 9 Schema de numerotare a nodurilor binare
Numărul de rădăcină este întotdeauna 1, copilul lăsat devine numărul 2 pe dreapta - Cameră de stânga 3. nodul descendent 2 ar trebui să primească numărul 4, iar dreapta - 5, nodul descendent din stânga 3 primește numărul 6, dreptul - 7, etc. Nodurile inexistente nu sunt numerotate, însă acestea nu încalcă ordinea indicată, deoarece numerele lor nu sunt utilizate. Cu acest sistem de numerotare din arbore, fiecare nod primește un număr unic.
Complet nivel arbore binar n - este un arbore în care fiecare nod nivel n este un nod frunză și fiecare nivel n mai mic are subarbori stânga și la dreapta nevide.
Un arbore binar aproape complet este definit ca un arbore binar pentru care există un întreg non-negativ k astfel încât:
1) fiecare frunză din arbore are un nivel k sau k +1;
2) dacă nodul copac are un descendent drept al nivelului k + 1, atunci toți descendenții săi din stânga care sunt foi au și nivelul k +1.
Având în vedere acțiunile pe arbori, putem spune că pentru a construi un copac este necesar să se formeze noduri și, după ce au fost determinate locul de includere în avans, să le includem în copac. Numărul de noduri este determinat de necesitate. Algoritmul de includere trebuie să fie cunoscut și constant. Nodurile copacului pot fi folosite pentru a stoca orice informație.
Poate apărea o problemă și distrugerea unui copac într-un moment în care dispare nevoia (în informațiile înregistrate în elementele sale). În unele cazuri, poate fi necesar să distrugeți subtreea.
Pentru ca un set de noduri să formeze un copac, este necesar să se formeze cumva și să se utilizeze legăturile nodurilor cu strămoșii și descendenții lor. Toate acestea sunt foarte asemănătoare cu acțiunile asupra elementelor din listă.
Luați în considerare un exemplu de formare a unui copac binar. Să presupunem că este necesar să se formeze un arbore binar, nodurile (elemente) care au următoarele valori caracteristice: 20, 10, 35, 15, 17, 27, 24, 8, 30. în același mod în care vor veni să fie incluse într-un arbore binar. Primul nod din arbore (root) este un nod cu o valoare de 20. Notă: Căutarea locației următorului element începe întotdeauna de la rădăcină. Prin în picioare pe partea stângă este conectat elementul 10 la rădăcinile elementului corect conectat 35. Apoi, elementul 15 este conectat la partea dreaptă a 10, merge calea: rădăcina de 20 - stânga - punctul 10 - spre dreapta - conexiunea, deoarece nu există nici o cale mai departe. Procesul continuă până când elementele incluse sunt epuizate. Rezultatul este arătat în Fig. 10.
Fig. 10 Construirea unui arbore binar.
Valorile elementelor de copac: 20, 10, 35, 15, 17, 27, 24, 8, 30
Atunci când creați un arbore binar, întrebarea este rezolvată separat, cu posibilitatea de a include elemente cu atribute de duplicare. algoritm de căutare binară poate fi poziționat corect atunci când nodurile din copac, dar de căutare a inclus elemente care au dificultăți, deoarece numai unul dintre duplicatele vor fi selectate în formularul standard de căutare. Pentru a detecta toate duplicatele, ar trebui aplicat un algoritm o astfel de traversare a arborelui, în care fiecare nod al copacului va fi selectat o singură dată.
Iată un exemplu de descriere a câmpurilor și a elementelor necesare pentru a construi un copac.
Când lucrați cu un arbore binar, sunt posibile următoarele sarcini de bază:
1) crearea unui element, a unui nod de copac,
2) includerea într-un arbore folosind algoritmul de căutare binar,
3) găsirea în arborele nodului a unei valori date a caracteristicii cheie,
4) determinarea adâncimii maxime a copacului,
5) determinarea numărului de noduri ale unui copac,
6) determinarea numărului de frunze ale unui copac,
7) o serie de alte probleme.
Iată câteva exemple de proceduri care implementează sarcinile de bază de lucru cu un arbore binar.
NOTĂ: un element cu un atribut cheie duplicator nu este inclus în arbore.
Acest arbore algoritm de mișcare poate fi baza pentru problema determinării nivelului maxim (adâncime) a arborelui binar, determina dacă există un element în arborele cu o anumită valoare a atributului cheie, etc. adică sarcinile a căror soluție se bazează pe algoritmul de căutare binar pentru arbore.
Cu toate acestea, nu toate sarcinile pot fi rezolvate folosind căutarea binară, de exemplu, numărarea numărului total de noduri dintr-un arbore. Aceasta necesită un algoritm care vă permite să vizitați o dată fiecare nod al arborelui.
Când vizitați un site, este posibilă una din următoarele trei acțiuni:
1) procesează nodul (un set specific de acțiuni nu este important în același timp). Denumim această acțiune de către O (prelucrare);
2) mergeți la legătura din stânga (notată cu - L);
3) mergeți la linia dreaptă (notată cu - P).
Puteți organiza ocolirea nodurilor binare ale copacilor executând o singură secvență de acțiuni pe fiecare nod. Acțiunile pot fi combinate în orice ordine, dar trebuie să fie constante în sarcina specifică de a traversa arborele.
Folosind exemplul unui arbore din Fig. 10 ilustrează opțiunile pentru traversarea arborelui.
1) Bypassing tipul de OLP. O astfel de ocolire se numește "în ordine directă", "în profunzime". El va da următoarea ordine de vizitare a nodurilor:
20, 10, 8, 15, 17, 35, 27, 24, 30
2) Bypass de tip LOP. Se numește "simetric" și dă următoarea ordine a nodurilor vizibile:
8, 10, 15, 17, 20, 24, 27, 30, 35
3) Bypassing tipul de LPO. Se numește "în ordine inversă" și dă următoarea ordine a nodurilor vizitate:
8, 17, 15, 10, 24, 30, 27, 35, 20
Dacă luăm în considerare sarcina care necesită traversal continuă a arborelui, pentru unii dintre ei comanda parcurgeri, în general, de exemplu, numărarea numărului de noduri din copac, numărul de frunze / informații nu critică nici un element de frunze care au predeterminat, etc. Cu toate acestea, o astfel de sarcină, cum ar fi distrugerea unui arbore binar cu eliberarea de memorie necesită utilizarea doar a unei "ordine inversă" cu crawlere.
Luați în considerare mijloacele prin care puteți oferi opțiuni pentru traversarea arborelui.
Când lucrați cu un copac binar din punct de vedere al programării, cel mai bun mod de a construi un program este să folosiți recursul. Varianta de bază a procedurii recursive pentru traversarea unui copac binar este foarte simplă.
Pentru studiul practic al mecanismului de recursiune atunci când se implementează opțiuni de traversare a unui arbore, se poate folosi arborele deja construit din Fig.
Un exemplu de folosire a unei proceduri recursive pentru rezolvarea problemei numărării frunzelor binare de copaci.
În concluzie, trebuie remarcat faptul că traversarea recursivă a unui copac este aplicabilă în majoritatea problemelor, dar este totuși necesar să se facă distincția între aplicațiile eficiente ale căutării binare și căutării continue.
Articole similare
Trimiteți-le prietenilor: