Jestem zdezorientowany co do terminologii poniższych drzew, studiowałem Drzewo i nie jestem w stanie rozróżnić tych drzew:
a) Pełne drzewo binarne
b) Ścisłe drzewo binarne
c) Pełne drzewo binarne
Proszę, pomóż mi rozróżnić te drzewa. Kiedy i gdzie te drzewa są używane w strukturze danych?
Odpowiedzi:
Pełne drzewo binarne (czasami właściwe drzewo binarne lub 2-drzewo lub ściśle binarne drzewo) to drzewo, w którym każdy węzeł inny niż liście ma dwoje dzieci.
Więc nie masz węzłów z tylko jednym dzieckiem. Wydaje się być tym samym, co ścisłe drzewo binarne.
Oto obraz pełnego / ścisłego drzewa binarnego z google:
Kompletne drzewo binarne to drzewo binarne, w którym każdy poziom, z wyjątkiem być może ostatniego, jest całkowicie wypełniony, a wszystkie węzły są tak daleko, jak to możliwe.
Wydaje się, że oznacza zrównoważone drzewo.
Tutaj jest obraz pełnego drzewa binarnego, z google, pełna część drzewa to bonus.
Idealne drzewo:
x
/ \
/ \
x x
/ \ / \
x x x x
/ \ / \ / \ / \
x x x x x x x x
Kompletne drzewo:
x
/ \
/ \
x x
/ \ / \
x x x x
/ \ /
x x x
Ścisłe / pełne drzewo:
x
/ \
/ \
x x
/ \
x x
/ \
x x
Istnieje różnica między ŚCIĄGŁYM a PEŁNYM DRZEWEM BINARNYM.
1) PEŁNE DRZEWO BINARNE: Drzewo binarne o wysokości h, które zawiera dokładnie (2 ^ h) -1 elementów, nazywane jest pełnym drzewem binarnym . (Ref: str. 427, Struktury danych, algorytmy i aplikacje w C ++ [University Press], wydanie drugie autorstwa Sartaj Sahni).
lub innymi słowy
W PEŁNYM DRZEWIE BINARNYM każdy węzeł ma dokładnie 0 lub 2 dzieci, a wszystkie węzły liści są na tym samym poziomie.
Na przykład: Poniżej przedstawiono PEŁNE DRZEWO BINARNE:
18
/ \
15 30
/ \ / \
40 50 100 40
2) ŚCIĘTE DRZEWO BINARNE: Każdy węzeł ma dokładnie 0 lub 2 dzieci.
Na przykład: Poniżej znajduje się ŚCIĄGLIWE DRZEWO BINARNE:
18
/ \
15 30
/ \
40 50
Myślę, że nie ma zamieszania w definicji kompletnego drzewa binarnego, ale dla kompletności postu chciałbym powiedzieć, czym jest pełne drzewo binarne.
3) KOMPLETNE DRZEWO BINARNE: Drzewo binarne jest kompletne. Drzewo binarne jest kompletne, jeśli wszystkie poziomy są całkowicie wypełnione, z wyjątkiem ostatniego poziomu, a ostatni poziom ma wszystkie klawisze tak pozostawione, jak to tylko możliwe.
Na przykład: Poniżej przedstawiono KOMPLETNE DRZEWO BINARNE:
18
/ \
15 30
/ \ / \
40 50 100 40
/ \ /
8 7 9
Uwaga: poniżej znajduje się również pełne drzewo binarne:
18
/ \
15 30
/ \ / \
40 50 100 40
Zastrzeżenie - Głównym źródłem niektórych definicji jest wikipedia, wszelkie sugestie dotyczące ulepszenia mojej odpowiedzi są mile widziane.
Chociaż ten post ma akceptowaną odpowiedź i jest dobry, nadal byłem zdezorientowany i chciałbym dodać więcej wyjaśnień dotyczących różnicy między tymi terminami.
(1) PEŁNE DRZEWO BINARNE - Pełne drzewo binarne to drzewo binarne, w którym każdy węzeł poza liśćmi ma dwoje dzieci. Nazywane jest również drzewem ściśle binarnym .
Dwa powyższe przykłady to pełne lub ściśle binarne drzewo.
(2) KOMPLETNE DRZEWO BINARNE - Definicja pełnego drzewa binarnego jest dość niejednoznaczna i stwierdza: - Kompletne drzewo binarne to drzewo binarne, w którym każdy poziom, z wyjątkiem być może ostatniego , jest całkowicie wypełniony, a wszystkie węzły są takie same jak najbardziej w lewo. Może mieć od 1 do 2h węzłów, jak najdalej w lewo, na ostatnim poziomie h
Zwróć uwagę na linie kursywą.
Niejednoznaczność tkwi w wierszach zapisanych kursywą, „z wyjątkiem ewentualnie ostatniego”, co oznacza, że ostatni poziom może być również całkowicie wypełniony, tj. Ten wyjątek nie zawsze musi być spełniony. Jeśli wyjątek nie zachowuje się, jest dokładnie taki sam, jak drugi opublikowany przeze mnie obraz, który można również nazwać doskonałym drzewem binarnym . Tak więc idealne drzewo binarne jest również pełne i kompletne, ale nie odwrotnie, co będzie jasne dzięki jeszcze jednej definicji, którą muszę stwierdzić:
PRAWIE KOMPLETNE DRZEWO BINARNE - Gdy wyjątek w definicji pełnego drzewa binarnego utrzymuje się, wtedy nazywa się prawie kompletnym drzewem binarnym lub prawie kompletnym drzewem binarnym. Jest to po prostu rodzaj kompletnego drzewa binarnego, ale potrzebna jest oddzielna definicja, aby było bardziej jednoznaczne.
Więc prawie kompletne drzewo binarne będzie wyglądać tak, możesz zobaczyć na obrazie, że węzły są jak najdalej z lewej strony, więc bardziej przypomina podzbiór pełnego drzewa binarnego, mówiąc bardziej rygorystycznie, każde prawie pełne drzewo binarne jest kompletnym binarnym drzewo, ale nie odwrotnie. :
Wnioskując z powyższych odpowiedzi, oto dokładna różnica między pełnymi / ściśle, kompletnymi i doskonałymi drzewami binarnymi
Pełne / ściśle binarne drzewo : - Każdy węzeł oprócz węzłów liści ma dwoje dzieci
Kompletne drzewo binarne : - Każdy poziom z wyjątkiem ostatniego jest całkowicie wypełniony, a wszystkie węzły są wyrównane.
Idealne drzewo binarne : - Każdy węzeł oprócz węzłów liści ma dwoje dzieci i każdy poziom (także ostatni poziom) jest całkowicie wypełniony.
Rozważmy drzewo binarne, którego węzły są rysowane na wzór drzewa. Teraz zacznij numerować węzły od góry do dołu i od lewej do prawej. Pełne drzewo ma następujące właściwości:
Jeśli n ma dzieci, to wszystkie węzły ponumerowane mniej niż n mają dwoje dzieci.
Jeśli n ma jedno dziecko, musi to być lewe dziecko, a wszystkie węzły mniejsze niż n mają dwoje dzieci. Ponadto żaden węzeł o numerze większym niż n nie ma dzieci.
Jeśli n nie ma dzieci, to żaden węzeł o numerze większym niż n nie ma dzieci.
Pełne drzewo binarne może być używane do reprezentowania sterty. Można go łatwo przedstawić w ciągłej pamięci bez przerw (tj. Wszystkie elementy tablicy są używane z wyjątkiem miejsca, które może istnieć na końcu).
Pełne drzewo binarne to kompletne drzewo binarne, ale odwrócenie nie jest możliwe, a jeśli głębokość pliku binarnego wynosi n, nie. węzłów w pełnym drzewie binarnym to (2 ^ n-1). W drzewie binarnym nie jest konieczne, aby miało dwoje dzieci, ale w pełnym binarnym drzewie każdy węzeł nie ma lub dwoje dzieci.
Aby rozpocząć od podstaw, bardzo ważne jest zrozumienie samego drzewa binarnego, aby zrozumieć jego różne typy.
Drzewo jest drzewem binarnym wtedy i tylko wtedy, gdy: -
- Ma węzeł główny, który może nie mieć żadnych węzłów podrzędnych (0 węzłów potomnych, drzewo NULL)
–Węzeł główny może mieć 1 lub 2 węzły potomne. Każdy taki węzeł sam tworzy drzewo abinarne
–Liczba węzłów potomnych może wynosić 0, 1, 2 ....... nie więcej niż 2
–Istnieje niepowtarzalna ścieżka od katalogu głównego do każdego innego węzła
Przykład:
X
/ \
X X
/ \
X X
Przechodząc do zapytanych terminologii:
Drzewo binarne jest kompletnym drzewem binarnym (o wysokości h, przyjmujemy węzeł główny jako 0) wtedy i tylko wtedy, gdy: -
Poziomy od 0 do h-1 reprezentują pełne drzewo binarne o wysokości h-1
- Jeden lub więcej węzłów na poziomie h-1 może mieć 0 lub 1 węzłów podrzędnych
Jeśli j, k są węzłami na poziomie h-1, to j ma więcej węzłów potomnych niż k wtedy i tylko wtedy, gdy j znajduje się na lewo od k, tj. Na ostatnim poziomie (h) może brakować węzłów liści, jednak te obecne muszą przesunąć w lewo
Przykład:
X
/ \
/ \
/ \
X X
/ \ / \
X X X X
/ \ / \ / \ / \
X X X X X X X X
Drzewo binarne jest drzewem ściśle binarnym wtedy i tylko wtedy, gdy: -
Każdy węzeł ma dokładnie dwa węzły podrzędne lub nie ma żadnych węzłów
Przykład:
X
/ \
X X
/ \
X X
/ \ / \
X X X X
Drzewo binarne jest pełnym drzewem binarnym wtedy i tylko wtedy, gdy: -
Każdy węzeł inny niż liść ma dokładnie dwa węzły potomne
Wszystkie węzły liści są na tym samym poziomie
Przykład:
X
/ \
/ \
/ \
X X
/ \ / \
X X X X
/ \ / \ / \ / \
X X X X X X X X
/ \ / \ / \ / \ / \ / \ / \ / \
X X X X X X X X X X X X X X X X
Powinieneś także wiedzieć, czym jest idealne drzewo binarne?
Drzewo binarne jest doskonałym drzewem binarnym wtedy i tylko wtedy, gdy: -
- to pełne drzewo binarne
- Wszystkie węzły liści są na tym samym poziomie
Przykład:
X
/ \
/ \
/ \
X X
/ \ / \
X X X X
/ \ / \ / \ / \
X X X X X X X X
/ \ / \ / \ / \ / \ / \ / \ / \
X X X X X X X X X X X X X X X X
Cóż, przykro mi, że nie mogę publikować zdjęć, ponieważ nie mam 10 punktów reputacji. Mam nadzieję, że to pomoże Tobie i innym!
W moim ograniczonym doświadczeniu z drzewem binarnym myślę:
Rozważmy drzewo binarne o wysokości „h”. Drzewo binarne nazywane jest kompletnym drzewem binarnym, jeśli wszystkie liście znajdują się na wysokości „h” lub „h-1” bez żadnych brakujących liczb w sekwencji.
1
/ \
2 3
/ \
4 5
To jest kompletne drzewo binarne.
1
/ \
2 3
/ /
4 6
Nie jest to pełne drzewo binarne, ponieważ w sekwencji brakuje węzła o numerze 5
pełne drzewo binarne jest pełne, jeśli każdy węzeł ma 0 lub 2 dzieci. w pełnej binarnej liczbie węzłów liści to liczba węzłów wewnętrznych plus 1 L = l + 1
Kompletne drzewo binarne: Wszystkie poziomy są całkowicie wypełnione, z wyjątkiem najniższego poziomu i jednej głównej rzeczy, wszystkie elementy liści muszą opuścić dziecko. Ścisłe drzewo binarne: W tym drzewie każdy węzeł nie będący liściem nie ma potomka, tj. Ani lewy, ani prawy. Pełne drzewo binarne: każdy węzeł ma zerowe dziecko lub dwoje dzieci (nigdy nie ma jednego dziecka).