Într-un arbore binar care conține N noduri, există exact un singur link pe nod, cu excepția rădăcină. Numărul total de obligațiuni este de 2 * N; non-gol - N-1. prin urmare, conexiunea N + 1 este goală. Liniile goale există numai pentru a indica că nu există o cale mai departe în această direcție, pentru care este suficient un bit. Se pune întrebarea: nu este posibil să se utilizeze mai rațional spațiul ocupat de conexiunile goale. Arborii copți folosesc un spațiu ocupat de legături goale pentru a stoca pointeri care simplifică trecerea copacului. Aceste conexiuni suplimentare sunt numite fire. de unde a apărut termenul de cusătură. Introducem notația:
- * P - predecesorul nodului P în ordine inversă,
- P * este urmașul nodului P în ordine inversă,
- + P este un precursor în ordinea directă,
- P + este un urmaș în ordinea directă.
Arborele poate fi cusut pentru a traversa într-o singură ordine. Comparați copacul obișnuit și arborele, cusute pentru o ocolire în ordine inversă. În loc de legăturile stânga goale, stocăm indicatorul la predecesorul său în ordine inversă, în loc de link-uri drepte, un pointer către următorul. Aceste legături vor fi numite "fire" în contrast cu legăturile principale, care sunt aceleași ca în arborele obișnuit. Pentru a distinge legăturile de bază de fire, la fiecare nod vom configura două câmpuri L și R. care vor avea valorile THREAD. dacă conexiunea este un fir și MAINLINK. dacă conexiunea este principala (constantele THREAD și MAINLINK). Astfel, structura nodului copacului cusut arată astfel:
Figura 25 prezintă un copac tăiat. Linia punctată arată firele.
Fig.25. Lemn tăiat
Avantajul arborilor cusuta este ca algoritmii de bypass sunt simplificati. Mai jos este o funcție care readuce un pointer la următorul p în ordine inversă.
dacă (p-> R == THREAD) returnați q; // dacă este un fir, atunci rezultatul q
În caz contrar, mergeți până la oprirea legăturilor din stânga
În prezența algoritmului pentru determinarea urmăritorului, nu este nevoie de o stivă (explicită sau generată de mecanismul de implementare a recursului). Funcția care efectuează traversarea arborelui în ordine inversă are forma:
void InverseBypass (NODE * Root)
// găsiți primul nod în ordine inversă
// se află la sfârșitul coborârii de-a lungul legăturilor stângi principale
// treceți prin toate nodurile utilizând funcția NextUzel
Articole similare
Trimiteți-le prietenilor: