Różnica między pełnym drzewem binarnym a pełnym drzewem binarnym

Kompletne drzewo binarne kontra pełne drzewo binarne

Drzewo binarne to drzewo, w którym każdy węzeł ma jedno lub dwoje dzieci. W drzewie binarnym węzeł nie może mieć więcej niż dwoje dzieci. W drzewie binarnym dzieci są nazywane dziećmi „lewymi” i „prawymi”. Węzły potomne zawierają odwołanie do ich elementu nadrzędnego. Kompletne drzewo binarne to drzewo binarne, w którym każdy poziom drzewa binarnego jest całkowicie wypełniony oprócz ostatniego poziomu. Na niewypełnionym poziomie węzły są dołączane, zaczynając od pozycji skrajnie lewej. Pełne drzewo binarne jest drzewem, w którym każdy węzeł drzewa ma dwoje dzieci oprócz liści drzewa.

Co to jest pełne drzewo binarne?

Pełne drzewo binarne to drzewo binarne, w którym każdy węzeł drzewa ma dokładnie zero lub dwoje dzieci. Innymi słowy, każdy węzeł drzewa oprócz liści ma dokładnie dwoje dzieci. Rycina 1 poniżej przedstawia pełne drzewo binarne. W pełnym drzewie binarnym liczba węzłów (n), liczba ścieżek (l) i liczba węzłów wewnętrznych (i) jest powiązana w specjalny sposób, tak że jeśli znasz którykolwiek z nich, możesz określić pozostałe dwa wartości w następujący sposób:

1. Jeśli pełne drzewo binarne ma i węzły wewnętrzne:

- Liczba liści l = i + 1

- Łączna liczba węzłów n = 2 * i + 1

2. Jeśli pełne drzewo binarne ma węzły:

- Liczba węzłów wewnętrznych i = (n-1) / 2

- Liczba liści l = (n + 1) / 2

3. Jeśli pełne drzewo binarne ma l liści:

- Łączna liczba węzłów n = 2 * l-1

- Liczba węzłów wewnętrznych i = l-1

Co to jest pełne drzewo binarne?

Jak pokazano na ryc. 2, kompletne drzewo binarne jest drzewem binarnym, w którym każdy poziom drzewa jest całkowicie wypełniony oprócz ostatniego poziomu. Ponadto na ostatnim poziomie należy dołączyć węzły, zaczynając od pozycji skrajnie lewej. Kompletne drzewo binarne wysokości h spełnia następujące warunki:

- Od węzła głównego poziom powyżej ostatniego poziomu reprezentuje pełne drzewo binarne o wysokości h-1

- Jeden lub więcej węzłów na ostatnim poziomie może mieć 0 lub 1 potomek

- Jeśli a, b są dwoma węzłami na poziomie powyżej ostatniego poziomu, to a ma więcej dzieci niż b wtedy i tylko wtedy, gdy a znajduje się na lewo od b

Jaka jest różnica między pełnym drzewem binarnym a pełnym drzewem binarnym?

Kompletne drzewa binarne i pełne drzewa binarne mają wyraźną różnicę. Podczas gdy pełne drzewo binarne jest drzewem binarnym, w którym każdy węzeł ma zero lub dwoje potomków, pełne drzewo binarne jest drzewem binarnym, w którym każdy poziom drzewa binarnego jest całkowicie wypełniony oprócz ostatniego poziomu. Niektóre specjalne struktury danych, takie jak stosy, muszą być kompletnymi drzewami binarnymi, podczas gdy nie muszą być pełnymi drzewami binarnymi. W pełnym drzewie binarnym, jeśli znasz liczbę całkowitych węzłów lub liczbę lavesów lub liczbę węzłów wewnętrznych, możesz łatwo znaleźć pozostałe dwa. Ale pełne drzewo binarne nie ma specjalnej właściwości odnoszącej się do tych trzech atrybutów.