Implementierung eines binären Suchbaums

Einführung

In diesem Lab werden wir lernen, wie man einen binären Suchbaum in Java implementiert. Ein binärer Suchbaum ist eine binäre Baumdatenstruktur, bei der der Wert jedes Knotens größer oder gleich den Werten in seinem linken Teilbaum und kleiner oder gleich den Werten in seinem rechten Teilbaum ist.

Skills Graph

Erstellen der Klasse BSTNode

Zunächst erstellen wir eine Java-Klasse, die einen Knoten eines binären Suchbaums darstellt, und nennen sie BSTNode. Ein Knoten in einem binären Suchbaum sollte einen Wert und zwei Kindknoten haben - einen links und einen rechts.

class BSTNode {
    int value;
    BSTNode leftChild;
    BSTNode rightChild;

    BSTNode(int val) {
        this.value = val;
        this.leftChild = null;
        this.rightChild = null;
    }
}

Einfügen von Elementen in den binären Suchbaum

Um Elemente in den binären Suchbaum einzufügen, folgen wir dem folgenden Algorithmus:

• Wenn der neue Wert kleiner als der aktuelle Knotenwert ist, dann rekursiv zum linken Kindknoten gehen.
• Wenn der neue Wert größer als der aktuelle Knotenwert ist, dann rekursiv zum rechten Kindknoten gehen.
• Wenn der aktuelle Knoten null ist, dann füge den neuen Wert an dieser Position hinzu.

public static BSTNode insert(int value, BSTNode current) {
    if (current == null) {
        BSTNode newNode = new BSTNode(value);
        return newNode;
    } else {
        if (value < current.value)
            current.leftChild = insert(value, current.leftChild);
        else
            current.rightChild = insert(value, current.rightChild);
    }
    return current;
}

Um diese Methode zu testen, erstellen wir den binären Suchbaum und fügen einige Elemente ein:

public static void main(String[] args) {
    BSTNode root = new BSTNode(12);
    root = insert(7, root);
    root = insert(20, root);
    root = insert(5, root);
    root = insert(9, root);
    root = insert(21, root);

    // Drucken Sie den Baum aus, um die Einfügung zu überprüfen
    System.out.println("Durchlauf nach der Einfügung: ");
    inorderTraversal(root);
}

// Funktion, um den Baum inorder zu traversieren
public static void inorderTraversal(BSTNode current) {
    if (current == null)
        return;
    inorderTraversal(current.leftChild);
    System.out.print(current.value + " ");
    inorderTraversal(current.rightChild);
}

Ausgabe:

Durchlauf nach der Einfügung:
5 7 9 12 20 21

Suchen nach einem Element im binären Suchbaum

Um nach einem Element im binären Suchbaum zu suchen, folgen wir dem folgenden Algorithmus:

• Wenn der Wert des aktuellen Knotens mit dem Wert übereinstimmt, den wir finden möchten, dann geben wir true zurück.
• Wenn der Wert des aktuellen Knotens größer als der Wert ist, den wir finden möchten, dann rekursiv zum linken Kindknoten gehen.
• Wenn der Wert des aktuellen Knotens kleiner als der Wert ist, den wir finden möchten, dann rekursiv zum rechten Kindknoten gehen.
• Wenn der aktuelle Knoten null ist, dann geben wir false zurück.

public static boolean search(int key, BSTNode current) {
    if (current == null)
        return false;
    if (current.value == key)
        return true;
    else {
        if (key < current.value)
            return search(key, current.leftChild);
        else
            return search(key, current.rightChild);
    }
}

Um diese Methode zu testen, suchen wir nach einigen Elementen:

public static void main(String[] args) {
    BSTNode root = new BSTNode(12);
    root = insert(7, root);
    root = insert(20, root);
    root = insert(5, root);
    root = insert(9, root);
    root = insert(21, root);

    // Suchen Sie nach Elementen
    System.out.println(search(7, root));
    System.out.println(search(9, root));
    System.out.println(search(17, root));
}

Ausgabe:

true
true
false

Löschen eines Elements aus einem binären Suchbaum

Das Löschen eines Elements aus einem binären Suchbaum ist etwas komplexer als die vorherigen Schritte, da wir verschiedene Fälle abhandeln müssen, je nachdem, welchen Typ der Knoten hat:

• Wenn der Knoten keine Kinder hat (ein Blattknoten), entfernen wir ihn einfach.
• Wenn der Knoten nur ein Kind hat, ersetzen wir ihn durch sein einziges Kind.
• Wenn der Knoten zwei Kinder hat, ersetzen wir ihn durch den kleinsten Wert aus dem rechten Teilbaum oder den größten Wert aus dem linken Teilbaum.

