A Struktura danych drzewa binarnego to hierarchiczna struktura danych, w której każdy węzeł ma co najwyżej dwoje dzieci, określanych jako lewe i prawe dziecko. Jest powszechnie stosowany w informatyce do wydajnego przechowywania i wyszukiwania danych za pomocą różnych operacji, takich jak wstawianie, usuwanie i przeglądanie.

Wstęp:

• Właściwości drzewa binarnego
• Rodzaje drzew binarnych
• Zastosowania, zalety i wady drzewa binarnego
• Drzewo binarne (implementacja tablicy)
• Kompletne drzewo binarne
• Idealne drzewo binarne

Podstawowe operacje na drzewie binarnym:

• Przemierzanie drzew (zamówienie, zamówienie przedsprzedażowe i zamówienie pocztowe)
• Przechodzenie przez drzewo kolejności poziomów
• Znajdź maksymalną głębokość lub wysokość danego drzewa binarnego
• Wstawienie do drzewa binarnego
• Usuwanie w drzewie binarnym
• Wyliczanie drzew binarnych

Kilka innych ważnych przejść przez drzewo binarne:

• Przechodzenie rzędu poziomów w formie spiralnej
• Odwrotne przechodzenie przez poziom zamówienia
• BFS vs DFS dla drzewa binarnego
• Przechodzenie przez drzewo Inorder bez rekurencji
• Przejście Morrisa w przedsprzedaży
• Iteracyjne przeglądanie zamówień w przedsprzedaży
• Iteracyjne przechodzenie po zamówieniu przy użyciu dwóch stosów
• Przechodzenie po przekątnej drzewa binarnego
• Przejście graniczne drzewa binarnego

Łatwe problemy ze strukturą danych drzewa binarnego:

• Oblicz głębokość pełnego drzewa binarnego z przedsprzedaży
• Skonstruuj drzewo na podstawie przejść w kolejności Inorder i Level
• Sprawdź, czy dane drzewo binarne jest SumTree
• Sprawdź, czy dwa węzły są kuzynami w drzewie binarnym
• Sprawdź, czy usunięcie krawędzi może podzielić drzewo binarne na dwie połowy
• Sprawdź, czy dane drzewo binarne jest doskonałe, czy nie
• Sprawdź, czy drzewo binarne zawiera zduplikowane poddrzewa o rozmiarze 2 lub większym
• Sprawdź, czy dwa drzewa są lustrzane
• Składane drzewa binarne
• Drzewo symetryczne (odbicie lustrzane samego siebie)
• Napisz kod sprawdzający, czy dwa drzewa są identyczne
• Poddrzewo z podaną sumą w drzewie binarnym
• Zwięzłe kodowanie drzewa binarnego
• Napisz program obliczający wielkość drzewa
• Średnica drzewa binarnego
• Uzyskaj poziom węzła w drzewie binarnym

Średnie problemy ze strukturą danych drzewa binarnego:

• Znajdź wszystkie możliwe drzewa binarne przy zadanym przejściu Inorder
• Wypełnij następcę Inorder dla wszystkich węzłów
• Skonstruuj kompletne drzewo binarne na podstawie jego reprezentacji na liście połączonych
• Minimalna zamiana wymagana do konwersji drzewa binarnego na drzewo wyszukiwania binarnego
• Konwertuj dane drzewo binarne na listę podwójnie połączoną | Zestaw 1
• Przekształć drzewo w las parzystych węzłów
• Odwróć drzewo binarne
• Wydrukuj ścieżki od korzenia do liścia bez użycia rekurencji
• Sprawdź, czy podane przejścia Preorder, Inorder i Postorder należą do tego samego drzewa
• Sprawdź, czy dane drzewo binarne jest kompletne czy nie | Zestaw 1 (rozwiązanie iteracyjne)
• Sprawdź, czy drzewo binarne jest poddrzewem innego drzewa binarnego | Zestaw 2
• Znajdź największą sumę poddrzewa w drzewie
• Maksymalna suma węzłów w drzewie binarnym, taka że żadne dwa nie sąsiadują ze sobą
• Najniższy wspólny przodek w drzewie binarnym | Zestaw 1
• Wysokość drzewa ogólnego z tablicy nadrzędnej
• Znajdź odległość między dwoma podanymi kluczami drzewa binarnego

Trudne problemy ze strukturą danych drzewa binarnego:

• Zmodyfikuj drzewo binarne, aby przeglądać zamówienia w przedsprzedaży wyłącznie przy użyciu właściwych wskaźników
• Skonstruuj pełne drzewo binarne, korzystając z przechodzenia w przedsprzedaży i przechodzenia w przedsprzedaży jego drzewa lustrzanego
• Skonstruuj specjalne drzewo na podstawie podanego przejścia w przedsprzedaży
• Skonstruuj drzewo z macierzy przodków
• Skonstruuj pełne drzewo k-ary na podstawie jego przejścia w przedsprzedaży
• Skonstruuj drzewo binarne z ciągu znaków z reprezentacją nawiasową
• Konwertuj drzewo binarne na listę podwójnie połączoną w sposób spiralny
• Konwertuj drzewo binarne na cykliczną listę podwójnych łączy
• Konwertuj wyrażenie trójskładnikowe na drzewo binarne
• Sprawdź, czy istnieje ścieżka od korzenia do liścia o podanej sekwencji
• Usuń wszystkie węzły, które nie leżą na żadnej ścieżce o sumie>= k
• Maksymalna suma spirali w drzewie binarnym
• Suma węzłów na k-tym poziomie drzewa reprezentowanego jako ciąg znaków
• Suma wszystkich liczb utworzonych od ścieżki korzenia do liścia
• Połącz dwa drzewa binarne, wykonując sumę węzłów (rekursywną i iteracyjną)
• Znajdź korzeń drzewa, w którym podana jest suma identyfikatorów dzieci dla każdego węzła

Szybkie linki :

• „Wideo” o drzewach