Arbore - o structură de date care reprezintă un set de elemente și relații care alcătuiesc o structură ierarhică a acestor elemente.
Fiecare element din arborele se numește un nod (nod) al arborelui.
Partea de sus a arborelui sunt conectate prin arce dirijate, care sunt numite ramurile unui copac.
Nodul inițial al arborelui se numește rădăcina arborelui, aceasta corespunde nivelului zero.
Frunzele pomului sunt numite vârfuri, care includ o ramură și nu lasă o singură ramură.
Fiecare copac are următoarele proprietăți:
• există un nod care nu face parte din orice arc (rădăcină);
• În fiecare nod, cu excepția rădăcină, conține un arc.
Copacii utilizate cel mai des în practică în reprezentarea diferitelor ierarhii.
Descendenții - toate topuri, care includ ramuri care provin dintr-un nod comun.
Strămoș - un vârf, din care emană o ramură la următorul nivel de topuri.
progenituri de nivel pe unitate depășește nivelul de mamă.
Rădăcina arborelui nu are nici o mamă, iar frunzele pomului nu sunt descendenți.
Înălțimea (adâncimea) a arborelui este determinată de numărul de straturi, care sunt dispuse pe partea superioară. Înălțimea arborelui gol înfășurat înălțimea zero a arborelui din aceeași rădăcină - unitate. La primul nivel al arborelui poate fi doar un singur nod - rădăcină de copac, al doilea - descendenții rădăcina copacului, al treilea - descendenții rădăcina arborelui de urmași, etc.
Subramificație - parte dintr-o structură de date arborescentă, care pot fi prezentate într-un lemn separat.
Gradul unui nod într-un arbore este numărul de arce, care vine.
Gradul de copac este egal cu gradul maxim, o parte din copac. Atunci când acest lucru lasă în copac sunt nodurile care au un grad zero.
copac comandat - un copac ale cărui ramuri care provin de la fiecare nod, ordonate după anumite criterii.
Copacii sunt structuri recursive, precum și fiecare subramificație este un copac. Astfel, arborele poate fi definit ca o structură recursivă, în care fiecare element este:
• o structură goală;
• orice element, care este asociat cu un număr finit de subarbori.
Acțiuni cu structuri recursive este descrisă cel mai convenabil folosind algoritmi recursive.
Traversal de copac - este o secvență ordonată de noduri ale arborelui în care fiecare nod exact o dată.
Atunci când traversează toate nodurile arborelui trebuie să fie vizitate în ordine. Există mai multe modalități de a lucra în jurul valorii de toate nodurile arborelui.
• endian - primul vizitat n rădăcină a T copac, atunci toate nodurile subarborelui T1, atunci toate nodurile T2 subramificație, etc. TK;
• simetrice - au vizitat mai întâi toate nodurile subarborelui T1, atunci rădăcina n, toate nodurile suplimentare T2 subarborele, etc. TK;
• întoarcere - inițial, toate nodurile vizitate subramificație T1, atunci toate nodurile T2 subramificație, etc. Mk, ultima vizită rădăcină de n.
Prezentarea de copaci folosind matrice
Binare Arbori de căutare, operații de adăugarea de elemente.
copaci binar de căutare (binar de căutare copac. BST)
Într-un arbore binar de căutare, fiecare nod poate avea (sau nu au), la stânga și la dreapta a copilului, fiecare nod cu excepția rădăcinii are un părinte. La depunerea folosind indicii stocăm pentru fiecare nod al arborelui, în plus față de valorile-cheie ale indicatorilor cheie ca stânga, dreapta și p (subarbori la stânga, dreapta și părinte). În cazul în care copilul (sau părinte - la rădăcină) nu are nici un câmp corespunzător conține NULL.
Cheile într-un arbore binar de căutare sunt stocate în conformitate cu proprietățile de ordine.
Fie x un nod arbitrar al unui arbore binar de căutare. În cazul în care nodul este în partea de sus în subarborele din stânga a lui x, apoi tasta [y]
Nod (T w): inf (w), la stânga (0), dreapta (0) <>
Nod * _Add (Nod * r, T s)
else if (s
r-> = _Add la stânga (r-> stânga, s);
r-> dreapta = _Add (r-> dreapta, s);