Binärbaum-Suche Implementation

T

TobiCodi

Mitglied
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?

Java:
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
 
L

LimDul

Top Contributor
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.
 
T

TobiCodi

Mitglied
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
 
T

TobiCodi

Mitglied
Java:
    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;
    }
 
L

LimDul

Top Contributor
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 :)
 
T

TobiCodi

Mitglied
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
 
L

LimDul

Top Contributor
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:

Java:
 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.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
D Binärbaum Suche Java Basics - Anfänger-Themen 5
Y Wie greift man auf die Knoten in einem Binärbaum zu? Java Basics - Anfänger-Themen 5
A Binärbaum rekursiv durchsuchen und Referenz zurückgeben Java Basics - Anfänger-Themen 4
D Werte aus einem BinärBaum in einem Array speichern Java Basics - Anfänger-Themen 1
D Binärbaum Blätter finden und Ausgeben Java Basics - Anfänger-Themen 22
O BinärBaum einfügen Java Basics - Anfänger-Themen 13
E Erste Schritte Testklasse Binärbaum Java Basics - Anfänger-Themen 10
void19 Methoden Binärbaum Inorder Traversierung in Array speichern Java Basics - Anfänger-Themen 1
A Größten Eintrag aus Binärbaum löschen Java Basics - Anfänger-Themen 4
L Ganzen BinärBaum ausgeben? Java Basics - Anfänger-Themen 3
L Binärbaum (Stammbaum) Java Basics - Anfänger-Themen 2
S Binärbaum in PreOrder in ArrayList speichern Java Basics - Anfänger-Themen 0
J Methoden Binärbaum, Traversierung in Array speichern Java Basics - Anfänger-Themen 18
K BinärBaum Java Basics - Anfänger-Themen 4
J Max. Anzahl von Knoten im Binärbaum Java Basics - Anfänger-Themen 3
M Werte der Knoten in Binärbaum addieren (iterativ) Java Basics - Anfänger-Themen 6
C Binärbaum mit grafischer Ausgabe Java Basics - Anfänger-Themen 0
J Binärbaum formatiert ausgeben. Java Basics - Anfänger-Themen 7
P Listen sortieren mit Binärbaum gibt keine Ausgabe ab 10000 Integern Java Basics - Anfänger-Themen 14
E Binärbaum - von rekursiv zu iterativ Java Basics - Anfänger-Themen 10
W Größtes Element im unsortierten Binärbaum Java Basics - Anfänger-Themen 7
N Generischer Binärbaum - löschen Java Basics - Anfänger-Themen 1
M Binärbaum mit parent-Zeigern Java Basics - Anfänger-Themen 1
B Methoden BinärBaum als String Knoten löschen Java Basics - Anfänger-Themen 5
S Binärbaum kopieren Java Basics - Anfänger-Themen 6
B Binärbaum mit java implementieren! Java Basics - Anfänger-Themen 5
D Binärbaum probleme Java Basics - Anfänger-Themen 4
P Binärbaum - Primärschlüssel Java Basics - Anfänger-Themen 3
X Fehler Binärbaum Java Basics - Anfänger-Themen 6
PaulG Fragen zu Binärbaum Java Basics - Anfänger-Themen 21
N Binärbaum/Implementierung Java Basics - Anfänger-Themen 9
P Binärbaum Ordnungsproblem Java Basics - Anfänger-Themen 8
P Generischer Binärbaum (compareTo Frage) Java Basics - Anfänger-Themen 4
P einen binärbaum implementieren Java Basics - Anfänger-Themen 4
M Binärbaum - Problem bei Knoten anhängen / löschen Java Basics - Anfänger-Themen 5
B Binärbaum höhe herausfinden Java Basics - Anfänger-Themen 12
L Rot Scharz Baum von Binärbaum erben Java Basics - Anfänger-Themen 9
S Klassen Aufgabe: Binärbaum überprüfen Java Basics - Anfänger-Themen 16
S Binärbaum Java Basics - Anfänger-Themen 9
S Variable Parameterliste in Binärbaum Java Basics - Anfänger-Themen 2
N BinärBaum Hilfestellung Java Basics - Anfänger-Themen 8
S Binärbaum prüfen, ob sortiert oder unsortiert Java Basics - Anfänger-Themen 6
W Binärbaum zahlen addieren Java Basics - Anfänger-Themen 4
S Binärbaum - Klasse Knoten - Methode Suchen Java Basics - Anfänger-Themen 5
S Binärbaum Java Basics - Anfänger-Themen 7
I Binärbaum Java Basics - Anfänger-Themen 5
S Bitte um Hilfe beim unsortierten Binärbaum!! Java Basics - Anfänger-Themen 6
J Binärbaum getSize Java Basics - Anfänger-Themen 4
P Fragen zum Binärbaum Java Basics - Anfänger-Themen 3
S Binärbaum implementieren Java Basics - Anfänger-Themen 6
K Tiefe im Binärbaum Java Basics - Anfänger-Themen 2
G generischer binärbaum Java Basics - Anfänger-Themen 9
G Binärbaum und Wrapperklassen Java Basics - Anfänger-Themen 6
F Binärbaum codieren. Codeproblem! Java Basics - Anfänger-Themen 4
D rekursion im binärbaum Java Basics - Anfänger-Themen 11
0 Binärbaum als verkettete Liste Java Basics - Anfänger-Themen 3
T Binärbaum - noch ein "klitzekleiner Fehler" Java Basics - Anfänger-Themen 4
B Binärbaum auf Vollständigkeit prüfen Java Basics - Anfänger-Themen 15
G Frage zur einfügen in einem Binärbaum Java Basics - Anfänger-Themen 21
G Binärbaum grafisch darstellen Java Basics - Anfänger-Themen 4
Y Suche von Studenten anhand Ihrer Eigenschaften. Java Basics - Anfänger-Themen 1
F Auf der Suche in π Java Basics - Anfänger-Themen 13
C Suche Nachhilfe in Java Java Basics - Anfänger-Themen 5
A suche dringend Hilfe!! Java Basics - Anfänger-Themen 6
N Operatoren Schreibtischtest der Reihen-Suche nach Aufschluss in die Basics Java Basics - Anfänger-Themen 1
B Suche free SVN Hosting Java Basics - Anfänger-Themen 12
S Binäre-Suche Algorithmus Java Basics - Anfänger-Themen 1
S Java Lineare-Suche Zeitmessung Java Basics - Anfänger-Themen 5
S Java Lineare Suche Java Basics - Anfänger-Themen 1
S Binäre-Suche bei unsortierten Daten Java Basics - Anfänger-Themen 7
E Die richtige Suche in der API Java Basics - Anfänger-Themen 1
S suche nach varible POSITION ... fuer das pixel-maennchen Java Basics - Anfänger-Themen 4
E Weg-Suche-Problem rekursiv Java Basics - Anfänger-Themen 12
B Suche Programme mit Fehlern Java Basics - Anfänger-Themen 9
jaleda100 Component für Suche Java Basics - Anfänger-Themen 4
L Suche ein sampel Projekt Java Basics - Anfänger-Themen 2
P Suche Aufwandsgenerator (o-notation) Java Basics - Anfänger-Themen 1
S Suche aktuelles 2D Grafik Tutorial Java Basics - Anfänger-Themen 5
M Suche hilfe bei Array Java Basics - Anfänger-Themen 4
L Binäre Suche mit Comparator Java Basics - Anfänger-Themen 5
J Methoden Suche effiziente Implementierung für eine Methode Java Basics - Anfänger-Themen 3
D Ich suche nach einer Möglickeit den Webseiten Inhalt per Java zu analysieren Automatisch Java Basics - Anfänger-Themen 3
B String: suche nach Wörter und in List<String> speichern Java Basics - Anfänger-Themen 3
D Erste Schritte Suche Quelltext Java Basics - Anfänger-Themen 7
M Rekursion Minimums Suche Java Basics - Anfänger-Themen 12
J Suche Hilfestellung Java Basics - Anfänger-Themen 10
G Erste Schritte Suche Java Programmierer für kleines Projekt Java Basics - Anfänger-Themen 1
J Suche die Emailadresse Java Basics - Anfänger-Themen 6
H Suche in Text und Markierung Java Basics - Anfänger-Themen 14
H Suche in einem Text Java Basics - Anfänger-Themen 17
H Erste Schritte Binäre Suche Java Basics - Anfänger-Themen 37
J Suche simples Beispiel für die EOFException Java Basics - Anfänger-Themen 1
H Rekursion Binäre Suche Java Basics - Anfänger-Themen 2
L Binäre Suche Java Basics - Anfänger-Themen 2
L Linerae Suche in einem sortierten Array Java Basics - Anfänger-Themen 2
N Array, lineare Suche, binäre Suche, Programm bleibt unerwartet stehen... Java Basics - Anfänger-Themen 6
I Innerhalb einer Methode suchen und hinzufügen. Neues Objekt in Suche dann? Java Basics - Anfänger-Themen 8
B Binäre Suche - Junit Test Java Basics - Anfänger-Themen 6
L Einfache Lineare Suche Java Basics - Anfänger-Themen 7
J Binäre Suche eines Array Java Basics - Anfänger-Themen 5

Ähnliche Java Themen

Anzeige

Neue Themen


Oben