wielu programistów i moich czytelników prosiło mnie o podzielenie się pytaniami o kodowanie drzewa binarnego, tak jak zrobiłem to dla tablicy, listy połączonej, ciągu znaków, projektowania oprogramowania, wzorców, tabeli skrótów i struktury danych w ogóle. To zadanie czekało na mnie od dłuższego czasu i utknęło mi w poszukiwaniu rozwiązania dla każdego pytania, które mogłem zebrać. Postanowiłem więc opublikować listę pytań z wywiadu z drzewem binarnym i ewentualnie opublikować rozwiązanie jako osobny artykuł później. To tak, jakby stworzyć interfejs i później dostarczyć implementację, aby nie blokować innych ludzi, którzy są zależni od twojego interfejsu (w rzeczywistości jest to jedna z zalet korzystania z interfejsu w Javie lub jakimkolwiek innym języku programowania).
co to jest struktura danych drzewa binarnego?
w każdym razie, wracając do drzewa binarnego, chciałbym ponownie iterować niektóre przydatne punkty dotyczące struktury danych drzewa w ogóle, które pomogą Ci rozwiązać te pytania na własną rękę:
1) drzewo jest hierarchiczną strukturą danych w przeciwieństwie do tablicy lub połączonej listy, które są liniowe. Oznacza to, że możesz przechowywać informacje hierarchiczne za pomocą struktury danych drzewa, takiej jak struktura organizacyjna, drzewo genealogiczne itp.
2) drzewo ma węzły i dzieci. Górny lub pierwszy węzeł nazywany jest korzeniem.
3) Jeśli chcesz zwizualizować, struktura danych drzewa jest jak odwrócone drzewo w prawdziwym świecie. To znaczy, kiedy widzisz drzewa wokół siebie, ich korzenie są na dole, ale kiedy rysujesz strukturę danych drzewa w programowaniu lub informatyce, ich korzeń jest na górze.
4) drzewo binarne to specjalne drzewo, w którym można mieć co najwyżej dwoje dzieci. Oznacza to, że jeden węzeł nie może mieć dziecka, jednego dziecka lub dwójki dzieci. Nie mogą mieć trójki dzieci ani więcej.
5) wszystkie węzły, które nie mają dzieci, są znane jako węzeł liści.
6) Binary Search Tree to specjalny typ drzewa binarnego, w którym wartości lewych podtrees są mniejsze lub równe root, a wartości węzłów w prawych podtrees są większe lub równe root. Zapewnia to strukturę sortowania do binarnego drzewa wyszukiwania, co sprawia, że wyszukiwanie jest naprawdę szybkie.
Możesz również sprawdzić struktury danych i algorytmy: Głębokie nurkowanie przy użyciu kursu Java na Udemy, aby dowiedzieć się więcej o binarnych drzewach wyszukiwania. To jeden z najlepszych kursów odświeżających strukturę danych i umiejętności algorytmiczne.
7) drzewo wyszukiwania binarnego jest ściśle związane z wyszukiwaniem binarnym, które działa na zasadzie zmniejszania rozmiaru wejściowego do połowy po każdej iteracji. To sprawia, że wyszukiwanie jest naprawdę szybkie i można znaleźć dowolny element w binarnym drzewie wyszukiwania w czasie O (logN), ale tylko wtedy, gdy drzewo jest zrównoważone.
8) istnieją dwa sposoby trawersowania struktury danych drzewa: depth-first lub level first. W głębi-najpierw idziesz w dół, aż nie ma już węzła do odwiedzenia, a następnie wracasz do odwiedzenia węzłów na tym samym poziomie.
podczas przechodzenia w kolejności poziomów odwiedzasz wszystkie węzły na tym samym poziomie, zanim przejdziesz do następnego poziomu. Istnieje również pre-order, post-order I in-order traversal dla binary, który jest używany do trawersowania węzłów drzewa binarnego. Inorder traversal jest wyjątkowy, ponieważ odwiedza wszystkie węzły w posortowanej kolejności.
9) zbalansowane drzewo binarne jest jak posiadanie równej liczby węzłów na każdym poddrzewie, jeśli masz wszystkie węzły na jedynym lewym lub prawym poddrzewie, twoje drzewo binarne stanie się niezbalansowane i będzie działać jak połączona lista, jak pokazano na poniższym diagramie:
10) niezbalansowane lub niezbalansowane drzewo wyszukiwania binarnego działa jak lista powiązana, w której wyszukiwanie zajmuje Czas O(N) w przeciwieństwie do czasu o(logN) w zbalansowanym drzewie wyszukiwania binarnego.
to niektóre z ważnych punktów, które każdy programista powinien wiedzieć o strukturze danych drzewa binarnego. Pomoże Ci rozwiązać problemy z kodowaniem opartym na drzewie. Jeśli chcesz dowiedzieć się więcej o drzewie binarnym i innych strukturach danych, proponuję dołączyć do dobrego kursu struktury danych i algorytmów, takiego jak struktury danych i algorytmy: Głębokie nurkowanie przy użyciu Javy na Udemy do szczotkowania podstaw.
40+ Binary Tree Interview Questions for Java Programmers
nie tracąc więcej czasu, oto moja lista problemów kodowania opartych na drzewie binarnym i drzewie wyszukiwania binarnego (BST) z programowania rozmów kwalifikacyjnych. Połączyłem się z rozwiązaniem wszędzie tam, gdzie jest to możliwe, ale jeśli nie ma linku, możesz również znaleźć rozwiązanie, wykonując wyszukiwanie w Google. Są to bardzo popularne pytania i wiele osób już je rozwiązało.
aby uzyskać jak najwięcej z tej listy, spróbuj rozwiązać problem, zanim spojrzysz na rozwiązanie, tylko wtedy twój umysł będzie działał i będziesz musiał stawić czoła wyzwaniom i skonsolidować swoje zrozumienie. Jeśli spojrzysz na rozwiązanie natychmiast, nauczysz się tylko 10%, ale jeśli spróbujesz, nauczysz się od 80 do 90% pojęć i sztuczek stojących za każdym pytaniem.
1) Jak znaleźć najniższego wspólnego przodka drzewa binarnego w Javie? (rozwiązanie)
2) Jak wydrukować lewy widok drzewa binarnego w Javie?
3) napisać program do budowy drzewa z inordera i preordera w Javie? (rozwiązanie)
4) Jak wydrukować wspólne węzły w dwóch binarnych drzewach wyszukiwania w Javie? (rozwiązanie)
5) Dlaczego Binary heap jest lepszym Wyborem niż BST do implementacji kolejki priorytetów?
6) Jak sprawdzić czy dane drzewo binarne jest zbalansowane czy nie? Napisz metodę Java, która akceptuje drzewo binarne i zwraca true, jeśli jest zbalansowane lub false. (rozwiązanie)
7) jakie są zalety binarnego drzewa wyszukiwania w stosunku do struktury danych z tabelą hashtable?
8) Jak sprawdzić, czy dane drzewo binarne jest podzbiorem innego drzewa binarnego? (rozwiązanie)
podałeś dwa drzewa binarne i musisz zwrócić true, jeśli pierwsze drzewo binarne jest podzbiorem drugiego. Podzbiór drzewa binarnego BT jest drzewem t składającym się z węzła z BT i wszystkich jego potomków. Na przykład, w następującym przypadku, T1 jest podzbiorem drzewa binarnego BT
9) Jak znaleźć odległość między dwoma węzłami w drzewie binarnym? (rozwiązanie)
10) Jak znaleźć najniższego wspólnego przodka w drzewie binarnym w Javie? (rozwiązanie)
11) napisać program Java, aby sprawdzić, czy wszystkie liście danego drzewa binarnego są na tym samym poziomie? (rozwiązanie)
12) Jak przekonwertować dane drzewo binarne na podwójnie połączoną listę w Javie? (rozwiązanie)
13) napisać program, aby znaleźć głębokość danego drzewa binarnego w Javie? (rozwiązanie)
14) Jaka jest różnica między drzewami wyszukiwania binarnego i binarnego? [odpowiedz]
15) co to jest samoistne drzewo?
16) co to jest drzewo AVL? [odpowiedz]
17) napisać program Java do wydruku pre-order z binarnego drzewa wyszukiwania? Dać rozwiązanie używając zarówno iteracji, jak i rekurencji? (rozwiązanie)
18) Wydrukuj Post-order traversal BST? Podaj algorytm iteracyjny i rekurencyjny (rozwiązanie)
19) Wydrukuj inorder traversal BST w Javie? Podaj zarówno algorytmy iteracyjne, jak i rekurencyjne (rozwiązanie)
20) podałeś BST, gdzie dwa węzły są zamienione? Jak odzyskać oryginalny BST? (rozwiązanie)
21) Jak przekonwertować drzewo binarne na drzewo wyszukiwania binarnego w Javie? (rozwiązanie)
22) Znajdź największy podzbiór BST danego drzewa binarnego w Javie? (rozwiązanie)
23) napisać program Java do łączenia węzłów na tym samym poziomie co drzewo binarne? (rozwiązanie)
24) Co to jest struktura danych Trie?
25) Jaka jest różnica między drzewem binarnym a Trie? [odpowiedz]
26) Wydrukuj przodków danego węzła drzewa binarnego w Javie? (rozwiązanie)
27) napisać program Java, aby wydrukować poziom danego węzła w drzewie binarnym? (rozwiązanie)
28) wypisuje wspólne węzły dwóch podanych BST w Javie? (rozwiązanie)
29) dać drzewo binarne, wypisać całą ścieżkę root-to-leaf w Javie? (solucja)
30) Drukuj Worder Tree traversal bez rekursji w Javie? (rozwiązanie)
31) Drukuj preorder Tree traversal bez rekurencji i stosu w Javie? (solucja)
32) Drukowanie drzewa Postordera bez rekursji w Javie?
33) Program Java do sprawdzania czy dane drzewo binarne jest BST czy nie?
34) napisać program Java do liczenia węzłów liści w drzewie binarnym? (rozwiązanie)
35) napisać program Java, aby znaleźć wysokość lub głębokość drzewa binarnego? (rozwiązanie)
36) Jak sprawdzić, czy dwa podane drzewa binarne są takie same? (rozwiązanie)
napisz metodę w Javie, która zaakceptuje dwa drzewa binarne i zwróci true, jeśli są takie same, w przeciwnym razie zwróci false.
37) Jak usunąć dany węzeł z binarnego drzewa wyszukiwania w Javie? (rozwiązanie)
38) napisać funkcję Java, aby dodać dany węzeł w binarnym drzewie wyszukiwania? (rozwiązanie)
39) Drukowanie drzewa binarnego w kolejności pionowej w Javie? (rozwiązanie)
40) co to jest czerwono-czarna struktura danych drzewa? (answer)
Answer – Red-Black Tree to samobalansujące się binarne drzewo wyszukiwania (BST), w którym każdy węzeł ma następujące właściwości
a) każdy węzeł ma kolor, czerwony lub czarny.
b) korzeń drzewa jest zawsze Czarny.
c) nie ma dwóch sąsiednich czerwonych węzłów (czerwony węzeł nie może mieć czerwonego rodzica ani czerwonego dziecka).
D) każda ścieżka od węzła głównego do węzła zerowego ma taką samą liczbę czarnych węzłów.
Możesz również sprawdzić struktury danych w Java: kurs odświeżający rozmowę kwalifikacyjną na Educative, aby dowiedzieć się więcej o strukturze danych Red Black Tree.
to wszystko na tej liście 40 najlepszych drzew binarnych i binarnych problemów z kodowaniem opartych na drzewie wyszukiwania z wywiadów programistycznych. Chociaż rozwiązanie jest podane w języku programowania Java, możesz rozwiązać te pytania na dowolnym języku programowania, takim jak Python, C, C++, JavaScript, Ruby, a nawet Swift. Możesz również opublikować swoje rozwiązanie w sekcji komentarzy, aby społeczność mogła je przejrzeć i przekazać przydatne informacje zwrotne.
Wszystkiego najlepszego na rozmowę kwalifikacyjną.
Dalsza Nauka
11 Podstawowych Pytań Kwalifikacyjnych.
opanuj rozmowę o kodowaniu: struktury danych + algorytmy
opanuj rozmowę o kodowaniu: Wzorce do kodowania pytań
inne pytania do kodowania wywiadów L może Ci się spodobać
- jak zaimplementować algorytm sortowania wstawiania w Javie? (tutorial)
- jak zastosować algorytm Quicksort w Javie? (tutorial)
- jak zaimplementować algorytm sortowania bąbelkowego w Javie? (tutorial)
- różnica między algorytmem sortowania opartym na Porównaniu i nie opartym na porównaniu?
- jak zastosować sortowanie kubełkowe w Javie? (tutorial)
- jak zaimplementować algorytm Quicksort bez rekurencji? (tutorial)
- jak wykonać binarny algorytm wyszukiwania w Javie? (tutorial)
- jak znaleźć wszystkie pary w tablicy, której suma jest równa k (rozwiązanie)
- jak usunąć duplikaty z tablicy w Javie? (rozwiązanie)
- jak znaleźć najbardziej znaczącą i najmniejszą liczbę w tablicy bez sortowania? (rozwiązanie)
- jak znaleźć duplikaty z nieposortowanej tablicy w Javie? (rozwiązanie)
- jak znaleźć jedną brakującą liczbę w posortowanej tablicy? (rozwiązanie)
- jak znaleźć brakującą wartość z tablicy zawierającej od 1 do 100? (rozwiązanie)
- 50+ Struktura danych i algorytmy problemy z wywiadów (pytania)
- Moje Ulubione Darmowe kursy do dogłębnej nauki struktury danych (FreeCodeCamp)
- jak usunąć element z tablicy w Javie? (rozwiązanie)
- Jak sprawdzić, czy tablica zawiera określoną wartość? (rozwiązanie)
- 10 Bezpłatne kursy struktury danych i algorytmów dla programistów (kursy)
- 100 + problemy z kodowaniem struktury danych z wywiadów (pytania)
Dziękujemy za przeczytanie tego artykułu. Jeśli podoba ci się ten artykuł, podziel się nim z przyjaciółmi i współpracownikami. Jeśli masz jakieś pytania lub uwagi, a następnie upuść notatkę.
P. S. – Jeśli szukasz darmowych kursów algorytmów, aby poprawić zrozumienie struktury danych i algorytmów, powinieneś również sprawdzić łatwy do zaawansowanego kurs struktur danych na Udemy. Jest on napisany przez inżyniera oprogramowania Google i eksperta od algorytmów i jest całkowicie bezpłatny.