Diferența dintre arborele binar complet și arborele binar complet

Arbore binar complet vs arbore binar complet

Arborele binar este un arbore în care fiecare nod are unul sau doi copii. Într-un copac binar, un nod nu poate avea mai mult de doi copii. Într-un copac binar, copiii sunt numiți copii "stângi" și "drepți". Nodurile copil conțin o referință la părintele lor. Un arbore binar complet este un arbore binar în care fiecare nivel al copacului binar este complet umplut cu excepția ultimului nivel. În nivelul neîncărcat, nodurile sunt atașate pornind de la poziția cea mai stângă. Un copac binar complet este un copac în care fiecare nod din copac are doi copii, cu excepția frunzelor copacului.

Ce este copacul 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 descrie un copac binar complet. Într-un arbore binar complet, numărul de noduri (n), numărul de lave (l) și numărul de noduri interne (i) este legat într-un mod special astfel încât, dacă știți unul dintre ele, puteți determina celelalte două valori după cum urmează:

1. Dacă un copac binar complet are noduri interne:

- Numărul 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 nodurilor interne i = (n-1) / 2

- Numărul de frunze l = (n + 1) / 2

3. Dacă un copac binar plin are frunze:

- Numărul total de noduri n = 2 * l-1

- Numărul de noduri interne i = l-1

Ce este copac binar complet?

După cum se arată în figura 2, un arbore binar complet este un arbore binar în care fiecare nivel al copacului este umplut complet, cu excepția ultimului nivel. De asemenea, în ultimul nivel, nodurile trebuie atașate pornind de la poziția cea mai stângă. Un arbore binar complet de înălțime h îndeplinește următoarele condiții:

- Din nodul rădăcină, nivelul deasupra ultimului nivel reprezintă un arbore binar complet cu î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 în nivelul deasupra ultimului nivel, atunci a are mai mulți copii decât b dacă și numai dacă a este situat în stânga lui b

Care este diferența dintre arborele binar complet și arborele binar complet?

Copacii binari compleți și copacii binari compleți au o diferență clară. În timp ce un arbore binar complet este un arbore binar în care fiecare nod are zero sau doi copii, un arbore binar complet este un arbore binar în care fiecare nivel al copacului binar este complet umplut, cu excepția ultimului nivel. Unele structuri de date speciale cum ar fi grămezi trebuie să fie arbori binari compleți, în timp ce nu trebuie să fie arbori binari compleți. Într-un copac binar complet, dacă cunoașteți numărul de noduri totale sau numărul de lave sau numărul de noduri interne, puteți găsi celelalte două foarte ușor. Dar un copac binar complet nu are o proprietate specială legată de aceste trei atribute.