Implementieren eines Binärbaums in Java

1. Einleitung

In diesem Artikel behandeln wir die Implementierung eines Binärbaums in Java.

Für diesen Artikel verwenden wir einen sortierten Binärbaum, der int- Werte enthält .

2. Binärer Baum

Ein Binärbaum ist eine rekursive Datenstruktur, bei der jeder Knoten höchstens zwei untergeordnete Knoten haben kann.

Ein üblicher Typ eines Binärbaums ist ein binärer Suchbaum, in dem jeder Knoten einen Wert hat, der größer oder gleich den Knotenwerten im linken Unterbaum und kleiner oder gleich den Knotenwerten im rechten Unterbaum ist Baum.

Hier ist eine schnelle visuelle Darstellung dieser Art von Binärbaum:

Für die Implementierung verwenden wir eine Hilfsknotenklasse , die int- Werte speichert und einen Verweis auf jedes untergeordnete Element enthält:

class Node { int value; Node left; Node right; Node(int value) { this.value = value; right = null; left = null; } }

Fügen wir dann den Startknoten unseres Baums hinzu, der normalerweise als root bezeichnet wird:

public class BinaryTree { Node root; // ... }

3. Gemeinsame Operationen

Lassen Sie uns nun die häufigsten Operationen sehen, die wir für einen Binärbaum ausführen können.

3.1. Elemente einfügen

Die erste Operation, die wir behandeln werden, ist das Einfügen neuer Knoten.

Zuerst müssen wir die Stelle finden, an der wir einen neuen Knoten hinzufügen möchten, um den Baum sortiert zu halten . Wir werden diese Regeln ab dem Wurzelknoten befolgen:

