Einfügen eines Knotens in einen binären Suchbaum

Definieren Sie zunächst einen binären Suchbaum, der im Java-Code wie folgt dargestellt wird:

public class BST<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 BST() {
        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;
    }
}

Node repräsentiert einen Knoten, und count repräsentiert die Anzahl der Knoten.

Das folgende Beispiel zeigt die Schritte zum Einfügen des Elements 61 in den unten stehenden binären Suchbaum:

(1) Das einzufügende Element 61 ist größer als 42; vergleichen Sie den Wurzelknoten des rechten Teilbaums von 42.

(2) 61 ist größer als 59, also muss 61 an die entsprechende Position im rechten Teilbaum von 59 verschoben werden. Da dieser hier leer ist, fügen Sie es direkt als rechten Kindknoten von 59 ein.

Die Einfügeoperation ist ebenfalls ein rekursiver Prozess, der drei Fälle abdeckt: gleich, größer als und kleiner als.

Java-Beispielcode

Quellcode-Paket-Download:Herunterladen

src/example/binary/BinarySearchTreeInsert.java Datei-Code:

package example.binary;

/**
* Fügt ein neues Element in den binären Suchbaum ein
 */

public class BinarySearchTreeInsert<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;
        }
    }

    private Node root;  // Wurzelknoten
    private int count;  // Anzahl der Knoten im Baum

    // Konstruktor, erstellt standardmäßig einen leeren binären Suchbaum
    public BinarySearchTreeInsert() {
        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);
    }

    // Kerncode --- Start
    // 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;
    }
    // Kerncode --- Ende
}
Weitere Erweiterungen