Binärbaum - von rekursiv zu iterativ

ElifÖzt

Mitglied
Hallo Leute,
ich habe einen Binärbaum gegeben und muss in diesen neue Elemente einfügen. In der Klasse ist eine Methode insert(Comparable elem) vorhanden, die neue Elemente rekursiv einfügt. Nun muss ich eine Methode insertLoop(Comparable elem) implementieren, die das selbe wie insert macht nur eben nicht rekursiv sondern mit einer Schleife also iterativ.

Ich hätte zuerst überprüft, ob das neue Element größer oder kleiner als die Wurzel ist, wenn kleiner hätte ich mittels for-Schleife den linken Teilbaum durchlaufen und bei item == null mein neues Element eingefügt (am Ende noch neue null Elemente erzeugt), wenn größer, das selbe für den rechten Teilbaum.

Nun weiß ich nicht, wie ich die for-Schleifen implementieren kann, da man ja bei Binärbäume nicht sowas wie length bei Arrays hat.

Quellcode von der rekursiven Methode:

Java:
public void insert(Comparable elem)
{
        if (item == null)
        {
            item = elem;
            left = new BinTree();
            right = new BinTree();
        } else {
            BinTree next;
            if (item.compareTo(elem) > 0)
                next = left;
            else
                next = right;
            next.insert(elem);
        }
}

Ich hoffe ihr bringt mich auf die Sprünge.
LG ElifÖzt :)
 

JBelarbi

Mitglied
Java:
public void insert(Comparable elem){

while(item !=elem){
    if(item.compareTo(elem) > 0 ){
        if (item.left == null){
            item.left= elem;
            break; // elem wurde eingefügt also schleife wird unterbrochen.
        }else{
                 item=item.left;
                }
     // und so weiter machst du für die rechte Seite
    }
}// End while
}
 
Zuletzt bearbeitet von einem Moderator:

ElifÖzt

Mitglied
Danke für die schnelle Antwort JBelarbi, vom Vorgehen her ist mir das klar, was du gemacht hast, aber irgendwie werden left und right nicht als Variablen akzeptiert. (left cannot be resolved or is not a field)
 

ElifÖzt

Mitglied
Bei this. kommt type mismatch

Java:
class BinTree
{
    private Comparable item;
    private BinTree left, right;
   
    public void insert(Comparable elem)
    {
        if (item == null)
        {
            item = elem;
            left = new BinTree();
            right = new BinTree();
        } else {
            BinTree next;
            if (item.compareTo(elem) > 0)
                next = left;
            else
                next = right;
            next.insert(elem);
        }
    }

    public void insertLoop(Comparable elem)
    {
        while(item !=elem){
            if(item.compareTo(elem) > 0 ){
                if (item.left == null){
                    item.left= elem;
                    break; // elem wurde eingefügt also schleife wird unterbrochen.
                } else{
                item=item.left;
                }
                // und so weiter machst du für die rechte Seite
            }
            if(item.compareTo(elem) < 0 ){
                if (item.right == null){
                    item.right = elem;
                    break; // elem wurde eingefügt also schleife wird unterbrochen.
                } else{
                item=item.right;
                }
            }
        }
       
    }
   
    public Comparable search(Comparable elem)
    {
        if (item == null)
            return null;
        int res = item.compareTo(elem);
        if (res == 0)
            return item;
        return ((res > 0) ? left : right).search(elem);
    }

    public String toString()
    {
        if (item == null)
            return "";
        return left.toString() + item.toString() + " " + right.toString();
    }

    public static void main(String[] args)
    {
        BinTree tree = new BinTree();
        tree.insert(5);
        tree.insert(4);
        tree.insert(2);
        tree.insert(1);
        tree.insert(3);
        tree.insert(10);
        tree.insert(6);
        tree.insert(12);
        tree.insert(8);
        System.out.println(tree);
    }
}
 

JBelarbi

Mitglied
Java:
if(item.compareTo(elem) > 0 ){
                if (this.left == null){
                    left.item = elem;
                    break; // elem wurde eingefügt also schleife wird unterbrochen.
                } else{
                item=left.item;
                }
 

ElifÖzt

Mitglied
Okay danke, jetzt habe ich keine Fehlermeldungen mehr, aber wenn ich jetzt die inserts in der Main-Methode zu insertLoop verändere kommt bei mir als Ergebnis:
Code:
Exception in thread "main" java.lang.NullPointerException
    at BinTree.insertLoop(BinTree.java:26)
    at BinTree.main(BinTree.java:67)
aber eigentlich sollte es ja dasselbe machen
 
Zuletzt bearbeitet von einem Moderator:

JBelarbi

Mitglied
Java:
    public void insertLoop(Comparable elem) {
        BinTree next =this;
       
        while (next.item != elem) {
           
            if (item == null) {
                item = elem;
                left = new BinTree();
                right = new BinTree();
            } else {
               
                if (next.item.compareTo(elem) > 0) {
                   
                    if (next.left.item == null) {
                        next.left.item = elem;
                        next.left.left = new BinTree();
                        next.left.right= new BinTree();
                        break;
                    } else {
                       
                        next  = next.left;
                    }

                }
                else {
                  
                    if (next.right.item == null) {
                        next.right.item = elem;
                        next.right.left = new BinTree();
                        next.right.right= new BinTree();
                        break;
                    } else {
                        next = next.right;
                    }
                }
            }
        }
      
    }
 

ElifÖzt

Mitglied
Wow, danke, das ist echt super von dir :)
Kannst du mir aber vielleicht mal erklären, warum du das mit dem this gemacht hast? Dann kann ich es das nächste mal auch machen
 

