Tiefensuche im binären Suchbaum

Die Traversierung eines binären Suchbaums wird in zwei Hauptkategorien unterteilt: Tiefensuche und Breitensuche.

Die Tiefensuche wird in drei Arten unterteilt: Preorder-Baumdurchlauf, Inorder-Baumdurchlauf und Postorder-Baumdurchlauf, die jeweils wie folgt lauten:

  • 1. Preorder-Traversierung:Zuerst wird der aktuelle Knoten besucht, dann werden der linke und der rechte Teilbaum der Reihenfolge nach rekursiv besucht.
  • 2. Inorder-Traversierung: Zuerst wird der linke Teilbaum rekursiv besucht, dann der aktuelle Knoten selbst, dann der rechte Teilbaum rekursiv besucht.
  • 3. Postorder-Traversierung: Zuerst werden der linke und der rechte Teilbaum rekursiv besucht, dann wird der aktuelle Knoten selbst besucht.

Diagramm des Ergebnisses der Preorder-Traversierung:

Zugehöriges Codebeispiel:

...
// Führe eine Preorder-Traversierung auf dem binären Suchbaum mit Wurzel node durch, rekursiver Algorithmus
private void preOrder(Node node){

    if( node != null ){
        System.out.println(node.key);
        preOrder(node.left);
        preOrder(node.right);
    }
}
...

Diagramm des Ergebnisses der Inorder-Traversierung:

Zugehöriges Codebeispiel:

...
// Führe eine Inorder-Traversierung auf dem binären Suchbaum mit Wurzel node durch, rekursiver Algorithmus
private void inOrder(Node node){

    if( node != null ){
        inOrder(node.left);
        System.out.println(node.key);
        inOrder(node.right);
    }
}
...

Diagramm des Ergebnisses der Postorder-Traversierung:

Zugehöriges Codebeispiel:

...
// Führe eine Postorder-Traversierung auf dem binären Suchbaum mit Wurzel node durch, rekursiver Algorithmus
private void postOrder(Node node){

    if( node != null ){
        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.key);
    }
}
...

Java-Beispielcode

Quellcode-Paket-Download:Download

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

package example.binary;

/**
* Prioritätsdurchlauf
 */


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

    // Preorder-Durchlauf des binären Suchbaums
    public void preOrder(){
        preOrder(root);
    }

    // Inorder-Durchlauf des binären Suchbaums
    public void inOrder(){
        inOrder(root);
    }

    // Postorder-Durchlauf des binären Suchbaums
    public void postOrder(){
        postOrder(root);
    }

    //********************
    //* 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 );
    }

    // Führe eine Preorder-Traversierung auf dem binären Suchbaum mit Wurzel node durch, rekursiver Algorithmus
    private void preOrder(Node node){

        if( node != null ){
            System.out.println(node.key);
            preOrder(node.left);
            preOrder(node.right);
        }
    }

    // Führe eine Inorder-Traversierung auf dem binären Suchbaum mit Wurzel node durch, rekursiver Algorithmus
    private void inOrder(Node node){

        if( node != null ){
            inOrder(node.left);
            System.out.println(node.key);
            inOrder(node.right);
        }
    }

    // Führe eine Postorder-Traversierung auf dem binären Suchbaum mit Wurzel node durch, rekursiver Algorithmus
    private void postOrder(Node node){

        if( node != null ){
            postOrder(node.left);
            postOrder(node.right);
            System.out.println(node.key);
        }
    }
}
Weitere Erweiterungen