public static BSTNode delete(int value, BSTNode current) {
    if (current == null)
        return current;
    if (value < current.value)
        current.leftChild = delete(value, current.leftChild);
    else if (value > current.value)
        current.rightChild = delete(value, current.rightChild);
    else if (value == current.value) {
        if (current.leftChild!= null && current.rightChild!= null) {
            int min = current.rightChild.value;
            BSTNode temp = current.rightChild;
            while (temp.leftChild!= null) {
                min = temp.leftChild.value;
                temp = temp.leftChild;
            }
            current.value = min;
            current.rightChild = delete(min, current.rightChild);
        } else if (current.leftChild == null)
            return current.rightChild;
        else if (current.rightChild == null)
            return current.leftChild;
    }
    return current;
}

Um diese Methode zu testen, löschen wir einige Knoten und drucken den Baum aus:

public static void main(String[] args) {
    BSTNode root = new BSTNode(12);
    root = insert(7, root);
    root = insert(20, root);
    root = insert(5, root);
    root = insert(9, root);
    root = insert(21, root);

    // Löschen Sie einige Knoten
    root = delete(12, root);
    root = delete(20, root);
    root = delete(9, root);

    // Drucken Sie den Baum aus, um die Löschung zu überprüfen
    System.out.println("Durchlauf nach der Löschung: ");
    inorderTraversal(root);
}

Ausgabe:

Durchlauf nach der Löschung:
5 7 21

Durchlaufen des binären Suchbaums

Wir können einen binären Suchbaum auf verschiedene Weise durchlaufen:

• Inorder-Durchlauf (Links-Knoten-Rechts)
• Preorder-Durchlauf (Knoten-Links-Rechts)
• Postorder-Durchlauf (Links-Rechts-Knoten)
• Level-order-Durchlauf (BFS)

public static void inorderTraversal(BSTNode current) {
    if (current == null)
        return;
    inorderTraversal(current.leftChild);
    System.out.print(current.value + " ");
    inorderTraversal(current.rightChild);
}

public static void preorderTraversal(BSTNode current) {
    if (current == null)
        return;
    System.out.print(current.value + " ");
    preorderTraversal(current.leftChild);
    preorderTraversal(current.rightChild);
}

public static void postorderTraversal(BSTNode current) {
    if (current == null)
        return;
    postorderTraversal(current.leftChild);
    postorderTraversal(current.rightChild);
    System.out.print(current.value + " ");
}

public static void levelOrderTraversal(BSTNode root) {
    Queue<BSTNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        BSTNode temp = queue.poll();
        System.out.print(temp.value + " ");
        if (temp.leftChild!= null)
            queue.add(temp.leftChild);
        if (temp.rightChild!= null)
            queue.add(temp.rightChild);
    }
}

Um diese Methoden zu testen, drucken wir den Baum mit jeder Durchlauf-Technik:

public static void main(String[] args) {
    BSTNode root = new BSTNode(12);
    root = insert(7, root);
    root = insert(20, root);
    root = insert(5, root);
    root = insert(9, root);
    root = insert(21, root);

    System.out.print("Inorder-Durchlauf: ");
    inorderTraversal(root);
    System.out.print("\nPreorder-Durchlauf: ");
    preorderTraversal(root);
    System.out.print("\nPostorder-Durchlauf: ");
    postorderTraversal(root);
    System.out.print("\nLevel-order-Durchlauf: ");
    levelOrderTraversal(root);
}

Ausgabe:

Inorder-Durchlauf: 5 7 9 12 20 21
Preorder-Durchlauf: 12 7 5 9 20 21
Postorder-Durchlauf: 5 9 7 21 20 12
Level-order-Durchlauf: 12 7 20 5 9 21

Zusammenfassung

In diesem Lab haben wir gelernt, wie man in Java einen binären Suchbaum erstellt, Elemente einfügt, nach einem Element sucht, ein Element löscht und durchläuft.

Wir haben zunächst die BSTNode-Klasse erstellt, die einen Knoten im binären Suchbaum repräsentiert. Anschließend haben wir die Einfüge-, Such- und Löschfunktionalitäten mit Hilfe von Algorithmen implementiert, die speziell für binäre Suchbäume sind. Schließlich haben wir gelernt, wie man den binären Suchbaum mit verschiedenen Durchlauf-Techniken wie Inorder-, Preorder-, Postorder- und Level-order-Durchlauf durchläuft.

Mit diesen Begriffen sollten Sie in der Lage sein, binäre Suchbäume in Ihren eigenen Java-Programmen zu implementieren.