Nachschlagen eines Knotens im binären Suchbaum

Der binäre Suchbaum hat keinen Index, daher wird hier für die Suchoperation im binären Suchbaum eine contain-Methode definiert, die bestimmt, ob der binäre Suchbaum ein bestimmtes Element enthält, und eine boolesche Variable zurückgibt. Diese Suchoperation ist ebenfalls ein rekursiver Prozess. Die konkrete Codeimplementierung ist wie folgt:

...
// Prüft, ob der bei node verwurzelte binäre Suchbaum einen Knoten mit Schlüsselwert key enthält, unter Verwendung eines rekursiven Algorithmus
private boolean contain(Node node, Key key){

    if( node == null )
        return false;

    if( key.compareTo(node.key) == 0 )
        return true;
    else if( key.compareTo(node.key) < 0 )
        return contain( node.left , key );
    else // key > node->key
        return contain( node.right , key );
}
...

Das folgende Beispiel sucht im binären Suchbaum nach Element 43.

(1)Element 43 ist größer als der Wurzelknoten 42, daher muss der Vergleich am rechten Kindknoten fortgesetzt werden.

(2)Element 43 ist kleiner als 59, daher muss der Vergleich am linken Kindknoten fortgesetzt werden.

(3)Element 43 ist kleiner als 51, daher muss es im linken Kindknoten weiter verglichen werden.

(4)Finde den linken Kindknoten 43 von 51, der genau gleich ist, und der Vorgang endet.

Wenn Sie den zum Schlüssel gehörenden Wert finden müssen, lautet der Code wie folgt:

...
// Finde den Wert, der key im binären Suchbaum mit Wurzel node entspricht, rekursiver Algorithmus
// Gib NULL zurück, wenn der Wert nicht existiert
private Value search(Node node, Key key){

    if( node == null )
        return null;

    if( key.compareTo(node.key) == 0 )
        return node.value;
    else if( key.compareTo(node.key) < 0 )
        return search( node.left , key );
    else // key > node->key
        return search( node.right, key );
}
...

Java-Beispielcode

Quellcode-Paket-Download:Download

Code der Datei src/example/binary/BinarySearchTreeSearch.java:

package example.binary;

/**
* Suche im binären Suchbaum
 */

public class BinarySearchTreeSearch<Key extends Comparable<Key>, Value> {
    // Die Knoten im Baum sind eine private Klasse; die Außenwelt muss die spezifische Implementierung der Knoten des binären Suchbaums nicht kennen.
    private class Node {
        private Key key;
        private Value value;
        private Node left, right;

        public Node(Key key, Value value) {
            this.key = key;
            this.value = value;
            left = right = null;
        }
    }
    // Wurzelknoten
    private Node root;
    // Anzahl der Knoten im Baum
    private int count;

    // Konstruktor, erstellt standardmäßig einen leeren binären Suchbaum
    public BinarySearchTreeSearch() {
        root = null;
        count = 0;
    }

    // Gibt die Anzahl der Knoten im binären Suchbaum zurück
    public int size() {
        return count;
    }

    // Gibt zurück, ob der binäre Suchbaum leer ist
    public boolean isEmpty() {
        return count == 0;
    }

    // Fügt ein neues Datenpaar (Schlüssel, Wert) in den binären Suchbaum ein
    public void insert(Key key, Value value){
        root = insert(root, key, value);
    }

    // Prüft, ob der Schlüssel im binären Suchbaum existiert
    public boolean contain(Key key){
        return contain(root, key);
    }

    // Durchsucht den binären Suchbaum nach dem Wert, der dem Schlüssel entspricht. Wenn der Wert nicht vorhanden ist, wird null zurückgegeben
    public Value search(Key key){
        return search( root , key );
    }


    //********************
    //* Hilfsfunktionen für den binären Suchbaum
    //********************

    // Knoten (key, value) in den bei node verwurzelten binären Suchbaum einfügen, unter Verwendung eines rekursiven Algorithmus
    // Gibt die Wurzel des binären Suchbaums nach dem Einfügen des neuen Knotens zurück
    private Node insert(Node node, Key key, Value value){

        if( node == null ){
            count ++;
            return new Node(key, value);
        }

        if( key.compareTo(node.key) == 0 )
            node.value = value;
        else if( key.compareTo(node.key) < 0 )
            node.left = insert( node.left , key, value);
        else    // key > node->key
            node.right = insert( node.right, key, value);

        return node;
    }

    // Prüft, ob der bei node verwurzelte binäre Suchbaum einen Knoten mit Schlüsselwert key enthält, unter Verwendung eines rekursiven Algorithmus
    private boolean contain(Node node, Key key){

        if( node == null )
            return false;

        if( key.compareTo(node.key) == 0 )
            return true;
        else if( key.compareTo(node.key) < 0 )
            return contain( node.left , key );
        else // key > node->key
            return contain( node.right , key );
    }

    // Finde den Wert, der key im binären Suchbaum mit Wurzel node entspricht, rekursiver Algorithmus
    // Gib NULL zurück, wenn der Wert nicht existiert
    private Value search(Node node, Key key){

        if( node == null )
            return null;

        if( key.compareTo(node.key) == 0 )
            return node.value;
        else if( key.compareTo(node.key) < 0 )
            return search( node.left , key );
        else // key > node->key
            return search( node.right, key );
    }
}
Weitere Erweiterungen