structuri de date dinamice, arbori de căutare binare

lemn # 151; un set de elemente, numite noduri (în acest caz, unul dintre ele este definit ca rădăcină) și relațiile (părinte-copil) noduri care formează o structură ierarhică. Nodurile pot fi valorile de orice tip simplu sau structurat, cu excepția fișierului. Nodurile care nu au nici un nod ulterior, numit frunze.

Într-un arbore binar (binar), fiecare nod poate fi conectat prin nici un alt mai mult de două noduri. Recursiv arbore binar este definit după cum urmează: un arbore binar este fie gol (nu conține un singur nod), sau conține un nod numit rădăcină. precum și două independente subramificație - subarborele stâng și subarborelui drept.

Binar copac de căutare poate fi gol sau are proprietatea că elementul rădăcină este mai important sit decât orice element din subarborele stâng, și mai mică sau egală decât elementele din subarborele din dreapta. proprietate a spus este numit o proprietate caracteristică a unui arbore binar de căutare și este valabil pentru orice nod al arborelui, inclusiv rădăcina. În cele ce urmează considerăm doar arbori de căutare binare. Acest nume binar arbori de căutare obținute pentru motivul că viteza de căutare pentru ei este aproximativ aceeași ca și în matrice sortat: O (n) = C • log2 (în cel mai rău caz O (n) = n).

Exemplu. Pentru un set de date 9, 44, 0, -7, 10, 6, -12, 45 pentru a construi un arbore binar de căutare.

Prin definiție, numărul 9 de căutare arbore binar pus la rădăcina tuturor valorilor lui mai mică - pe subarborele stâng, mai mare sau egală - la dreapta. Fiecare element următor subramificație poate fi privit ca rădăcină și acționează pe același algoritm. Ca rezultat, vom obține

Alegem operații tipice pe arbori de căutare binare:

adăugarea unui element din arbore;
îndepărtarea unui element din arbore;
Traversarea arbore (elemente de imprimare, etc.);
Caută în copac.

Având în vedere că definiția unui arbore binar recursiv, toate aceste operații standard pot fi implementate ca subrutine recursive (în practică, această variantă este cel mai des folosit). Remarcăm doar că utilizarea recursivitatii încetini programul și consumă în exces de memorie atunci când este executat.

Fie un arbore binar de căutare este descris de tipul

Vom arăta două variante de a adăuga un element la un copac: iterativ si recursiv.

In mod similar, in C ++.

Există mai multe modalități de a lucra în jurul valorii (trecerea) a tuturor nodurilor de copac. Trei dintre cele mai frecvent utilizate dintre acestea sunt numite eludării trăi (prefix) ordine. ocolind revers (postfix) modalitatea și ocolind ordinea internă (sau mersul echilibrat). Fiecare dintre ocoluri este implementat folosind recursivitate.

Mai jos sunt elementele subrutina de imprimare ale arborelui folosind parcurgeri binar arbore de căutare în ordine inversă.

Punerea în aplicare a unei funcții care returnează true (1) în cazul în care un element este prezent în copac, și fals (0) - în caz contrar.

Comparativ cu sarcina anterioară pentru a șterge un nod este pus în aplicare un pic mai complicat de un copac. Putem distinge două cazuri de a elimina un element x (cazul nici un element din arborele este degenerată)

1) cuprinzând un element de asamblare x. El are un grad de cel mult 1 (grad nod - numărul de subarbori care provin din acel nod);

2) care cuprinde un element de asamblare x. 2 deține.

Cazul 1 este ușor. nodul anterior este conectat sau îndepărtat cu un singur subarbore al nodului (dacă nodul este îndepărtat gradul 1), sau nu ar avea subramificație în întregime (în cazul în care nodul este 0 grade).

Mult mai dificilă în cazul în care nodul eliminat are doi subarbori. În acest caz, este necesar să se înlocuiască elementul detașabil elementul de subarborele din dreapta sa stângă.

Notă. Dacă un element se repetă în arborele de mai multe ori, înlăturat numai prima apariție a acesteia.

Elaborarea procedurilor de creare a unui arbore binar de căutare care conține n elemente.

întrebări de control și sarcini

Ce este un algoritm recursiv?
Care sunt părțile construite definirea unui algoritm recursiv?
Ce este o necesitate în orice algoritm recursiv?
Pot să înlocuiesc recursivitate iterație? Este posibil să se înlocuiască iterație recursivitate?
Care este principiul structurii dinamice a „copac“?
Lista asemănările și diferențele de structuri dinamice, cum ar fi „lista liniara“, „stivă“, „copac“.
Lista structurilor care pot fi reprezentate ca un copac, care apar în viața de zi cu zi.
Finish teză: „Lista liniara - un copac care ...“.
Punerea în aplicare a versiunilor iterative ale algoritmilor de prelucrare a lemnului, care sunt prezentate într-o formă recursivă.
Scrieți o procedură recursiv, care imprimă elementele toate frunzele copacului.
Scrieți o funcție recursivă care determină adâncimea elementului specificat în copac și returnează -1 dacă nu există un astfel de element.
Scrieți o rutină care se imprimă (o dată), toate în partea de sus a arborelui.
Scrieți o procedură care, având în vedere n contorizează numărul tuturor nodurilor de adâncime n din arborele specificat.
Scrieți o procedură care determină adâncimea de copac.

Site-ul creat în sistemul uCoz