Arborele binar complet vs Arborele binar complet
Arborele binar este un arbore î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 arbore binar, copiii sunt numiți drept copii „stânga” și „dreapta”. Nodurile copil conțin o referință la părintele lor. Un arbore binar complet este un arbore binar în care fiecare nivel al arborelui binar este complet complet, cu excepția ultimului nivel. La nivelul neumplut, nodurile sunt atașate începând din poziția cea mai din stânga. Un arbore binar complet este un arbore în care fiecare nod din arbore 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 arbore 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 arbore binar complet. Într-un arbore binar complet, numărul de noduri (n), numărul de lave (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 celel alte două valorile după cum urmează:
1. Dacă un arbore binar complet are i noduri interne:
– Numărul de frunze l=i+1
– Numărul total de noduri n=2i+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 arbore binar complet are l frunze:
– Numărul total de noduri n=2l-1
– Numărul de noduri interne i=l-1
Ce este arborele binar complet?
După cum se arată în figura 2, un arbore binar complet este un arbore binar în care fiecare nivel al arborelui este complet umplut, cu excepția ultimului nivel. De asemenea, în ultimul nivel, nodurile ar trebui atașate începând din poziția cea mai din stânga. Un arbore binar complet cu înălțimea h îndeplinește următoarele condiții:
– Din nodul rădăcină, nivelul de 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 de 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?
Arborii binari completi și arborii binari completi 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 arborelui binar este complet umplut, cu excepția ultimului nivel. Unele structuri speciale de date, cum ar fi grămezile, trebuie să fie arbori binari completi, în timp ce nu trebuie să fie arbori binari completi. Într-un arbore binar complet, dacă cunoașteți numărul total de noduri sau numărul de lave sau numărul de noduri interne, le puteți găsi pe celel alte două foarte ușor. Dar un arbore binar complet nu are o proprietate specială care să raporteze aceste trei atribute.
