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.
