# Binärbaum - von rekursiv zu iterativ



## ElifÖzt (22. Nov 2015)

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 (22. Nov 2015)

```
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 (22. Nov 2015)

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 (22. Nov 2015)

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


----------



## ElifÖzt (22. Nov 2015)

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 (22. Nov 2015)

```
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 (22. Nov 2015)

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 (22. Nov 2015)

```
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 (22. Nov 2015)

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 (22. Nov 2015)

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 (22. Nov 2015)

Okay jetzt ergibt alles Sinn, dankeschön


----------

