So implementieren Sie einen binären Suchbaumalgorithmus mit Java

So verwenden Sie Java zum Implementieren des binären Suchbaumalgorithmus

Der binäre Suchbaum (BST) ist eine häufig verwendete Datenstruktur, mit der Vorgänge wie Einfügen, Löschen und Suchen effizient implementiert werden können. In diesem Artikel wird die Verwendung von Java zum Implementieren eines binären Suchbaums vorgestellt und entsprechende Codebeispiele bereitgestellt.

1. Definition des binären Suchbaums

Der binäre Suchbaum ist ein geordneter Baum mit den folgenden Merkmalen:

1. Jeder Knoten hat einen eindeutigen Schlüsselwert.
2. Der Schlüsselwert des linken Teilbaums ist kleiner als der Schlüsselwert des Knotens, und der Schlüsselwert des rechten Teilbaums ist größer als der Schlüsselwert des Knotens.
3. Der linke Teilbaum und der rechte Teilbaum sind ebenfalls binäre Suchbäume.

2. Implementieren Sie die Knotenklasse des binären Suchbaums

Zuerst definieren wir eine Knotenklasse des binären Suchbaums, einschließlich Schlüsselwerten und Verweisen auf die linken und rechten untergeordneten Knoten. Der Code lautet wie folgt:

class Node {
    int data;
    Node left, right;

    public Node(int item) {
        data = item;
        left = right = null;
    }
}

In dieser Knotenklasse speichern wir die Referenzen der linken und rechten untergeordneten Knoten über das data字段保存节点的键值，left和right-Feld.

3. Implementieren Sie die Einfügeoperation des binären Suchbaums

Als nächstes implementieren wir die Einfügeoperation des binären Suchbaums. Der Einfügevorgang bestimmt die Einfügeposition des Knotens durch Vergleich der Schlüsselwertgröße des Knotens. Wenn der Schlüsselwert kleiner als der aktuelle Knoten ist, wird er in den linken Teilbaum eingefügt, andernfalls wird er in den rechten Teilbaum eingefügt. Der Code lautet wie folgt:

class BinarySearchTree {
    Node root;

    // 插入操作
    public void insert(int key) {
        root = insertRec(root, key);
    }

    private Node insertRec(Node root, int key) {
        // 如果树为空，创建一个新的节点
        if (root == null) {
            root = new Node(key);
            return root;
        }

        // 否则，递归地插入节点到左子树或右子树
        if (key < root.data)
            root.left = insertRec(root.left, key);
        else if (key > root.data)
            root.right = insertRec(root.right, key);

        return root;
    }
}

Beim Einfügevorgang ermitteln wir zunächst, ob der Baum leer ist, und erstellen, wenn er leer ist, einen neuen Knoten als Wurzelknoten. Andernfalls führen Sie eine rekursive Einfügung in den linken oder rechten Teilbaum durch Vergleich der Größenbeziehung zwischen dem Schlüsselwert und dem aktuellen Knoten durch.

4. Implementieren Sie die Suchoperation des binären Suchbaums. Die Suchoperation des binären Suchbaums ist relativ einfach. Sie vergleicht die Größenbeziehung zwischen dem Schlüsselwert und dem Knoten Schritt für Schritt, bis eine Übereinstimmung gefunden wird oder ein leerer Knoten vorhanden ist Knoten gefunden wird. Der Code lautet wie folgt:

class BinarySearchTree {
    ...

    // 查找操作
    public boolean contains(int key) {
        return containsRec(root, key);
    }

    private boolean containsRec(Node root, int key) {
        // 树为空或者找到匹配节点
        if (root == null || root.data == key)
            return (root != null);

        // 比较键值与当前节点
        if (key < root.data)
            return containsRec(root.left, key);
        else
            return containsRec(root.right, key);
    }
}

Beim Suchvorgang ermitteln wir zunächst, ob der Baum leer ist oder ob der aktuelle Knoten übereinstimmt. Gibt „true“ zurück, wenn eine Übereinstimmung vorliegt. Andernfalls wird der linke oder rechte Teilbaum rekursiv durchsucht, indem die Größe des Schlüsselwerts mit dem aktuellen Knoten verglichen wird.

5. Code zum Testen des binären Suchbaums

Abschließend schreiben wir Code zum Testen des von uns implementierten binären Suchbaums. Der Code lautet wie folgt:

public class Main {
    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();

        tree.insert(50);
        tree.insert(30);
        tree.insert(20);
        tree.insert(40);
        tree.insert(70);
        tree.insert(60);
        tree.insert(80);

        System.out.println(tree.contains(30));
        System.out.println(tree.contains(90));
    }
}

Das laufende Ergebnis ist:

true
false

Hier fügen wir einige Knoten in den Baum ein, indem wir die Einfügeoperation aufrufen. Dann rufen wir die Suchoperation auf, um Knoten mit den Schlüsselwerten 30 bzw. 90 zu finden. Das zurückgegebene Ergebnis gibt an, ob der Einfügevorgang erfolgreich war.

Durch die oben genannten Schritte haben wir den binären Suchbaumalgorithmus mithilfe von Java erfolgreich implementiert und die Einfüge- und Suchvorgänge implementiert. In praktischen Anwendungen können binäre Suchbäume auch Funktionen wie Löschvorgänge, Pre-Order-, In-Order- und Post-Order-Traversal unterstützen. Leser können die Implementierung je nach spezifischem Bedarf weiter ausbauen.

Das obige ist der detaillierte Inhalt vonSo implementieren Sie einen binären Suchbaumalgorithmus mit Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!