  • Wenn der Wert des neuen Knotens niedriger als der des aktuellen Knotens ist, gehen wir zum linken Kind
  • Wenn der Wert des neuen Knotens größer als der des aktuellen Knotens ist, gehen wir zum richtigen untergeordneten Knoten
  • Wenn der aktuelle Knoten null ist, haben wir einen Blattknoten erreicht und können den neuen Knoten an dieser Position einfügen

Zuerst erstellen wir eine rekursive Methode zum Einfügen:

private Node addRecursive(Node current, int value) { if (current == null) { return new Node(value); } if (value  current.value) { current.right = addRecursive(current.right, value); } else { // value already exists return current; } return current; }

Als nächstes werden wir die öffentliche Methode erstellen, die die Rekursion von der beginnt Wurzelknoten:

public void add(int value) { root = addRecursive(root, value); }

Nun wollen wir sehen, wie wir diese Methode verwenden können, um den Baum aus unserem Beispiel zu erstellen:

private BinaryTree createBinaryTree() { BinaryTree bt = new BinaryTree(); bt.add(6); bt.add(4); bt.add(8); bt.add(3); bt.add(5); bt.add(7); bt.add(9); return bt; }

3.2. Ein Element finden

Fügen wir nun eine Methode hinzu, um zu überprüfen, ob der Baum einen bestimmten Wert enthält.

Nach wie vor erstellen wir zunächst eine rekursive Methode, die den Baum durchläuft:

private boolean containsNodeRecursive(Node current, int value) { if (current == null) { return false; } if (value == current.value) { return true; } return value < current.value ? containsNodeRecursive(current.left, value) : containsNodeRecursive(current.right, value); }

Hier suchen wir nach dem Wert, indem wir ihn mit dem Wert im aktuellen Knoten vergleichen und dann je nach Bedarf im linken oder rechten untergeordneten Element fortfahren.

Als nächstes erstellen wir die öffentliche Methode, die vom Stamm ausgeht :

public boolean containsNode(int value) { return containsNodeRecursive(root, value); }

Erstellen wir nun einen einfachen Test, um zu überprüfen, ob der Baum wirklich die eingefügten Elemente enthält:

@Test public void givenABinaryTree_WhenAddingElements_ThenTreeContainsThoseElements() { BinaryTree bt = createBinaryTree(); assertTrue(bt.containsNode(6)); assertTrue(bt.containsNode(4)); assertFalse(bt.containsNode(1)); }

Alle hinzugefügten Knoten sollten im Baum enthalten sein.

3.3. Ein Element löschen

Eine weitere häufige Operation ist das Löschen eines Knotens aus dem Baum.

Zuerst müssen wir den zu löschenden Knoten auf ähnliche Weise wie zuvor finden:

private Node deleteRecursive(Node current, int value) { if (current == null) { return null; } if (value == current.value) { // Node to delete found // ... code to delete the node will go here } if (value < current.value) { current.left = deleteRecursive(current.left, value); return current; } current.right = deleteRecursive(current.right, value); return current; }

Sobald wir den zu löschenden Knoten gefunden haben, gibt es drei verschiedene Hauptfälle:

  • Ein Knoten hat keine Kinder - dies ist der einfachste Fall. Wir müssen diesen Knoten nur durch null in seinem übergeordneten Knoten ersetzen
  • Ein Knoten hat genau ein Kind - im übergeordneten Knoten ersetzen wir diesen Knoten durch sein einziges Kind.
  • Ein Knoten hat zwei untergeordnete Knoten. Dies ist der komplexeste Fall, da eine Baumreorganisation erforderlich ist

Mal sehen, wie wir den ersten Fall implementieren können, wenn der Knoten ein Blattknoten ist:

if (current.left == null && current.right == null) { return null; }

Fahren wir nun mit dem Fall fort, in dem der Knoten ein untergeordnetes Element hat:

if (current.right == null) { return current.left; } if (current.left == null) { return current.right; }

Hier geben wir das Nicht-Null- Kind zurück, damit es dem übergeordneten Knoten zugewiesen werden kann.

Schließlich müssen wir den Fall behandeln, in dem der Knoten zwei Kinder hat.

Zuerst müssen wir den Knoten finden, der den gelöschten Knoten ersetzt. Wir verwenden den kleinsten Knoten des zu löschenden Knotens im rechten Teilbaum:

private int findSmallestValue(Node root) { return root.left == null ? root.value : findSmallestValue(root.left); }

Dann weisen wir dem zu löschenden Knoten den kleinsten Wert zu und danach löschen wir ihn aus dem rechten Teilbaum:

int smallestValue = findSmallestValue(current.right); current.value = smallestValue; current.right = deleteRecursive(current.right, smallestValue); return current;

Zuletzt erstellen wir die öffentliche Methode, mit der das Löschen vom Stamm aus gestartet wird :

public void delete(int value) { root = deleteRecursive(root, value); }

Lassen Sie uns nun überprüfen, ob das Löschen wie erwartet funktioniert:

@Test public void givenABinaryTree_WhenDeletingElements_ThenTreeDoesNotContainThoseElements() { BinaryTree bt = createBinaryTree(); assertTrue(bt.containsNode(9)); bt.delete(9); assertFalse(bt.containsNode(9)); }

4. Den Baum durchqueren

In diesem Abschnitt werden verschiedene Möglichkeiten zum Durchlaufen eines Baums beschrieben, wobei die Suche nach Tiefe und Breite im Detail ausführlich behandelt wird.

Wir verwenden denselben Baum, den wir zuvor verwendet haben, und zeigen die Durchlaufreihenfolge für jeden Fall an.

4.1. Tiefensuche

Die Tiefensuche ist eine Art von Durchquerung, die bei jedem Kind so tief wie möglich geht, bevor das nächste Geschwister erforscht wird.

Es gibt verschiedene Möglichkeiten, eine Tiefensuche durchzuführen: In-Order, Pre-Order und Post-Order.

Die In-Order-Durchquerung besteht darin, zuerst den linken Unterbaum, dann den Wurzelknoten und schließlich den rechten Unterbaum zu besuchen:

public void traverseInOrder(Node node) { if (node != null) { traverseInOrder(node.left); System.out.print(" " + node.value); traverseInOrder(node.right); } }

Wenn wir diese Methode aufrufen, zeigt die Konsolenausgabe die Durchquerung in der angegebenen Reihenfolge:

3 4 5 6 7 8 9

Durchlaufen der Vorbestellung besucht zuerst den Wurzelknoten, dann den linken Teilbaum und schließlich den rechten Teilbaum:

public void traversePreOrder(Node node) { if (node != null) { System.out.print(" " + node.value); traversePreOrder(node.left); traversePreOrder(node.right); } }

Und überprüfen wir die Vorbestellungsdurchquerung in der Konsolenausgabe:

6 4 3 5 8 7 9

Die Nachbestellungsdurchquerung besucht den linken Teilbaum, den rechten Teilbaum und den Wurzelknoten am Ende:

public void traversePostOrder(Node node) { if (node != null) { traversePostOrder(node.left); traversePostOrder(node.right); System.out.print(" " + node.value); } }

Hier sind die Knoten in der Nachbestellung:

3 5 4 7 9 8 6

4.2. Breitensuche

Dies ist eine weitere häufige Art der Durchquerung, bei der alle Knoten einer Ebene besucht werden, bevor zur nächsten Ebene gewechselt wird .

Diese Art der Durchquerung wird auch als Ebenenreihenfolge bezeichnet und besucht alle Ebenen des Baums von der Wurzel aus und von links nach rechts.

Für die Implementierung verwenden wir eine Warteschlange , um die Knoten von jeder Ebene der Reihe nach zu halten. Wir extrahieren jeden Knoten aus der Liste, drucken seine Werte aus und fügen seine untergeordneten Elemente der Warteschlange hinzu:

public void traverseLevelOrder() { if (root == null) { return; } Queue nodes = new LinkedList(); nodes.add(root); while (!nodes.isEmpty()) { Node node = nodes.remove(); System.out.print(" " + node.value); if (node.left != null) { nodes.add(node.left); } if (node.right != null) { nodes.add(node.right); } } }

In diesem Fall lautet die Reihenfolge der Knoten:

6 4 8 3 5 7 9

5. Schlussfolgerung

In diesem Artikel haben wir gesehen, wie ein sortierter Binärbaum in Java und seinen häufigsten Operationen implementiert wird.

Der vollständige Quellcode für die Beispiele ist auf GitHub verfügbar.