RÓŻNICA MIĘDZY PEŁNYM I KOMPLETNYM DRZEWEM BINARNYM

Drzewo binarne

Są różne rodzaje drzew binarnych ale tutaj omówimy różnicę Kompletne drzewo binarne I Pełne drzewo binarne .

Pełne drzewo binarne:

Pełne drzewo binarne to drzewo binarne, w którym wszystkie węzły mają 0 lub 2 potomstwo . Inaczej mówiąc, pełne drzewo binarne to drzewo binarne, w którym wszystkie węzły, z wyjątkiem węzłów liściowych, mają dwoje potomków.

Pełne drzewo binarne

Pozwalać, I będzie liczbą węzłów wewnętrznych
N będzie całkowitą liczbą węzłów
l być liczbą liści
l być liczbą poziomów
przechodzenie przez drzewo binarne w kolejności

Następnie,

Liczba liści jest (ja + 1) .
Całkowita liczba węzłów wynosi (2i + 1) .
Liczba węzłów wewnętrznych wynosi (n – 1) / 2 .
Liczba liści jest (n + 1) / 2 .
Całkowita liczba węzłów wynosi (2l – 1) .
Liczba węzłów wewnętrznych wynosi (l – 1) .
Liczba liści jest maksymalna (2^l- 1) .

Kompletne drzewo binarne:

Mówi się, że drzewo binarne to a kompletne drzewo binarne jeśli wszystkie jego poziomy, z wyjątkiem ewentualnie ostatniego poziomu, mają maksymalną liczbę możliwych węzłów, a wszystkie węzły w ostatni poziom pojawia się jak najdalej po lewej stronie .

Kompletne drzewo binarne

Można stąd rozpoznać 2 punkty,

Zawsze należy najpierw wypełnić lewą stronę węzła liścia.

Nie jest konieczne, aby ostatni węzeł liścia miał prawego rodzeństwa.

Sprawdź poniższe przykłady, aby lepiej zrozumieć pełne i kompletne drzewo binarne.

Przykład 1:

Ani kompletne, ani pełne

Węzeł C ma więc tylko jedno dziecko, nie jest to pełne drzewo binarne.

Węzeł C dlatego też ma prawe dziecko, ale nie ma lewego dziecka nie jest to również kompletne drzewo binarne.

Zatem drzewo binarne pokazane powyżej to ani kompletne, ani pełne drzewo binarne.

Przykład 2:

Pełne, ale nie kompletne

Wszystkie węzły mają jedno 0 Lub 2 potomstwo, zatem jest to pełne drzewo binarne .
Nie jest to kompletne drzewo binarne, ponieważ node B nie ma dzieci, podczas gdy node C ma dzieci i zgodnie z pełnym drzewem binarnym węzły należy wypełnić z lewa strona .

Zatem drzewo binarne pokazane powyżej to a Pełne drzewo binarne i to jest nie jest kompletnym drzewem binarnym.

Przykład 3:

Kompletny, ale nie pełny

Jest to kompletne drzewo binarne, ponieważ wszystkie węzły są wypełnione.
Dlatego węzeł B ma tylko jedno dziecko nie jest to pełne drzewo binarne.

Zatem drzewo binarne pokazane powyżej to a Kompletne drzewo binarne i to jest nie pełne drzewo binarne.

Przykład 4:
sieciowy system operacyjny

Kompletne i pełne

To jest Kompletny binarny drzewo, ponieważ wszystkie węzły są pozostało wypełnione .

Wszystkie węzły mają jedno 0 Lub 2 potomstwo, dlatego jest to A pełne drzewo binarne .

Zatem drzewo binarne pokazane powyżej to zarówno kompletne, jak i pełne drzewo binarne.

Tak nie.	Kompletne drzewo binarne	Pełne drzewo binarne
1.	W pełnym drzewie binarnym węzeł na ostatnim poziomie może mieć tylko jedno dziecko.	W pełnym drzewie binarnym węzeł nie może mieć tylko jednego dziecka.
2.	W pełnym drzewie binarnym węzeł należy wypełnić od lewej do prawej.	W pełnym drzewie binarnym nie ma kolejności wypełniania węzłów.
3.	Kompletne drzewa binarne są używane głównie w strukturach danych opartych na stertach.	Pełne drzewo binarne nie ma zastosowania jako takiego, ale jest również nazywane właściwym drzewem binarnym.
4.	Kompletne drzewo binarne jest również nazywane prawie kompletnym drzewem binarnym.	Pełne drzewo binarne zwane także właściwym drzewem binarnym lub drzewem 2.
5	Kompletne drzewo binarne musi mieć cały węzeł liści dokładnie na tej samej głębokości.	W pełnym binarnym poziomie liści drzewa niekoniecznie muszą znajdować się na tej samej głębokości.

TechCodeview