Copaci binari
Obiectiv: Să studieze modalitățile de stocare și prelucrare eficientă a informațiilor despre exemplul copacilor binari.
Informații generale
Un arbore binar este o structură de date dinamică ierarhică, constând din noduri și arce de conectare. Fiecare nod, cu excepția unuia, are exact un singur arc. Acest nod unic se numește rădăcina copacului. Un număr finit de copaci individuali, numiți substraturi, sunt asociate cu fiecare vârf al copacului. Figura prezintă un arbore ale cărui noduri sunt simbolurile: nodurile Y situate direct sub sus X, numit directe copil X, X și vârful este numit un strămoș al Y. Dacă nodul nu are descendenți, se numește o frunză, dacă are, atunci numit vârful interior . De exemplu, vârfurile D, E sunt descendenții direcți ai vârfului B; nodurile lui H, I, J sunt frunze. Evident, un arbore este necesar pentru referințe. Vom descrie un arbore binar ca structura de înregistrare de tip care cuprinde cel puțin două câmpuri - indicii la stânga și subarborele dreapta, și un câmp de date, cum ar fi tipul Integer: Operații de bază pe copac la operațiunile de bază peste copaci includ: • element de intrare în copac; • traversarea arborelui; • eliminarea unui element din arbore.
Introduceți un element într-un copac. Creați și afișați un arbore ale cărui elemente sunt introduse de la tastatură și au un tip întreg. În plus, pentru fiecare vârf al copacului în toate vârfurile stânga trebuie să existe numere mai mici și în dreapta sunt mai mari decât numerele stocate în acest vârf. Un astfel de copac este numit arbore de căutare. Să descriem procedura de introducere a unui nou vârf în arbore. Atunci când este inserat într-un copac, vârful este introdus fie sub forma unui vârf deja existent, fie ca singurul vârf al copacului. Prin urmare, ambele legături stânga și dreapta ale noului vârf trebuie să fie egale cu zero. Când arborele este gol, valoarea referinței trecută ca parametru este zero. În acest caz, trebuie să îl schimbați astfel încât să indice un nou vertex care a fost introdus ca root. Când introduceți al doilea element transmis de principala opțiune de program Anodul nu va mai fi egală cu zero, și este necesar să se decidă dacă, într-un subarbore este necesar să se introducă un nou vârf. Ieșirea elementelor de copac. Să descriem procedura de afișare a valorilor elementelor binare ale copacilor pe ecran. Pentru a face acest lucru, trebuie să finalizați o traversare completă a copacilor. Când un copac este traversat, vârfurile sale individuale sunt vizitate într-o anumită ordine. Ieșirea unui arbore binar poate fi făcută recursiv, efectuând trei acțiuni pentru fiecare vârf: • ieșirea numărului stocat în nod; • traversarea sub-alfismului din stânga; • traversarea substratului drept. Ordinea în care sunt executate acești pași determină modul în care arborele este traversat. Modalități de ocolire: • Bypass direct (de sus în jos); • bypass simetric (de la stânga la dreapta); • bypass invers (de sus în jos). Procedura pentru ieșirea simetrică a unui copac este după cum urmează: Eliminarea dintr-un copac. Îndepărtarea imediată a unui element dintr-un arbore ordonat este pus în aplicare, pur și simplu, în cazul în care acest nod este final: fie că provine dintr-o singură margine: Trebuie să schimbați link-ul din vârfurile anterioare. Dacă îndepărtat din partea de sus frunze două ramuri, trebuie să găsiți în partea de sus dreapta a arborelui, care ar putea fi introdus în loc un top detașabil. În acest caz, elementul care trebuie șters trebuie înlocuit fie cu elementul din dreapta al sub-alfismului său stâng, fie cu elementul din partea stângă a sub-alfatului său drept. Astfel de elemente nu pot avea mai mult de un copil. Se va da următoarea structură: Procedura auxiliară Del este chemată numai în cel de-al treilea caz. Ea „jos“ de-a lungul ramurii din dreapta a subarborele stâng al nodului q îndepărtat ^ și apoi se înlocuiește datele (câmp de date) în valorile corespunzătoare ale q ^ din dreapta nodului R ^ subarborelui stâng, și apoi de la R ^ pot scăpa. Figura arată arborele inițial (a), din care nodurile cu valori de 13, 15, 5, 10 sunt șterse succesiv. Arborii care rezultă sunt arătați în Fig. b - e.
Întrebări de test
1. Ce este un algoritm recursiv? 2. Din ce părți este construită definiția unui algoritm recursiv? 3. Ce este obligatoriu în orice algoritm recursiv? 4. Este posibil să înlocuiți recursiunea cu iterație? Este posibil să înlocuiți iterația cu recursivitate? 5. Care este principiul construirii structurii dinamice "copac"? 6. Listați asemănările și diferențele dintre structurile dinamice, cum ar fi "lista liniară", "stiva", "copac". 7. Listați structurile care pot fi reprezentate sub forma unui copac care se găsesc în viața de zi cu zi. 8. Finalizați fraza: "Lista este un copac în care ...".
În toate problemele, arborele binar de căutare are înțeles. Scrieți o funcție numerică recursivă care numără suma elementelor de copac. 2. Scrieți o funcție care găsește cel mai mare element al copacului. 3. Scrie o funcție care găsește cel mai mic element al arborelui. 4. Scrieți o procedură care elimină toate elementele din copac. 5. Scrieți o procedură recursivă care determină numărul de apariții ale elementului dat în arbore. 6. Scrieți o procedură recursivă care imprimă elemente din toate frunzele copacului. 7. Scrieți o procedură care afișează un copac, arătând adâncimea nodurilor cu linia din marginea din stânga a ecranului. De exemplu, arborele va fi afișat după cum urmează: 1 grup 1 curs 2 grup de PMI 3 grup 2 curs 4 grup 8. Scrieți o funcție recursivă care determină adâncimea elementului dat în arbore și returnează -1 dacă nu există un astfel de element. 9. Scrieți o procedură care imprimă (o dată) toate vârfurile arborelui. 10. Scrieți o procedură care, dată de o dată n, numără numărul tuturor vârfurilor de adâncime n din arborele dat. 11. Scrieți o procedură care ia în considerare adâncimea copacului. 12. Sortați o matrice A prin includerea elementelor sale în arbore și copiați datele sortate înapoi în A. 13. Se specifică o secvență de cuvinte. Determinați frecvența apariției fiecăruia dintre cuvinte în secvență. Notă. Pentru a rezolva problema, se caută orice cuvânt în arbore, care este gol în stadiul inițial. Dacă se găsește cuvântul, contorul aparițiilor acestuia crește cu unul, dacă nu, cuvântul este inclus în arbore, cu o singură valoare a contorului. Înapoi Acasă
Articole similare
Trimiteți-le prietenilor: