Tiefensuche und Breitensuche: Navigieren von Binärbäumen in Java
Erfahre in diesem Java-Tutorial, wie Breadth-First Search und Depth-First Search zur effektiven Traversierung von Binärbäumen eingesetzt werden. Von der Erklärung der Algorithmen bis zur vollständigen Java-Implementierung – entdecke alles, was du für die erfolgreiche Navigation durch Binärbäume benötigst. Tauche ein und meistere die Kunst der Baumtraversierung mit Leichtigkeit!
Was ist Depth First Search (DFS)?
DFS beginnt an der Wurzel eines Baumes und erkundet dann jeden Ast, bevor es zurückschreitet. Diese Methode wird üblicherweise mit Stacks implementiert. Durch die Verwendung von Rekursion können wir von der Tatsache profitieren, dass linke und rechte Teilbäume ebenfalls Bäume sind und die gleichen Eigenschaften teilen.
Für Binärbäume gibt es drei Arten von DFS-Traversierungen:
- In-Order
- Pre-Order
- Post-Order
Was ist Breadth-First Search (BFS)?
BFS beginnt ebenfalls an der Wurzel und besucht dann alle Knoten schichtweise. Das bedeutet, dass es nach der Wurzel alle direkten Kinder der Wurzel durchläuft. Nachdem alle direkten Kinder durchlaufen sind, bewegt es sich zu deren Kindern und so weiter. Zur Implementierung von BFS verwenden wir eine Warteschlange.
Für Binärbäume haben wir die Level-Order-Traversierung, die BFS folgt.
Implementierung von BFS und DFS in Java
Die Struktur der TreeNode-Klasse ist wie folgt:
static class TreeNode {
int data;
TreeNode left, right;
public TreeNode(int key) {
data = key;
left = right = null;
}
}
1. Pre-Order Traversal
Die Pre-Order-Traversierung eines Binärbaumes durchläuft zuerst die Wurzel, dann den linken Teilbaum und schließlich den rechten Teilbaum. Dies geschieht rekursiv, um von der Tatsache zu profitieren, dass linke und rechte Teilbäume ebenfalls Bäume sind.
Der Algorithmus für die Pre-Order-Traversierung lautet:
- Durchlaufe die Wurzel.
- Rufe preorder() auf dem linken Teilbaum auf.
- Rufe preorder() auf dem rechten Teilbaum auf.
Die Pre-Order-Traversierung des oben genannten Baumes ist:
0 1 3 4 2
Die Java-Code-Implementierung sieht wie folgt aus:
static void preorder(TreeNode TreeNode) {
if (TreeNode == null)
return;
// Durchlaufe die Wurzel
System.out.print(TreeNode.data + " ");
// Durchlaufe links
preorder(TreeNode.left);
// Durchlaufe rechts
preorder(TreeNode.right);
}
2. In-Order Traversal
Die In-Order-Traversierung eines Binärbaumes durchläuft zuerst den linken Teilbaum, dann die Wurzel und schließlich den rechten Teilbaum.
Der Algorithmus für die In-Order-Traversierung lautet:
- Rufe inorder() auf dem linken Teilbaum auf.
- Durchlaufe die Wurzel.
- Rufe inorder() auf dem rechten Teilbaum auf.
Die In-Order-Traversierung des oben genannten Baumes ist:
3 1 4 0 2
Die Java-Code-Implementierung sieht wie folgt aus:
static void inorder(TreeNode TreeNode) {
if (TreeNode == null)
return;
// Durchlaufe links
inorder(TreeNode.left);
// Durchlaufe die Wurzel
System.out.print(TreeNode.data + " ");
// Durchlaufe rechts
inorder(TreeNode.right);
}
3. Post-Order Traversal
Die Post-Order-Traversierung eines Binärbaumes durchläuft zuerst den linken Teilbaum, dann den rechten Teilbaum und schließlich die Wurzel.
Der Algorithmus für die Post-Order-Traversierung lautet:
- Rufe postorder() auf dem linken Teilbaum auf.
- Rufe postorder() auf dem rechten Teilbaum auf.
- Durchlaufe die Wurzel.
Die Post-Order-Traversierung des oben genannten Baumes ist:
3 4 1 2 0
Die Java-Code-Implementierung sieht wie folgt aus:
static void postorder(TreeNode TreeNode) {
if (TreeNode == null)
return;
// Durchlaufe links
postorder(TreeNode.left);
// Durchlaufe rechts
postorder(TreeNode.right);
// Durchlaufe die Wurzel
System.out.print(TreeNode.data + " ");
}
4. Level-Order Traversal
Die Level-Order-Traversierung verwendet eine Warteschlange, um die zu besuchenden Knoten zu verfolgen. Nachdem ein Knoten besucht wurde, werden seine Kinder in die Warteschlange gestellt. Um einen neuen Knoten zum Durchlaufen zu erhalten, werden Elemente aus der Warteschlange entnommen.
Der Algorithmus lautet wie folgt:
- Initialisiere eine leere Warteschlange.
- Setze temp als Wurzel.
- Führe eine Schleife aus, solange die Warteschlange nicht leer ist:
- Gib Daten von temp aus.
- Füge temp’s Kinder in der Reihenfolge links und dann rechts in die Warteschlange ein.
- Nehme einen Knoten aus der Warteschlange und weise seinen Wert temp zu.
Die Level-Order-Traversierung des oben genannten Baumes ist:
0 1 2 3 4
Die Java-Code-Implementierung sieht wie folgt aus:
static void printLevelOrder(TreeNode root) {
Queue queue = new LinkedList();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode tempNode = queue.poll();
System.out.print(tempNode.data + " ");
/* Füge das linke Kind zur Warteschlange hinzu */
if (tempNode.left != null) {
queue.add(tempNode.left);
}
/* Füge das rechte Kind zur Warteschlange hinzu */
if (tempNode.right != null) {
queue.add(tempNode.right);
}
}
}
Vollständige Code-Implementierung von BFS und DFS in Java
Die vollständige Java-Code-Implementierung ist wie folgt:
package com.JournalDev;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static class TreeNode {
int data;
TreeNode left, right;
public TreeNode(int key) {
data = key;
left = right = null;
}
}
static void preorder(TreeNode TreeNode) {
if (TreeNode == null)
return;
// Durchlaufe die Wurzel
System.out.print(TreeNode.data + " ");
// Durchlaufe links
preorder(TreeNode.left);
// Durchlaufe rechts
preorder(TreeNode.right);
}
static void inorder(TreeNode TreeNode) {
if (TreeNode == null)
return;
// Durchlaufe links
inorder(TreeNode.left);
// Durchlaufe die Wurzel
System.out.print(TreeNode.data + " ");
// Durchlaufe rechts
inorder(TreeNode.right);
}
static void postorder(TreeNode TreeNode) {
if (TreeNode == null)
return;
// Durchlaufe links
postorder(TreeNode.left);
// Durchlaufe rechts
postorder(TreeNode.right);
// Durchlaufe die Wurzel
System.out.print(TreeNode.data + " ");
}
static void printLevelOrder(TreeNode root) {
Queue queue = new LinkedList();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode tempNode = queue.poll();
System.out.print(tempNode.data + " ");
/* Füge das linke Kind zur Warteschlange hinzu */
if (tempNode.left != null) {
queue.add(tempNode.left);
}
/* Füge das rechte Kind zur Warteschlange hinzu */
if (tempNode.right != null) {
queue.add(tempNode.right);
}
}
}
public static void main(String args[]) {
TreeNode root = new TreeNode(0);
root.left = new TreeNode(1);
root.right = new TreeNode(2);
root.left.left = new TreeNode(3);
root.left.right = new TreeNode(4);
System.out.println("Inorder Traversierung");
inorder(root);
System.out.println("\nPreorder Traversierung");
preorder(root);
System.out.println("\nPostorder Traversierung");
postorder(root);
System.out.println("\nLevelorder Traversierung");
printLevelOrder(root);
}
}
Fazit
Dieses Tutorial behandelte die BFS- und DFS-Traversierungen in Binärbäumen. Für die Implementierung von DFS in C++ verweisen wir auf dieses Tutorial. Für die C++-Implementierung der Level-Order-Traversierung verweisen wir auf dieses Tutorial.