JBelarbi

Mitglied
Also die next ist wie ein Iterator der zeigt am Anfang an der oberste Node von der Baum daher
next = This; (this is a reference to the current objec )
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
A Binärbaum rekursiv durchsuchen und Referenz zurückgeben Java Basics - Anfänger-Themen 4
Y Wie greift man auf die Knoten in einem Binärbaum zu? Java Basics - Anfänger-Themen 5
T Binärbaum-Suche Implementation Java Basics - Anfänger-Themen 6
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 8
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
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 Suche 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 7
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
H Passwort Brute Force rekursiv Java Basics - Anfänger-Themen 7
1 Array rekursiv durchlaufen Java Basics - Anfänger-Themen 8
E Rekursiv Objekte erzeugen - geht das? Java Basics - Anfänger-Themen 2
Cassy3 Binäre Bäume Rekursiv durchlaufen und bestimmte Elemente Zählen Java Basics - Anfänger-Themen 6
R0m1lly Kombinationen aus int array rekursiv Java Basics - Anfänger-Themen 2
L Rekursiv gegebenes Passwort herausfinden. Java Basics - Anfänger-Themen 2
P9cman Char Index rekursiv finden Java Basics - Anfänger-Themen 4
B Methoden Rekursiv festellen, ob eine Zahl gerade-oft vorkommt oder nicht Java Basics - Anfänger-Themen 4
S Methoden Methodenaufruf rekursiv zählen Java Basics - Anfänger-Themen 4
B Array nach Wert prüfen rekursiv Java Basics - Anfänger-Themen 5
sashady Zahlen rekursiv zerlegen und Ziffern addieren Java Basics - Anfänger-Themen 38
jhCDtGVjcZGcfzug Fibonacci Zahlen rekursiv und iterativ Java Basics - Anfänger-Themen 21
H Binominalkoeffizient tail-rekursiv in java darstellen Java Basics - Anfänger-Themen 0
GAZ Tribonacci Folge Rekursiv Java Basics - Anfänger-Themen 11
G Primzahlen von Rekursiv nach Iterativ Java Basics - Anfänger-Themen 6
A Ackermmanfunktion rekursiv Java Basics - Anfänger-Themen 4
H Rekursiv Methode ausführen bei Kindern Java Basics - Anfänger-Themen 12
G Methode Rekursiv umschreiben Java Basics - Anfänger-Themen 8
L Jede zweite Ziffer entfernen (rekursiv) Java Basics - Anfänger-Themen 6
J Dateien in Verzeichnissen rekursiv auflisten wirft Exception Java Basics - Anfänger-Themen 4
D Pentagonale Nummern in Rekursiv Java Basics - Anfänger-Themen 14
O Enum Array Rekursiv abarbeiten Java Basics - Anfänger-Themen 44
E Weg-Suche-Problem rekursiv Java Basics - Anfänger-Themen 12
O Primzahl rekursiv mit einem Wert ohne i, wie? Java Basics - Anfänger-Themen 6
E Erste Schritte Potenz Negativ (rekursiv) Java Basics - Anfänger-Themen 2
O Rekursiv aufrufen Java Basics - Anfänger-Themen 2
F In List Rekursiv suchen Java Basics - Anfänger-Themen 12
F Iterativ in Rekursiv Java Basics - Anfänger-Themen 2
S Fibonacci Zahlen rekursiv Java Basics - Anfänger-Themen 1
L Rekursiv zwei Strings vergleichen Java Basics - Anfänger-Themen 3
B Fakultätsfunktion Rekursiv Berechnen aber mit Array Java Basics - Anfänger-Themen 10
J Fibonacci -Folge rekursiv berechnen Java Basics - Anfänger-Themen 18
B Wie kann ich Linien rekursiv zeichnen? Java Basics - Anfänger-Themen 4
kilopack15 Sin(x) rekursiv lösen Java Basics - Anfänger-Themen 17
T Rekursiv Tiefe eines binären Suchbaums ermitteln Java Basics - Anfänger-Themen 22
P Methoden Arrays.AsList kleinste Zahl ausgeben Rekursiv Java Basics - Anfänger-Themen 9
W A hoch N Rekursiv Java Basics - Anfänger-Themen 3
K Rechtecke rekursiv zeichnen Java Basics - Anfänger-Themen 20
V Quadrate rekursiv zeichnen Java Basics - Anfänger-Themen 7
M Fibonacci rekursiv mittels Cache Java Basics - Anfänger-Themen 17

Ähnliche Java Themen

Neue Themen


Oben