Ce este un arbore binar complet?
Un arbore binar complet poate fi definit ca a arbore binar în care toate nodurile au 0 sau doi copii. Cu alte cuvinte, arborele binar complet poate fi definit ca un arbore binar în care toate nodurile au doi copii, cu excepția nodurilor frunze.
Arborele de mai jos este un arbore binar complet:
Arborele de mai sus este un arbore binar complet, deoarece toate nodurile, cu excepția nodurilor frunze, au doi copii.
Teorema completă a arborelui binar:
Considerați un arbore binar T ca fiind un arbore nevid atunci:
matrice java dinamică
- Fie I noduri interne într-un arbore și L să fie un nod frunză într-un arbore, atunci numărul de noduri frunze ar fi egal cu:
L = I + 1 - Dacă T are, I număr de noduri interne și N este numărul total de noduri, atunci numărul total de noduri ar fi egal cu:
N = 2I + 1 - Dacă T conține „N” numărul total de noduri și „I” este numărul de noduri interne, atunci numărul de noduri interne ar fi egal cu:
I = (N-1)/2 - Dacă „T” are „N” număr total de noduri, iar „L” este un număr de noduri frunză, atunci numărul de noduri frunză ar fi egal cu:
L = (N+1)/2 - Dacă „T” conține „L” număr de noduri frunze, atunci numărul total de noduri ar fi egal cu:
N = 2L - 1 - Dacă „T” are „L” număr de noduri frunză și „I” să fie un număr de noduri interne, atunci numărul de noduri interne ar fi egal cu:
I = L - 1
Ce este un arbore binar complet?
Se spune că un arbore binar este un arbore binar complet atunci când toate nivelurile sunt complet umplute, cu excepția ultimului nivel, care este umplut din stânga.
Arborele de mai jos este un arbore binar complet:
Arborele binar complet este similar cu arborele binar complet, cu excepția celor două diferențe care sunt prezentate mai jos:
- Umplerea nodului frunzei trebuie să înceapă din partea stângă.
- Nu este obligatoriu ca ultimul nod frunză să aibă fratele potrivit.
Să înțelegem punctele de mai sus printr-un exemplu:
parafrazați dacă prin rudyard kipling
Luați în considerare arborele de mai jos:
Arborele de mai sus este un arbore binar complet, dar nu un arbore binar complet, deoarece nodul 6 nu are fratele său drept.
Crearea arborelui binar complet
Să presupunem că avem o matrice de 6 elemente prezentate mai jos:
Matricea de mai sus conține 6 elemente, adică 1, 2, 3, 4, 5, 6. Următorii sunt pașii care trebuie utilizați pentru a crea un arbore binar complet:
Pasul 1: Mai întâi, vom selecta primul element al matricei, adică 1, și vom face un nod rădăcină al arborelui. Numărul de elemente disponibile în primul nivel este 1.
Pasul 2: Acum, vom selecta al doilea și al treilea element al matricei. Păstrați al doilea element și al treilea element al matricei ca fiul stâng și drept al nodului rădăcină, respectiv, prezentate mai jos:
După cum putem observa mai sus, numărul de elemente disponibile în al doilea nivel este 2.
Pasul 3: Acum, vom selecta următoarele două elemente din matrice, adică 4 și 5. Păstrați aceste două elemente în stânga și în dreapta nodului 2, prezentate mai jos:
șir împărțit c++
După cum putem observa mai sus, nodurile 4 și 5 sunt copilul stâng și, respectiv, drept al nodului 2.
Pasul 4: Acum, vom selecta ultimul element al matricei, adică 6, și îl vom păstra ca copil stâng al nodului 3, deoarece știm că într-un arbore binar complet, nodurile sunt umplute din partea stângă, prezentată mai jos:
După cum putem observa că al doilea nivel conține 3 elemente.
Să înțelegem diferențele dintre arborele binar complet și complet prin imagini.
- Arborele binar care este prezentat mai jos nu este nici un arbore binar complet, nici complet. Nu este un arbore binar complet deoarece nodul 3 are un singur copil. De asemenea, nu este un arbore binar complet, deoarece nodurile ar trebui să fie completate din partea stângă, dar nodul 3 are un copil drept și nu are un copil stâng.
- Arborele binar, care este prezentat mai jos, este un arbore binar complet, dar nu un arbore binar complet. Este un arbore binar complet deoarece toate nodurile au fie 0, fie 2 copii. Nu este un arbore binar complet, deoarece nodul 3 nu are copii, în timp ce nodul 2 are copiii săi și știm că nodurile ar trebui să fie completate din partea stângă într-un arbore binar complet.
- Arborele binar care este prezentat mai jos este un arbore binar complet, dar nu un arbore binar complet. Este un arbore binar complet, deoarece toate nodurile sunt lăsate umplute. Nu este un arbore binar complet, deoarece nodul 2 are un singur copil.
- Arborele binar care este prezentat mai jos este un arbore binar complet și complet. Este un arbore binar complet, deoarece toate nodurile sunt lăsate umplute. Este un arbore binar complet, deoarece toate nodurile au fie 0, fie 2 copii.
