Viele Programmierer und meine Leser haben mich gebeten, einige Fragen zur binärbaumbasierten Codierung zu stellen, genau wie ich es für getan habe das Array, die verknüpfte Liste, die Zeichenfolge, das Softwaredesign, die Muster, die Hash-Tabelle und die Datenstruktur im Allgemeinen. Diese Aufgabe stand tatsächlich einige Zeit an und es steckte fest, als ich versuchte, die Lösung für jede einzelne Frage zu finden, die ich hätte sammeln können. Daher habe ich beschlossen, die Liste der Interviewfragen für Binärbäume jetzt zu veröffentlichen und die Lösung möglicherweise später als separaten Artikel zu veröffentlichen. Dies ist wie das Erstellen einer Schnittstelle und das spätere Bereitstellen einer Implementierung, damit Sie andere Personen, die von Ihrer Schnittstelle abhängig sind, nicht blockieren (tatsächlich ist dies ein Vorteil der Verwendung der Schnittstelle in Java oder einer anderen Programmiersprache).
Was ist eine Binärbaum-Datenstruktur?
Um auf einen Binärbaum zurückzukommen, möchte ich einige der nützlichen Punkte zur Baumdatenstruktur im Allgemeinen wiederholen, die Ihnen helfen, diese Fragen selbst zu lösen:
1) Ein Baum ist die hierarchische Datenstruktur im Gegensatz zu einem Array oder einer verknüpften Liste, die linear sind. Dies bedeutet, dass Sie hierarchische Informationen mithilfe einer Baumdatenstruktur wie einer Organisationsstruktur, einem Stammbaum usw. speichern können.
2) Ein Baum hat Knoten und Kinder. Der oberste oder erste Knoten wird als Wurzel bezeichnet.
3) Wenn Sie visualisieren möchten, ist die Baumdatenstruktur wie ein invertierter Baum in der realen Welt. Ich meine, wenn Sie Bäume um Sich herum sehen, sind ihre Wurzeln unten, aber wenn Sie eine Baumdatenstruktur in der Programmierung oder Informatik zeichnen, ist ihre Wurzel oben.
4) Ein Binärbaum ist ein spezieller Baum, in dem Sie höchstens zwei Kinder haben können. Dies bedeutet, dass ein Knoten entweder kein Kind, ein Kind oder zwei Kinder haben kann. Sie können nicht drei oder mehr Kinder haben.
5) Alle Knoten, die keine Kinder haben, werden als Blattknoten bezeichnet.
6) Binary Search Tree ist eine spezielle Art von Binärbaum, bei dem die Werte der linken Teilbäume kleiner oder gleich root und die Werte der Knoten in den rechten Teilbäumen größer oder gleich root . Dies bietet eine Sortierstruktur für einen binären Suchbaum, der die Suche sehr schnell macht.
Sie können auch Datenstrukturen und Algorithmen überprüfen: Deep Dive mit Java-Kurs auf Udemy, um mehr über binäre Suchbäume zu erfahren. Es ist einer der besten Kurse, um Ihre Datenstruktur und Algorithmen Fähigkeiten zu aktualisieren.
7) Der binäre Suchbaum ist eng mit einer binären Suche verbunden, die nach dem Prinzip arbeitet, die Eingabegröße nach jeder Iteration auf die Hälfte zu reduzieren. Dies macht die Suche sehr schnell und Sie können jedes Element im binären Suchbaum zur O (logN) -Zeit finden, aber nur, wenn der Baum ausgeglichen ist.
8) Es gibt zwei Möglichkeiten, eine Baumdatenstruktur zu durchlaufen: Tiefe zuerst oder Ebene zuerst. In der Tiefe – Zuerst gehen Sie nach unten, bis kein Knoten mehr zu besuchen ist, und dann kehren Sie zurück, um Knoten auf derselben Ebene zu besuchen.
Beim Durchlaufen der Ebenenreihenfolge besuchen Sie alle Knoten auf derselben Ebene, bevor Sie zur nächsten Ebene wechseln. Es gibt auch Vorbestellungs-, Nachbestellungs- und In-Order-Traversal für Binärdateien, mit denen Knoten eines Binärbaums durchlaufen werden. Inorder Traversal ist besonders, weil es alle Knoten in sortierter Reihenfolge besucht.
9) Ein ausgeglichener Binärbaum ist wie eine gleiche Anzahl von Knoten in jedem Teilbaum Wenn Sie alle Knoten im einzigen linken oder rechten Teilbaum haben, wird Ihr Binärbaum unausgewogen und verhält sich wie eine verknüpfte Liste, wie im Diagramm unten gezeigt:
10) Ein unsymmetrischer oder unsymmetrischer binärer Suchbaum verhält sich wie eine verknüpfte Liste, bei der eine Suche O (n) Zeit im Gegensatz zu O (logN) Zeit in einem ausgeglichenen binären Suchbaum benötigt.
Dies sind einige der wichtigen Punkte, die jeder Programmierer über die Binärbaum-Datenstruktur wissen sollte. Es wird Ihnen helfen, Baum-basierte Codierung Probleme zu lösen. Wenn Sie mehr über den Binärbaum und andere Datenstrukturen erfahren möchten, empfehle ich Ihnen, an einem guten Datenstruktur- und Algorithmuskurs wie Data Structures and Algorithms: Deep Dive Using Java on Udemy teilzunehmen, um Ihre Grundlagen zu verbessern.
40+ Binary Tree Interview Fragen für Java-Programmierer
Ohne mehr Zeit zu verschwenden, hier ist meine Liste der binären Baum und Binary Search Tree (BST) basierte Codierung Probleme von der Programmierung Vorstellungsgespräche. Ich habe mit der Lösung verlinkt, wo immer es möglich ist, aber wenn es keinen Link gibt, können Sie auch eine Lösung finden, indem Sie einfach eine Google-Suche durchführen. Sie sind sehr beliebte Fragen und viele Leute haben sie bereits gelöst.
Um das Beste aus dieser Liste herauszuholen, versuchen Sie, das Problem zu lösen, bevor Sie sich mit der Lösung befassen. Wenn Sie sich die Lösung sofort ansehen, werden Sie nur 10% lernen, aber wenn Sie es versuchen, werden Sie 80 bis 90% der Konzepte und Tricks hinter jeder Frage lernen.
1) Wie finden Sie den kleinsten gemeinsamen Vorfahren eines Binärbaums in Java? (lösung)
2) Wie drucken Sie die linke Ansicht eines Binärbaums in Java? (lösung)
3) Schreiben Sie ein Programm zum Erstellen eines Baums aus Inorder- und PreOrder-Traversal in Java? (lösung)
4) Wie drucken Sie gemeinsame Knoten in zwei binären Suchbäumen in Java? (lösung)
5) Warum ist der binäre Heap eine bessere Wahl als BST für die Implementierung der Prioritätswarteschlange? (antwort)
6) Wie überprüfen Sie, ob ein bestimmter Binärbaum ausgeglichen ist oder nicht? Schreiben Sie eine Java-Methode, die einen Binärbaum akzeptiert und true zurückgibt, wenn er ausgeglichen ist, oder false. (Lösung)
7) Was sind einige Vorteile eines binären Suchbaums gegenüber einer Hashtabellendatenstruktur? (antwort)
8) Wie überprüfen Sie, ob ein bestimmter Binärbaum ein Teilbaum eines anderen Binärbaums ist? (lösung)
Sie haben zwei Binärbäume angegeben und müssen true zurückgeben, wenn ein erster Binärbaum ein Teilbaum des zweiten ist. Ein Teilbaum des Binärbaums BT ist ein Baum T, der aus einem Knoten von BT und allen seinen Nachkommen besteht. Im folgenden Fall ist T1 beispielsweise ein Teilbaum des Binärbaums BT
9) Wie finden Sie den Abstand zwischen zwei Knoten in einem Binärbaum? (Lösung)
10) Wie finde ich den kleinsten gemeinsamen Vorfahren in einem Binärbaum in Java? (lösung)
11) Schreiben Sie ein Java-Programm, um zu überprüfen, ob sich alle Blätter eines bestimmten Binärbaums auf derselben Ebene befinden? (lösung)
12) Wie konvertiert man einen gegebenen Binärbaum in eine doppelt verknüpfte Liste in Java? (lösung)
13) Schreiben Sie ein Programm, um eine Tiefe eines bestimmten Binärbaums in Java zu finden? (lösung)
14) Was ist der Unterschied zwischen binären und binären Suchbäumen? (antwort)
15) Was ist ein selbstbalancierter Baum? (antwort)
16) Was ist der AVL-Baum? (antwort)
17) Schreiben Sie ein Java-Programm, um das Durchlaufen eines binären Suchbaums vor der Bestellung zu drucken? Geben Sie eine Lösung mit Iteration und Rekursion? (lösung)
18) Drucken Sie die Nachbestellung von BST? Geben Sie einen iterativen und rekursiven Algorithmus an (Lösung)
19) Drucken Sie die Inorder-Durchquerung eines BST in Java? Geben Sie sowohl iterative als auch rekursive Algorithmen an (Lösung)
20) Sie haben eine BST angegeben, bei der zwei Knoten ausgetauscht werden? Wie stellen Sie die ursprüngliche BST wieder her? (lösung)
21) Wie konvertiert man einen Binärbaum in einen binären Suchbaum in Java? (lösung)
22) Finden Sie den größten BST-Teilbaum eines bestimmten Binärbaums in Java? (lösung)
23) Schreiben Sie ein Java-Programm, um Knoten auf derselben Ebene wie einen Binärbaum zu verbinden? (lösung)
24) Was ist eine Trie-Datenstruktur? (antwort)
25) Was ist der Unterschied zwischen dem Binärbaum und Trie? (antwort)
26) Vorfahren eines bestimmten Knotens eines Binärbaums in Java drucken? (lösung)
27) Schreiben Sie ein Java-Programm, um die Ebene eines bestimmten Knotens in einem Binärbaum zu drucken? (lösung)
28) Gemeinsame Knoten zweier gegebener BST in Java drucken? (lösung)
29) Geben Sie einen Binärbaum an, drucken Sie alle Wurzel-zu-Blatt-Pfade in Java? (lösung)
30) Inorder tree Traversal ohne Rekursion in Java drucken? (lösung)
31) PreOrder Tree Traversal ohne Rekursion und Stack in Java drucken? (lösung)
32) PostOrder Tree Traversal ohne Rekursion in Java drucken? (Lösung)
33) Java-Programm, um zu überprüfen, ob ein bestimmter Binärbaum BST ist oder nicht? (lösung)
34) Schreiben Sie ein Java-Programm, um Blattknoten in einem Binärbaum zu zählen? (lösung)
35) Schreiben Sie ein Java-Programm, um die Höhe oder Tiefe eines Binärbaums zu ermitteln? (lösung)
36) Wie finden Sie heraus, ob zwei gegebene Binärbäume gleich sind? (lösung)
Schreiben Sie eine Methode in Java, die zwei Binärbäume akzeptiert und true zurückgibt, wenn sie identisch sind, andernfalls false .
37) Wie löscht man einen bestimmten Knoten aus einem binären Suchbaum in Java? (lösung)
38) Schreiben Sie eine Java-Funktion, um einen bestimmten Knoten in einem binären Suchbaum hinzuzufügen? (lösung)
39) Drucken Sie einen Binärbaum in vertikaler Reihenfolge in Java? (lösung)
40) Was ist die rot-schwarze Baumdatenstruktur? (Antwort)
Antwort – Rot-Schwarz-Baum ist ein selbstausgleichender binärer Suchbaum (BST), bei dem jeder Knoten die folgenden Eigenschaften hat
a) Jeder Knoten hat eine Farbe, entweder rot oder schwarz.
b) Die Wurzel des Baumes ist immer schwarz.
c) Es gibt keine zwei benachbarten roten Knoten (Ein roter Knoten kann kein rotes übergeordnetes oder rotes untergeordnetes Element haben).
d) Jeder Pfad von der Wurzel zu einem Nullknoten hat die gleiche Anzahl schwarzer Knoten.
Sie können auch Datenstrukturen in Java überprüfen: Ein Interview Auffrischungskurs auf Educative, um mehr über Red Black Tree Datenstruktur zu erfahren.
Das ist alles in dieser Liste der Top 40 Binary Trees und Binary Search Tree based Coding Probleme von Programming Interviews. Obwohl die Lösung in der Programmiersprache Java gegeben ist, können Sie diese Fragen gerne in jeder Programmiersprache Ihrer Wahl wie Python, C, C ++, JavaScript, Ruby oder sogar Swift lösen. Sie können Ihre Lösung auch im Kommentarbereich veröffentlichen, damit die Community Ihre Lösung überprüfen und nützliches Feedback geben kann.
Alles Gute für Ihr Coding-Interview.
Weiteres Lernen
11 wesentliche Fragen zum Codierungsinterview.
Master das Coding Interview: Datenstrukturen + Algorithmen
Grokking das Coding Interview: Muster für Codierungsfragen
Andere Codierungsinterview-Fragen, die Ihnen gefallen könnten
- Wie implementiere ich den Einfügesortieralgorithmus in Java? (tutorial)
- Wie wende ich den Quicksort-Algorithmus in Java an? (tutorial)
- Wie implementiere ich den Blasensortieralgorithmus in Java? (tutorial)
- Unterschied zwischen Vergleich und nicht vergleichsbasiertem Sortieralgorithmus? (antwort)
- Wie wende ich die Bucket-Sortierung in Java an? (tutorial)
- Wie implementiere ich den Quicksort-Algorithmus ohne Rekursion? (tutorial)
- Wie führe ich einen binären Suchalgorithmus in Java aus? (tutorial)
- So finden Sie alle Paare in einem Array, dessen Summe gleich k ist (Lösung)
- Wie entferne ich Duplikate aus einem Array in Java? (Lösung)
- Wie finde ich die signifikanteste und kleinste Zahl in einem Array ohne zu sortieren? (Lösung)
- Wie finde ich Duplikate aus einem unsortierten Array in Java? (lösung)
- Wie finde ich eine fehlende Zahl in einem sortierten Array? (lösung)
- Wie finde ich einen fehlenden Wert aus einem Array mit 1 bis 100? (lösung)
- 50+ Datenstruktur- und Algorithmenprobleme aus Interviews (Fragen)
- Meine bevorzugten kostenlosen Kurse zum eingehenden Erlernen der Datenstruktur (FreeCodeCamp)
- Wie entferne ich ein Element aus einem Array in Java? (lösung)
- Wie überprüfe ich, ob ein Array einen bestimmten Wert enthält? (lösung)
- 10 kostenlose Datenstruktur- und Algorithmuskurse für Programmierer (Kurse)
- 100 Datenstrukturcodierungsprobleme aus Interviews (Fragen)
Vielen Dank für das Lesen dieses Artikels. Wenn Ihnen dieser Artikel gefällt, teilen Sie ihn bitte mit Ihren Freunden und Kollegen. Wenn Sie Fragen oder Feedback haben, schreiben Sie uns bitte eine Nachricht.
P. S. – Wenn Sie nach kostenlosen Algorithmenkursen suchen, um Ihr Verständnis von Datenstruktur und Algorithmen zu verbessern, sollten Sie auch den Kurs Easy to Advanced Data Structures auf Udemy besuchen. Es wurde von einem Google-Softwareentwickler und Algorithmus-Experten verfasst und ist völlig kostenlos.