1.1. Definiția structura: lemn
Arborele - un set finit T. eventual gol, în caz contrar, constând din unul sau mai multe elemente (noduri sau noduri ale arborelui) astfel încât:
a) există un element special desemnat, numit rădăcina arborelui;
b) elementele rămase cuprinse în m> 0 disjuncte seturi T1. Tm. fiecare dintre care, la rândul său, este un copac; copaci T1. Tm sunt numite subramificații de rădăcină (fig.1.A).
Fig.1. tipuri de arbori
Dacă valoarea este ordinea relativă a subarbori T1. Tm, atunci spunem că arborele este comandat. Numărul de subarbori al nodului este numit gradul de nod. Nod de zero grade se numește nodul terminale (frunză sau nod sau terminal), toate celelalte elemente - nodurile interne (non-terminal). Gradul maxim de toate nodurile se numește gradul de copac. rădăcină copac are un nivel egal cu 0. restul vârfurilor au un nivel de o mai mare decât nivelul de strămoș direct. Nivelul maxim al oricăruia dintre vârfuri se numește adâncimea sau înălțimea copacului. Înălțimea minimă pentru un anumit număr de noduri este atins în cazul în care, la toate nivelurile, cu excepția ultimului, a pus numărul maxim posibil de noduri. Numărul maxim de noduri din înălțimea arborelui h se realizează în cazul fiecărui nod, cu excepția nivelului h, se procedează d subramificații, unde d este gradul arborelui: pe un 0-lea nivel 1 vertex la 1 - descendenți d 2 lea - d 2 descendenții la nivelul 3 d 3 copii, etc.
arbori binari (binare) (ris.1.b) sunt cele mai des utilizate. Un arbore binar este un set finit de elemente, care este fie gol sau constă dintr-o rădăcină și a doi arbori binari care nu se suprapun, numite subramificații din stânga și dreapta ale rădăcinii. Astfel, fiecare element al arborelui binar este 0, 1 sau 2 subramificație. arbore binar - comandat copac, deoarece distinge subramificații stânga și dreapta.
Definiția structura arborescentă dat mai sus este recursiv și reflectă natura recursiv a structurii în sine.
Structura de date - arborele poate fi reprezentat ca în memorie statică și dinamică.
În matrice SRAM poate fi reprezentat printr-un arbore, pentru care a definit conceptul unui element gol:
Fig.2. arbore binar reprezentat ca o matrice
Nodurile sunt aranjate într-o matrice arbore binar după cum urmează (a se vedea figura 2 ..): Dacă k - nod index copac, descendenții săi sunt în elementele de matrice cu indicii 1 și 2k + 2 (k + 1); rădăcina arborelui este elementul cu indexul 0 (când indexarea matrice de la 1 la N codurile descendenților k-th vertex: 2k și 2k + 1, indicele de rădăcină este 1).
Memoria dinamică a arborelui reprezintă o listă ierarhică. Set element poate fi o listă arbore binar ca element cu trei câmpuri: două câmpuri de referință conținând indicii pentru sale stânga (L) și dreapta subramificații (R), și un câmp de informații (E):
Determinarea tipului de element de arbore binar dinamic:
btree * stânga, dreapta *;>
Aici tip - Tip câmp de informații (în cazul în care câmpul de informații are o structură complicată, tipul poate fi de tip - pointer la obiectul care conține valoarea arborelui elementului).
Pentru a determina copac ca o singură structură ar trebui să fie stabilite pe rădăcina arborelui indicatorul:
Figura 3. Arborele binar dinamic
Figura 3 prezintă un arbore dinamic d binar în conformitate cu tipul de element particular, a făcut mai sus. elemente din lemn, cu un grad de 0 și 1 sunt una sau două domeniu de referință, cu o valoare a unui pointer gol (NULL).
Tratarea lemnului, este necesar pentru a vizualiza elementele sale - aceasta se numește parcurgeri de copac (sau trecerea de copac).