Arborele binar complet vs Arborele binar complet
Arborele binar este un copac în care fiecare nod are unul sau doi copii. Într-un arbore binar, un nod nu poate avea mai mult de doi copii. Într-un copac binar, copiii sunt numiți copii „stânga” și „dreapta”. Nodurile copil conțin o referință la părintele lor. Un copac binar complet este un copac binar în care fiecare nivel al arborelui binar este complet umplut, cu excepția ultimului nivel. La nivelul neumplut, nodurile sunt atașate începând din cea mai stângă poziție. Un copac binar complet este un copac în care fiecare nod din copac are doi copii, cu excepția frunzelor copacului.
Ce este arborele binar complet?
Arborele binar complet este un arbore binar în care fiecare nod din copac are exact zero sau doi copii. Cu alte cuvinte, fiecare nod din copac, cu excepția frunzelor, are exact doi copii. Figura 1 de mai jos prezintă un copac binar complet. Într-un arbore binar complet, numărul de noduri (n), numărul de spălături (l) și numărul de noduri interne (i) sunt legate într-un mod special, astfel încât, dacă cunoașteți unul dintre ele, puteți determina celelalte două valorile după cum urmează:
1. Dacă un arbore binar complet are i noduri interne:
- Număr de frunze l = i + 1
- Numărul total de noduri n = 2 * i + 1
2. Dacă un arbore binar complet are n noduri:
- Numărul de noduri interne i = (n-1) / 2
- Numărul de frunze l = (n + 1) / 2
3. Dacă un copac binar complet are l frunze:
- Numărul total de noduri n = 2 * l-1
- Numărul de noduri interne i = l-1
Ce este arborele binar complet?
Așa cum se arată în figura 2, un copac binar complet este un copac binar în care fiecare nivel al copacului este complet umplut, cu excepția ultimului nivel. De asemenea, în ultimul nivel, nodurile ar trebui să fie atașate începând din cea mai stângă poziție. Un arbore binar complet de înălțime h îndeplinește următoarele condiții:
- Din nodul rădăcină, nivelul de deasupra ultimului nivel reprezintă un arbore binar complet de înălțimea h-1
- Unul sau mai multe noduri din ultimul nivel pot avea 0 sau 1 copii
- Dacă a, b sunt două noduri la nivelul peste ultimul nivel, atunci a are mai mulți copii decât b dacă și numai dacă a este situat la stânga lui b
Care este diferența dintre Arborele binar complet și Arborele binar complet?
Arborii binari complet și arborii binari complet au o diferență clară. În timp ce un copac binar complet este un copac binar în care fiecare nod are zero sau doi copii, un copac binar complet este un copac binar în care fiecare nivel al copacului binar este complet umplut, cu excepția ultimului nivel. Unele structuri speciale de date, cum ar fi grămezile, trebuie să fie arbori binari complet, în timp ce nu trebuie să fie arbori binari complet. Într-un arbore binar complet, dacă cunoașteți numărul total de noduri sau numărul de spălături sau numărul de noduri interne, puteți găsi celelalte două foarte ușor. Însă un copac binar complet nu are o proprietate specială referitoare la aceste trei atribute.
