Binärbaum - von rekursiv zu iterativ

[ElifÖzt]

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:

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]

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
}

 

[ElifÖzt]

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)

 

[JBelarbi]

ich muss die gesamt klasse sehen.
versuch erstmal mit this.left statt item.left und item=this.left

 

[ElifÖzt]

Bei this. kommt type mismatch

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]

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]

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:

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

 

[JBelarbi]

    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]

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]

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 )

 

[ElifÖzt]

Okay jetzt ergibt alles Sinn, dankeschön