Binärer Suchbaum von Grund auf in Java

Einführung
Ein binärer Suchbaum (BST) ist eine Art Binärbaum, bei dem jeder Knoten höchstens zwei untergeordnete Knoten hat, die als linkes und rechtes untergeordnetes Kind bezeichnet werden. Für jeden Knoten enthält der linke Teilbaum nur Knoten mit Werten, die kleiner als der Wert des Knotens sind, und der rechte Teilbaum enthält nur Knoten mit Werten, die größer als der Wert des Knotens sind. BSTs werden für effiziente Such-, Einfüge- und Löschvorgänge verwendet.

Warum einen binären Suchbaum verwenden?
BSTs bieten mehrere Vorteile:

Effiziente Suche: Die durchschnittliche Zeitkomplexität beträgt O(log n) für Suche, Einfügen und Löschen.
Dynamischer Satz von Elementen: Unterstützt dynamische Vorgänge im Gegensatz zu statischen Arrays.
Geordnete Elemente: Das Durchlaufen eines BST in der richtigen Reihenfolge liefert Elemente in einer sortierten Reihenfolge.
Schritt-für-Schritt-Anleitung zum Aufbau eines BST
Schritt 1: Definieren Sie die Knotenstruktur
Der erste Schritt besteht darin, die Struktur eines Knotens im Baum zu definieren. Jeder Knoten verfügt über drei Attribute: einen Wert, einen Verweis auf das linke untergeordnete Element und einen Verweis auf das rechte untergeordnete Element.

public class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

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

Schritt 2: Erstellen Sie die BST-Klasse mit dem Konstruktor
Als nächstes erstellen wir die BST-Klasse, die einen Verweis auf die Wurzel des Baums und die Methoden zum Einfügen von Elementen enthält.

public class BinarySearchTree {
    TreeNode root;

    public BinarySearchTree() {
        this.root = null;
    }
}

Schritt 3: Implementieren Sie die Einfügemethode
Um ein Element in das BST einzufügen, müssen wir die richtige Position für den neuen Knoten finden. Die Einfügemethode wird normalerweise als rekursive Funktion implementiert.

public void insert(int value) {
    root = insertRec(root, value);
}

private TreeNode insertRec(TreeNode root, int value) {
    // Base case: if the tree is empty, return a new node
    if (root == null) {
        root = new TreeNode(value);
        return root;
    }

    // Otherwise, recur down the tree
    if (value < root.value) {
        root.left = insertRec(root.left, value);
    } else if (value > root.value) {
        root.right = insertRec(root.right, value);
    }

    // Return the (unchanged) node pointer
    return root;
}

Visualisierung
Um besser zu verstehen, wie das Einfügen funktioniert, betrachten wir ein Beispiel. Angenommen, wir möchten die folgende Zahlenfolge in die BST einfügen: 50, 30, 70, 20, 40, 60, 80.

50

  50
 /
30

  50
 /  \
30  70

50
 /  \
30  70
/

40 einfügen:

  50
 /  \
30  70
/ \

60 einfügen

  50
 /  \
30  70
/ \  /

80 einfügen:

  50
 /  \
30  70
/ \  / \

Vollständiger Code
Hier ist der vollständige Code zum Erstellen eines BST und zum Einfügen von Elementen:

public class BinarySearchTree {
    TreeNode root;

    public BinarySearchTree() {
        this.root = null;
    }

    public void insert(int value) {
        root = insertRec(root, value);
    }

    private TreeNode insertRec(TreeNode root, int value) {
        if (root == null) {
            root = new TreeNode(value);
            return root;
        }

        if (value < root.value) {
            root.left = insertRec(root.left, value);
        } else if (value > root.value) {
            root.right = insertRec(root.right, value);
        }

        return root;
    }

    // Additional methods for traversal, search, and delete can be added here

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        int[] values = {50, 30, 70, 20, 40, 60, 80};
        for (int value : values) {
            bst.insert(value);
        }

        // Add code to print or traverse the tree
    }
}

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

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

Das obige ist der detaillierte Inhalt vonBinärer Suchbaum von Grund auf in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!