Różnica Między Pełnym Drzewem Binarnym A Pełnym Drzewem Binarnym

2024 Autor: Mildred Bawerman | [email protected]. Ostatnio zmodyfikowany: 2023-12-16 08:41

Pełne drzewo binarne kontra pełne drzewo binarne

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

Co to jest pełne drzewo binarne?

Pełne drzewo binarne to drzewo binarne, w którym każdy węzeł ma dokładnie zero lub dwoje dzieci. Innymi słowy, każdy węzeł w drzewie poza liśćmi ma dokładnie dwoje dzieci. Rysunek 1 poniżej przedstawia pełne drzewo binarne. W pełnym drzewie binarnym liczba węzłów (n), liczba węzłów (l) i liczba węzłów wewnętrznych (i) są powiązane w specjalny sposób, tak że znając którykolwiek z nich, można 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 skrzydeł l = i + 1

- Całkowita liczba węzłów n = 2 * i + 1

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

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

- Liczba skrzydeł l = (n + 1) / 2

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

- Całkowita 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 rysunku 2, kompletne drzewo binarne to drzewo binarne, w którym każdy poziom drzewa jest całkowicie wypełniony, z wyjątkiem ostatniego. Ponadto na ostatnim poziomie węzły powinny być dołączane, zaczynając od skrajnej lewej pozycji. Pełne drzewo binarne o wysokości h spełnia następujące warunki:

- Od węzła głównego, poziom powyżej ostatniego poziomu przedstawia 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 dziecko

- Jeśli a, b to dwa węzły 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?

Pełne 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 dzieci, pełne drzewo binarne jest drzewem binarnym, w którym każdy poziom drzewa binarnego jest całkowicie wypełniony, z wyjątkiem ostatniego poziomu. Niektóre specjalne struktury danych, takie jak sterty, muszą być kompletnymi drzewami binarnymi, podczas gdy nie muszą to być pełne drzewa binarne. W pełnym drzewie binarnym, jeśli znasz liczbę wszystkich węzłów lub liczbę warstw lub liczbę węzłów wewnętrznych, możesz bardzo łatwo znaleźć pozostałe dwa. Ale pełne drzewo binarne nie ma specjalnej właściwości związanej z tymi trzema atrybutami.