// Dacă da, creșteți variabila de numărare
dacă (t-> Stânga () == NULL t-> dreapta () == NULL)
Funcția de adâncime folosește metoda de trecere inversă pentru a calcula adâncimea unui copac binar. În fiecare nod, se calculează adâncimea substraturilor stânga și dreapta. Adâncimea totală pe unitate este mai mare decât adâncimea maximă a substraturilor.
// Această funcție folosește metoda inversă de trecere
// pentru a calcula adâncimea substraturilor stânga și dreapta
// nod și returnează valoarea de adâncime rezultată,
// egal cu 1 + max (depthLeft, depthRight).
// Adâncimea copacului gol este -1
șablon
spațiu gol (TreeNode
int adâncime, adâncimeRight, depthval;
depthval = 1 + (depthLeft> adâncimeAlte adâncimeAlte adâncimeRight);
b = GetTreeNode ("B", NULL, d);
c = GetTreeNode ('C', e, NULL);
a = GetTreeNode ('A', b, c);
Mai întâi creează un fiu D, care apoi se alătură părintelui B atunci când creează nodul. Se creează un nod E care se alătură familiei sale C la momentul nașterii (sau creării) celui din urmă. În cele din urmă, se creează o rădăcină și se unește cu fiii ei B și C.
Algoritmul copierii copacilor începe să lucreze din rădăcină și construiește mai întâi subdrivea stângă a nodului, iar apoi - subdrija sa dreaptă. Abia după aceea se creează un nou nod. Același proces recursiv se repetă pentru fiecare nod. În consecință, nodul t al arborelui sursă creează un nod nou cu indicele newlptr și newrptr.
Cu metoda inversă de trecere, fiii sunt vizitați în fața părinților lor. Drept rezultat, în arborele nou, sunt create substrele corespunzătoare t-> stânga () și t-> dreapta (). Fiii se alătură părinților lor în momentul creării acestora din urmă.
// creați un părinte și îi atacați pe fiii lui
newnode = GetTreeNode (t-> date, newlptr, newrptr);
Esența nodului de vizitare t din arborele sursă este crearea unui nod nou în arborele duplicat.
TreeNode
MakeCharTree (root1, 0); // root1 indică Tree_0
Treceți descendenții nodului A, începând cu subordonul din stânga (nodul B și apoi la nodul D, care este subdriga dreaptă a nodului B). Creați un nou nod cu date egale cu D, indicatorii stânga și dreapta egali cu NULL.
Fiii nodului B sunt trecuți. Creați un nou nod cu date egale cu B, un indicator de stânga egal cu NULL și un indicator corect îndreptat spre o copie a nodului D.
Odată cu trecerea subdomeniului stâng al nodului A, începeți să treceți subtreea sa dreaptă și ajungeți la nodul E. Creați un nod nou cu date din nodul E și câmpurile pointerului egal cu NULL.
După procesarea E, mergeți la părintele său și creați un nou nod cu datele din C. În câmpul cu pointerul drept, puneți NULL și atribuiți pointerul stâng copiei nodului copil E.
// Creați un arbore duplicat t și returnați rădăcina arborelui nou
șablon
// Variabila newnode indică noul nod care este creat
// apelând GetTreeNode și atașat
// în viitorul copac nou.
// nod și trecute ca parametri pentru GetTreeNode
TreeNode
// Opriți trecerea recursivă atunci când ajunge
// nodurile copacului t. în fiecare nod al acestei funcții de arbore
// copia sa este creată. În caz contrar, se întoarce
// și atârnă copiile fiilor săi.
dacă (t-> stânga ()! = NULL)
dacă (t-> dreapta ()! = NULL)
// construi un nou copac de jos în sus, creând mai întâi
// doi fii, apoi părinții lor
newnode = GetTreeNode (t-> date, newlptr, newrptr);
// returnați pointerul la arborele nou creat
Atunci când o aplicație utilizează o structură dinamică, cum ar fi un copac, responsabilitatea pentru eliberarea memoriei este suportată de programator. Vom dezvolta funcția DeleteTree, care utilizează metoda inversă de trecere a unui arbore binar. Folosind metoda inversă a trecerii, asigurăm că vom vizita toți fiii nodului părinte înainte de al șterge. Operația de vizitare constă în apelarea funcției FreeTreeNode, care elimină nodul.
// Folosiți algoritmul invers pentru a traversa nodurile copacilor
// și șterge fiecare nod la vizita
șablon
void DeleteTree (TreeNode
De asemenea, dezvoltăm funcția ClearTree, care șterge toate nodurile copacului și resetează rădăcina. Funcția apelează DeleteTree pentru a șterge nodurile arborelui și alocă pointerul la valoarea rădăcină NULL.
/ / Apelați funcția DeleteTree pentru a șterge nodurile copacilor.
// Apoi resetați pointerul la rădăcina lui în NULL
șablon
void ClearTree (TreeNode
t = NULL; // acum rădăcina este goală
Arbori binari de căutare
Un arbore binar tipic poate conține o colecție vastă de date și oferă totuși o căutare rapidă, adăugarea sau eliminarea elementelor. Una dintre cele mai importante aplicații ale copacilor este construcția de clase de colecții. Pentru structurile liniare, complexitatea algoritmului care implementează căutarea secvențială este O (N), care este ineficientă pentru colecțiile mari. În general, structurile copacilor oferă o productivitate semnificativ mai mare, deoarece calea către orice date nu depășește adâncimea copacului. Eficiența căutării este maximă cu arborele binar finit și este O (log2 N). De exemplu, în lista de 10.000 de articole, numărul estimat de comparații pentru căutarea secvențială este 5000. O căutare pe arborele terminat nu va necesita mai mult de 14 comparații. Arborele binar prezintă un mare potențial ca structură de stocare a listei.
Pentru a ne aminti elementele sub forma unui copac pentru accesul efectiv, trebuie să dezvoltăm o structură de căutare care să indice calea spre element. Această structură, numită arbore binar de căutare, aranjează elementele prin intermediul "<". Чтобы сравнить узлы дерева, мы подразумеваем, что часть или все поле данных определено в качестве ключа и оператор "<" сравнивает ключи, когда добавляет элемент. Бинарное дерево поиска строится по следующему правилу:
Pentru fiecare nod, valorile datelor din subordonul din stânga sunt mai mici decât în acest nod, iar în subordonul drept - mai mult sau egal.
Fig. 10. Arborele de căutare binar
În Fig. Figura 10 prezintă un exemplu de arbore binar de căutare. Acest arbore este numit arbore de căutare deoarece, în căutarea unui element (cheie), putem merge doar pe o cale foarte specifică. Pornind de la rădăcină, vom scana subarga stânga dacă valoarea cheii este mai mică decât nodul curent. În caz contrar, substratul drept este scanat. Această metodă de creare a unui arbore vă permite să căutați un element pe calea cea mai scurtă din rădăcină. De exemplu, căutarea pentru numărul 37 necesită patru comparații, începând cu rădăcina.
Fig. 11. Exemple de arbori binari de căutare
În Fig. 11 noduri conțin o singură valoare întregă, care este cheia. În acest caz, nodul 25 are tasta 25, iar noi comparăm două noduri prin compararea numerelor întregi. Comparația este efectuată folosind integerul "<" и "==". Для студента университета ключом является ssn, и мы сравниваем две символьные строки. Это делается с помощью перегрузки операций. Например, следующий код реализует отношение "<" для двух объектов Student:
int operator <(const Student& s, const Student& t)
returnați s.ssn În aplicațiile noastre, oferim câteva exemple de chei / date. În ilustrații, folosim un format simplu, în care cheia și datele sunt aceleași. Lucrul cu arborele binar de căutare Un arbore binar de căutare este o structură neliniară pentru stocarea unui set de elemente. Ca orice structură de listă, arborele trebuie să permită inserarea, ștergerea și extragerea elementelor. Pentru arborele de căutare, este necesară o operație de inserare care introduce corect elementul nou. Luați în considerare, de exemplu, introducerea nodului 8 în arborele BinSTree_1. Pornind de la nodul rădăcină 25, determinăm că nodul 8 trebuie să fie în subordonatul stâng al nodului 25 (8<25). В узле 10 определяем, что место узла 8 должно быть в левом поддереве узла 10, которое в данный момент пусто. Узел 8 вставляется в дерево в качестве левого сына узла 10.
Există o cale specifică pentru fiecare nod introdus în arbore. Aceeași cale poate fi folosită pentru a găsi elementul. Algoritmul de căutare ia cheia și caută-l în subarborele stânga sau la dreapta fiecărui membru constituie calea. De exemplu, elementul de căutare 30 pe BinSTree_1 arbore (fig. 10), începe la nodul rădăcină 25 și trece în subarborele drept (30> 25), apoi subarborele stâng. (30 <37). Поиск прекращается на третьем сравнении, когда ключ совпадает с числом 30, хранящемся в узле.
În lista legată, operația de ștergere deconectează nodul și conectează nodul precedent la nodul următor. Pe un arbore binar de căutare, această operație este mult mai complicată, deoarece un nod poate întrerupe ordonarea elementelor de copac. Luați în considerare sarcina de a șterge rădăcina (având valoarea 25) din BinSTree_1. Ca rezultat, există două subrețe disjuncte care necesită o nouă rădăcină.
La prima vedere, decizia de a alege fiul nodului 25 - spune, 37 - și înlocuirea părintelui său. Cu toate acestea, această soluție simplă nu reușește, deoarece unele noduri se află pe partea rădăcină a rădăcinii. Deoarece acest arbore este relativ mic, putem stabili că 15 sau 30 reprezintă un înlocuitor acceptabil pentru nodul rădăcină.
// Specificația clasei BinSTree
șablon
cout <<"Студент отсутствует в базе данных." < Folosind arbori binari de căutare Clasa BinSTree este o structură puternică de date care este utilizată pentru a gestiona liste dinamice. Înainte de a examina un exemplu de problemă practică a construcției de concordanță, să luăm în considerare câteva exemple mai simple. Prin concordanță se înțelege o listă alfabetică a tuturor cuvintelor din textul dat cu indicii în locurile aparițiilor lor. Luați în considerare o serie de programe simple în care se folosesc arbori de căutare. Crearea exemplelor de arbori de căutare. În secțiunea "Structura binară a copacilor", funcția MakeCharTree a fost utilizată pentru a crea o serie de copaci binari cu date de caractere. Să creăm o funcție similară MakeSearchTree, care construiește arbori binari de căutare cu date întregi, utilizând metoda Insert. Primul arbore SearchTree_0 este creat pe baza arr0 array. În acest exemplu, variabila T este de tip BinSTree. pentru (i = 0; i <6; i++) T.Insert (arr0 [i]); // Adăugați un element în arbore Alți doi copaci, SearchTree_1 și SearchTree_2, creați-l singur. Primul dintre ele ar trebui să fie un copac cu opt elemente, iar al doilea ar trebui să fie un copac cu zece numere aleatorii din intervalul 10-99 (Figura 12). Numărul de arbore creat trebuie să fie transmis funcției MakeSearchTree ca parametru. Ca un alt parametru, funcția ar trebui să primească un pointer la o variabilă de tip BinSTree.
Fig. 12. Copaci creați cu funcția MakeSearchTree
Metodă simetrică de trecere
Cu un pasaj simetric al unui arbore binar, mai întâi este vizitat subdrivul stâng al nodului, apoi nodul în sine și în final subordona dreapta. Atunci când această metodă de trecere este aplicată arborelui binar de căutare, nodurile sunt vizitate în ordine sortată. Acest fapt devine evident atunci când comparați nodurile din subrețelele nodului curent. Toate componentele subarborele stâng al nodului curent au valori mai mici decât nodul curent și toate nodurile subarborelui drept al nodului curent este mai mare sau egal cu nodul curent. Simetric care trece arbore binar se asigură că, pentru fiecare nod, pe care le vizitați pentru prima dată, unitățile mai mici sunt situate în subarborele stâng, și mari - pe dreapta. Ca urmare, nodurile sunt traversate în ordine ascendentă.
Un arbore binar de căutare poate avea noduri duplicate. În operația de inserare, continuăm să scanăm subordonul corect dacă elementul nostru nou se potrivește cu datele din nodul curent. Ca rezultat, nodurile duplicate apar în subordonul drept al nodului concurent.
De exemplu, arborele următor este generat din lista 50 70 25 90 30 55 25 15 25.
Multe aplicații nu permit duplicarea nodurilor, dar folosiți contorul instanței în câmpul de date. Acesta este principiul concordanței, când sunt urmărite numerele de linie în care se întâlnește un cuvânt. În loc de a plasa cuvântul pe arbore de mai multe ori, procesăm instanțe repetate de utilizare a acestui cuvânt prin punerea numerelor de linie în listă.
Implementarea clasei BinSTree
Elementele de date ale clasei BinSTree
Un arbore binar de căutare este definit de indicatorul rădăcină, care este utilizat în operațiile Insert, Find and Delete. Clasa BinSTree conține un element de date rădăcină care este un pointer rădăcină și are o valoare inițială de NULL. Accesul la rădăcină se face prin metoda GetRoot, care permite apelurile către funcțiile de trecere externă. Al doilea pointer, curent, definește un loc pentru actualizări în arbore. Funcția Găsire setează curentul la nodul corespunzător, iar acest indicator este utilizat de funcția Actualizare pentru a actualiza datele. Metodele Inserare și ștergere reseta curentul la un nou nod sau la un nod care înlocuiește nodul la distanță. Obiectul BinSTree este o listă a cărei dimensiune este întotdeauna modificată de funcțiile Insert și Delete. Numărul curent de elemente din listă este stocat în dimensiunea elementului de date închis.
// Se indică la rădăcină și la nodul curent
// Numărul de elemente de copac
Constructor, distrugator și operator de atribuire
șablon
BinSTree
// Nu puteți copia un copac în sine
dacă (acest == RHS)
// Goliți copacul curent.
// Copiați noul copac în obiectul curent
Articole similare
Trimiteți-le prietenilor: