Co to jest pełne drzewo binarne?

Pełne drzewo binarne można zdefiniować jako: drzewo binarne w którym wszystkie węzły mają 0 lub dwoje dzieci. Innymi słowy, pełne drzewo binarne można zdefiniować jako drzewo binarne, w którym wszystkie węzły mają dwoje dzieci, z wyjątkiem węzłów liści.

Poniższe drzewo jest pełnym drzewem binarnym:

Powyższe drzewo jest pełnym drzewem binarnym, ponieważ wszystkie węzły z wyjątkiem węzłów liściowych mają dwoje dzieci.

Twierdzenie o pełnym drzewie binarnym:

zablokowane kontakty

Rozważ drzewo binarne T jako drzewo niepuste, a następnie:

• Niech I będzie węzłem wewnętrznym drzewa, a L węzłem liścia w drzewie, wówczas liczba węzłów liści będzie równa:
  L = ja + 1
• Jeśli T ma, I liczbę węzłów wewnętrznych, a N jest całkowitą liczbą węzłów, wówczas całkowita liczba węzłów będzie równa:
  N = 2I + 1
• Jeżeli T zawiera całkowitą liczbę węzłów „N”, a „I” jest liczbą węzłów wewnętrznych, to liczba węzłów wewnętrznych będzie równa:
  Ja = (N-1)/2
• Jeśli „T” ma całkowitą liczbę węzłów „N”, a „L” jest liczbą węzłów liściowych, wówczas liczba węzłów liściowych będzie równa:
  L = (N+1)/2
• Jeśli „T” zawiera liczbę węzłów liściowych „L”, wówczas całkowita liczba węzłów będzie równa:
  N = 2L - 1
• Jeżeli „T” ma liczbę węzłów liściowych „L”, a „I” jest liczbą węzłów wewnętrznych, to liczba węzłów wewnętrznych będzie równa:
  Ja = L - 1

Co to jest pełne drzewo binarne?

Drzewo binarne nazywa się kompletnym drzewem binarnym, gdy wszystkie poziomy są całkowicie wypełnione, z wyjątkiem ostatniego poziomu, który jest wypełniany od lewej strony.

Poniższe drzewo jest kompletnym drzewem binarnym:

Pełne drzewo binarne jest podobne do pełnego drzewa binarnego, z wyjątkiem dwóch różnic podanych poniżej:

• Wypełnianie węzła liścia należy rozpocząć od lewej strony.
• Nie jest obowiązkowe, aby ostatni węzeł-liść miał prawe rodzeństwo.

Rozumiemy powyższe punkty na przykładzie:

co to jest jajko wielkanocne na Androida

Rozważ poniższe drzewo:

Powyższe drzewo jest kompletnym drzewem binarnym, ale nie pełnym drzewem binarnym, ponieważ węzeł 6 nie ma swojego prawego rodzeństwa.

Utworzenie kompletnego drzewa binarnego

Załóżmy, że mamy tablicę 6 elementów pokazaną poniżej:

Powyższa tablica zawiera 6 elementów, tj. 1, 2, 3, 4, 5, 6. Aby utworzyć kompletne drzewo binarne, należy wykonać następujące kroki:

Krok 1: Najpierw wybierzemy pierwszy element tablicy, czyli 1, i utworzymy węzeł główny drzewa. Liczba elementów dostępnych na pierwszym poziomie wynosi 1.

Krok 2: Teraz wybierzemy drugi i trzeci element tablicy. Zachowaj drugi element i trzeci element tablicy jako odpowiednio lewe i prawe dziecko węzła głównego, jak pokazano poniżej:

Jak możemy zauważyć powyżej, liczba elementów dostępnych na drugim poziomie wynosi 2.

wyliczenia Java

Krok 3: Teraz wybierzemy kolejne dwa elementy z tablicy, tj. 4 i 5. Zachowaj te dwa elementy po lewej i prawej stronie węzła 2, jak pokazano poniżej:

Jak możemy zauważyć powyżej, węzły 4 i 5 są odpowiednio lewym i prawym dzieckiem węzła 2.

Krok 4: Teraz wybierzemy ostatni element tablicy, tj. 6, i pozostawimy go jako lewe dziecko węzła 3, ponieważ wiemy, że w pełnym drzewie binarnym węzły są wypełniane od lewej strony, jak pokazano poniżej:

Jak możemy zauważyć, drugi poziom zawiera 3 elementy.

Rozumiemy różnice między pełnym i pełnym drzewem binarnym na podstawie obrazów.

1. Drzewo binarne pokazane poniżej nie jest ani kompletnym, ani pełnym drzewem binarnym. Nie jest to pełne drzewo binarne, ponieważ węzeł 3 ma tylko jedno dziecko. Nie jest to również kompletne drzewo binarne, ponieważ węzły należy wypełniać od lewej strony, ale węzeł 3 ma prawe dziecko i nie ma lewego dziecka.
   
2. Drzewo binarne pokazane poniżej jest pełnym drzewem binarnym, ale nie kompletnym drzewem binarnym. Jest to pełne drzewo binarne, ponieważ wszystkie węzły mają 0 lub 2 dzieci. Nie jest to pełne drzewo binarne, ponieważ węzeł 3 nie ma dzieci, natomiast węzeł 2 ma swoje dzieci i wiemy, że w pełnym drzewie binarnym węzły należy wypełniać od lewej strony.
   
3. Drzewo binarne pokazane poniżej jest kompletnym drzewem binarnym, ale nie pełnym drzewem binarnym. Jest to kompletne drzewo binarne, ponieważ wszystkie węzły są wypełnione. Nie jest to pełne drzewo binarne, ponieważ węzeł 2 ma tylko jedno dziecko.
   
4. Drzewo binarne pokazane poniżej jest zarówno kompletnym, jak i pełnym drzewem binarnym. Jest to kompletne drzewo binarne, ponieważ wszystkie węzły są wypełnione. Jest to pełne drzewo binarne, ponieważ wszystkie węzły mają 0 lub 2 dzieci.