Binärbaum-Suche Implementation

[TobiCodi]

Hallo zusammen 🙂

Dies wäre meine Binärbaumsuche-Implementation. Ich soll den Node mit gegebenem Key zurückgeben, bzw. nil, wenn kein solcher Node existiert. Ist das folgende richtig?

public TreeNode search(int key) {
      
        TreeNode tmp = this._root;
        if(_root == _nil) {
            return _nil; //oder muss ich hier null zurückgeben?
        }
        
        if(tmp.key < key) {
            if(tmp.left != _nil) {
                return search(tmp.left.key);
            }
        }else if(tmp.key > key) {
            if(tmp.right != _nil) {
                return search(tmp.right.key);
            }
        }else if(tmp.key == key) {
            return tmp;
        }
        return _nil; // oder NULL ???
    }

Viele Grüße und Danke!!
TobiCodi

 

[LimDul]

Die funktioniert so nicht. Du steigst nie im Binärbaum ab - sondern du - änderst den Key.

Das ergibt eine Endlosschleife. Du musst in die Search Funktion den Knoten den die Suchfunktion als "ihren root" betrachten soll reingeben. Und den Key darfst du nie ändern.

 

[TobiCodi]

Die funktioniert so nicht. Du steigst nie im Binärbaum ab - sondern du - änderst den Key.

Das ergibt eine Endlosschleife. Du musst in die Search Funktion den Knoten den die Suchfunktion als "ihren root" betrachten soll reingeben. Und den Key darfst du nie ändern.

Okay danke schonmal. Ich darf leider die Parameterliste von search nicht ändern... aber ich könnte eine Hilfsfunktion schreiben! Ein Moment ich schick gleich mal was ich geändert hab

 

[TobiCodi]

    public TreeNode search(int key) {
       return searchRecursion(this._root, key);
    }
    
    private TreeNode searchRecursion(TreeNode node, int key) {
        if(_root == _nil) {
            return _nil; //oder return null?
        }
        if(key < node.key) {
            if(node.left != _nil){
                return searchRecursion(node.left, key);
            }
        }else if(key > node.key) {
            if(node.right != _nil) {
                return searchRecursion(node.right, key);
            }
        }else if(key == node.key){
            return node; //oder return null?
        }
        return _nil;
    }

 

[LimDul]

Jepp, so sieht es auf den ersten Blick richtig aus.

PS: Wer immer die Aufgabe gestellt hat möge mal die Steinzeit verlassen - Unterstriche zur Kennzeichnung von Membervariablen sind leicht veraltet 🙂

 

[TobiCodi]

Jepp, so sieht es auf den ersten Blick richtig aus.

PS: Wer immer die Aufgabe gestellt hat möge mal die Steinzeit verlassen - Unterstriche zur Kennzeichnung von Membervariablen sind leicht veraltet 🙂

Super danke! Das mit den Unterstrichen gebe ich gerne weiter xD. Ich rufe die Hilfmethode in search(int key){...} auch richtig auf oder? Also bei diesem this._root war ich mir unsicher. Außerdem wollen Sie ja nil returnen wenn kein solcher node existiert, darum ist das return _nil anstatt return null auch richtig oder?

LG

 

[LimDul]

Ja, das ist beides genau richtig. Du hast eine Hilfsmethode, die eine Binäre Suche von einem beliebigen Knoten nach unten startet.
Wenn du public search Methode aufrufst, delegiert die an die Hilfsmethode weiter - Start ist halt die oberste Ebene deines Binärbaums (this._root).

Wenn in der Aufgabe steht, es soll _nil zurückkommen, dann macht man das halt so - auch wenn ich es nicht verstehe 🙂

Was du dir sparen kannst, sind die Überprüfungen auf _nil vor dem rekursiven Aufruf:

 private TreeNode searchRecursion(TreeNode node, int key) {
        if(_root == _nil) {
            return _nil; //oder return null?
        }
        if(key < node.key) {
              return searchRecursion(node.left, key);
        }else if(key > node.key) {
              return searchRecursion(node.right, key);
        }else if(key == node.key){
            return node; //oder return null?
        }
        return _nil;
    }

Dadurch, das der erste Teil deiner searchRecursion Methode die überprüfung auf _nil ist, brauchst du die nicht vor dem Aufruf checken.